ได้รับสตริงของตัวเลข 0-9 สำหรับปัญหานี้ เราต้องคำนวณจำนวนสตริงที่หาร 8 ลงตัว แต่ไม่หาร 3 ลงตัว นี่เป็นปัญหา 2 ขั้นตอน เราต้องเขียนโค้ดทีละขั้นตอนเพื่อแก้ปัญหา เช่น
ข้อมูลนำเข้า
str = "80"
ข้อมูลส่งออก
2
ข้อมูลนำเข้า
str = "7675636788"
ข้อมูลส่งออก
15
แนวทางการหาคำตอบ
เฉพาะตัวเลขที่ 3 หลักสุดท้ายหาร 8 ลงตัว และผลรวมตัวเลขหาร 3 ลงตัว จึงหาร 8 ลงตัวได้
ตอนนี้เก็บ prefix sum ของสตริงไว้ เพื่อให้ผลรวมตัวเลขของ prefix modulo 3 เป็น 0, 1, หรือ 2 จากนั้นวนลูปสตริงสำหรับตำแหน่ง i ทั้งหมด นับจำนวนสตริงย่อยที่ตำแหน่ง i ที่หาร 8 ลงตัว — ลบด้วยจำนวนสตริงย่อยที่ตำแหน่ง i ที่หาร 3 ลงตัว จากค่านี้
กำหนดอาร์เรย์ 2 มิติขนาด |S| X 3 โดย |S| คือขนาดของสตริง ให้เป็น dp[i][j]
ที่ดัชนี i ใดๆ dp[i][j] เริ่มจากดัชนี i ถึง 0 จำนวนสตริงย่อยที่มีผลลัพธ์ j ดังนั้น 0<=j<=0 เนื่องจาก modulo 3
เราต้องวนลูปสตริงเพื่อตรวจสอบว่าตัวเลข 1 หลัก, 2 หลัก, และ 3 หลัก หาร 8 ลงตัวหรือไม่
- เพื่อตรวจสอบว่าตัวอักษรที่ดัชนีเป็น 8 ให้ตรวจสอบตัวเลขที่ดัชนีนั้น
- หารตัวเลขด้วย 8 แทนที่จะเป็น 3 หากมี 2 หลัก
สมมติว่าตัวเลขหาร 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++ โค้ดนี้สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ ในการแก้ปัญหานี้ เราได้กลับสตริงเพื่อหาจำนวนสตริงย่อยที่หาร 8 ลงตัวแต่ไม่หาร 3 ลงตัว เป็นปัญหาที่ตรงไปตรงมามากเมื่อแบ่งเป็น 2 ส่วน
