สตริงของ 0-9 จะได้รับ สำหรับปัญหานี้ เราต้องคำนวณจำนวนสตริงที่หารด้วย 8 ลงตัว ไม่ใช่ 3 นี่เป็นปัญหา 2 ขั้นตอน และเราต้องทำโค้ดทีละขั้นตอนเพื่อแก้ปัญหา เช่น
ป้อนข้อมูล
str = "80"
ผลผลิต
2
ป้อนข้อมูล
str = "7675636788"
ผลผลิต
15
แนวทางในการหาแนวทางแก้ไข
เฉพาะตัวเลขที่มี 3 หลักสุดท้ายเท่านั้นที่หารด้วย 8 ลงตัว และผลรวมของหลักหารด้วย 3 ลงตัวจะหารด้วย 8 ลงตัว
ตอนนี้เก็บผลรวมคำนำหน้าของสตริงเพื่อให้ผลรวมหลักของโมดูลคำนำหน้า 3 เป็น 0,1 หรือ 2 จากนั้นสตริงจะถูกวนซ้ำสำหรับตำแหน่งทั้งหมดของ i จากนั้นนับจำนวนสตริงย่อยที่ i ซึ่งหารด้วย 8 ลงตัว ตอนนี้ลบจำนวนสตริงย่อยที่ i ซึ่งหารด้วย 3 ลงตัวจากค่านี้
|ส| อาร์เรย์ 2D ขนาด X 3 ถูกกำหนด |S| คือขนาดของสตริง พูด dp[i][j].
ที่ดัชนีใด ๆ ฉัน dp[i][j] เริ่มจากดัชนี i ถึง 0 จำนวนสตริงย่อยมีเอาต์พุต j ดังนั้น 0<=j<=0 ตั้งแต่โมดูล 3
เราจำเป็นต้องวนซ้ำในสตริงเพื่อตรวจสอบว่าตัวเลขหนึ่งหลัก สองหลัก และสามหลักหารด้วย 8 หารด้วย 8 ได้หรือไม่
-
ตรวจสอบว่าอักขระเป็น 8 ที่ดัชนีหรือไม่ ให้ตรวจสอบตัวเลขที่ดัชนี
-
หารตัวเลขด้วย 8 แทนที่จะเป็น 3 หากมีตัวเลขสองหลัก
สมมติว่าจำนวนนั้นหารด้วย 8 ลงตัว ต้องมีสตริงย่อยสอง (1-3) หากหารด้วย 8 ลงตัว อย่างไรก็ตาม มันก็จะมีสตริงย่อยที่หารด้วย 8 ลงตัวเพื่อลบออก
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int count (char s[], int len) {
int cur = 0,
dig = 0;
int sum[MAX], dp[MAX][3];
memset (sum, 0, sizeof (sum));
memset (dp, 0, sizeof (dp));
dp[0][0] = 1;
for (int i = 1; i <= len; i++) {
dig = int (s[i - 1]) - 48;
cur += dig;
cur %= 3;
sum[i] = cur;
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 1][2];
dp[i][sum[i]]++;
}
int ans = 0, dprev = 0, value = 0, dprev2 = 0;
for (int i = 1; i <= len; i++) {
dig = int (s[i - 1]) - 48;
if (dig == 8) ans++;
if (i - 2 >= 0) {
dprev = int (s[i - 2]) - 48;
value = dprev * 10 + dig;
if ((value % 8 == 0) && (value % 3 != 0)) ans++;
}
// Taking 3 digit number.
if (i - 3 >= 0){
dprev2 = int (s[i - 3]) - 48;
dprev = int (s[i - 2]) - 48;
value = dprev2 * 100 + dprev * 10 + dig;
if (value % 8 != 0) continue;
ans += (i - 2);
ans -= (dp[i - 3][sum[i]]);
}
}
return ans;
}
int main () {
char str[] = "7675636788";
int len = strlen (str);
cout << count (str, len) << endl;
return 0;
} ผลลัพธ์
4
บทสรุป
ในปัญหานี้ เราได้เรียนรู้วิธีค้นหาจำนวนสตริงย่อยที่หารด้วย 8 ลงตัว ไม่ใช่ 3 ควบคู่ไปกับโค้ด c++ รหัสนี้ยังสามารถเขียนในภาษาจาวา ไพธอน และภาษาอื่นๆ ได้อีกด้วย ในการแก้ปัญหานี้ เราได้ย้อนกลับสตริงเพื่อค้นหาจำนวนสตริงย่อยที่หารด้วย 8 ลงตัวแต่หารด้วย 3 ไม่ลงตัว ซึ่งเป็นปัญหาที่ตรงไปตรงมามากเมื่อเราแบ่งออกเป็น 2 ส่วน
