เราจะพิจารณาปัญหาที่เราได้รับสตริงจำนวนเต็มและต้องกำหนดจำนวนสตริงย่อยที่หารด้วย 6 ลงตัวในรูปแบบจำนวนเต็ม ควรสังเกตว่าอินพุตอยู่ในรูปสตริงที่สร้างจากตัวเลข (จำนวนเต็ม) อย่างไรก็ตาม การตรวจสอบการหารจะดำเนินการโดยพิจารณาว่าเป็นจำนวนเต็มเท่านั้น (ไม่ใช้ค่า ASCII ของอินพุตสตริง)
ป้อนข้อมูล
str = “648”
ผลผลิต
คำอธิบาย
สตริงย่อย “6”, “48” และ “648” หารด้วย 6 ลงตัว
ป้อนข้อมูล
str = “38342”
ผลผลิต
4
คำอธิบาย
สตริงย่อย “3834”, “342”, ”834” และ “42” หารด้วย 6 ลงตัว
แนวทางเดรัจฉาน
ผู้ใช้สามารถตรวจสอบสตริงย่อยที่เป็นไปได้ทั้งหมดเพื่อดูว่าหารด้วยหกลงตัวหรือไม่ หากสตริงย่อยหารลงตัว ให้นับเพิ่มเติมด้วย วิธีนี้จะใช้เวลาแก้ปัญหานานกว่าและใช้เวลา O(n2) ในการดำเนินการให้สำเร็จ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
int temp = 0;
for (; i <= j; i++) {
temp = temp * 10 + (str[i] - '0');
}
return temp;
}
int main () {
char str[] = "24661";
int n = strlen (str);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = str_to_int (str, i, j);
if (temp % 6 == 0) count++;
}
}
cout << count << endl;
return 0;
} ผลลัพธ์
6
แนวทางที่มีประสิทธิภาพ
ตัวเลขหลักสุดท้ายของตัวเลขต้องหารด้วย 2 ลงตัวจึงจะหารด้วย 6 ลงตัว จำนวนหลักทั้งหมดควรเป็น 3 โดยการติดตามคำตอบที่คำนวณไว้ก่อนหน้านี้ เราอาจใช้โปรแกรมแบบไดนามิกเพื่อค้นหาวิธีแก้ปัญหา
ให้ f(i,s) - จำนวนสตริงจากดัชนี ith ที่มีตัวเลขรวม modulo 3 คือ s ซึ่งให้ Σin-1 f(i,0)
ให้ เป็นตัวเลข ith ของสตริง จาก f(i,s) เราจำเป็นต้องค้นหาสตริงย่อยทั้งหมดที่เป็นคู่และเริ่มต้นด้วย i + 1 ถ้า (a+s) หารด้วย 3 ลงตัว จะสร้างสตริงย่อยเพิ่มเติมได้ ดังนั้นความสัมพันธ์ที่เกิดขึ้นซ้ำของเราจึงเกิดขึ้น ,
f(i,s) =f(i + 1, (s + a)%3) + ( a%2 ==0 AND (a+s)%3 ==0).
ตัวอย่างที่ 2
#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
// when reached end of string.
if (i == strlen(str))
return 0;
// if already computed then return result.
if (dp[i][s] != -1)
return dp[i][s];
int a = str[i] - '0';
int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
return dp[i][s] = ans;
}
int main(){
char str[] = "24661";
int n = strlen(str);
// dp array to store all states.
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++){
// if any position contains 0 increment count.
if (str[i] == '0')
count++;
// Passing previous sum modulo 3 = 0 to recursive function.
else
count += find(i, 0, str, dp);
}
cout << "Number of substrings divisible by 6: " << count << endl;
return 0;
} ผลลัพธ์
Number of substrings divisible by 6: 6
ความซับซ้อนของเวลา:O(N)
บทสรุป
ในบทช่วยสอนนี้ เราได้เรียนรู้วิธีใช้การเขียนโปรแกรมแบบไดนามิกเพื่อค้นหาจำนวนสตริงย่อยที่หารด้วย 6 ลงตัวในสตริงของจำนวนเต็ม โปรแกรมเดียวกันอาจเขียนในภาษาต่างๆ เช่น C, Java, Python และอื่นๆ เราหวังว่าคุณจะพบว่าบทเรียนนี้เป็นประโยชน์
