数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告