資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中整數字符串中可被 6 整除的子字串數量
我們將研究一個問題，在這個問題中，我們給定一個整數字符串，並且必須確定有多少個子字串在整數格式下可以被 6 整除。需要注意的是，輸入是以數字（整數）組成的字串的形式。但是，可整除性檢查將僅考慮它作為一個整數（不使用字串輸入的 ASCII 值）。
輸入
str = “648”
解釋
子字串“6”、“48”和“648”可以被 6 整除。
輸入
str = “38342”
輸出
4
解釋
子字串“3834”、“342”、“834”和“42”可以被 6 整除。
暴力方法
使用者可以檢查每個可能的子字串，以檢視它是否可以被 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
有效方法
為了使一個數可以被 6 整除，該數的最後一位數字必須可以被 2 整除。數字的總和必須是 3。透過跟蹤之前計算的答案，我們可以使用動態規劃來發現解決方案。
令 f(i,s) - 從第 i 個索引開始的字串數量，其數字和模 3 等於 s，這給出了 Σin-1 f(i,0)。
令 a 為字串的第 i 位數字；現在，從 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 等。我們希望您覺得本課很有用。
更新於： 2022-03-07
270 次瀏覽
廣告