在 C++ 中可被 8 整除且不能被 3 整除的子字符串数
给出一个 0-9 的字符串。对于这个问题，我们需要计算能被 8 整除而不被 3 整除的字符串的数量。这是一个 2 步问题，我们需要一次执行代码来解决它，例如
输入
str = "80"
输出
2
输入
str = "7675636788"
输出
15
寻找解决方案的方法
只有后三位数字能被 8 整除，能被 3 整除的数字之和也能被 8 整除。
现在存储字符串的前缀和，使得前缀模块 3 的数字和为 0,1 或 2。然后针对 i 的所有位置迭代字符串。然后计算 i 处可被 8 整除的子串数量——现在，从该值中减去 i 处可被 3 整除的子串数量。
|S| 定义 X 3 大小的二维数组，|S| 是字符串的大小，例如 dp[i][j]。
在任何索引 i dp[i][j]。从索引 i 到 0，子串的数量有输出 j。所以 0<=j<=0，从模块 3 开始。
我们需要遍历字符串以检查一位数、两位数和三位数是否可以被 8 整除。
要确定一个字符在索引处是否为 8，请检查索引处的数字。
如果有两位数，则将数字除以 8 而不是 3。
让我们假设该数字可以被 8 整除。如果它可以被 8 整除，则必须有两个 (1-3) 子字符串。但是，它也将具有可以被 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++;
}
//取 3 位数字。
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 整除的子串的数量。将其分成两部分，这是一个非常简单的问题。
以上是 在 C++ 中可被 8 整除且不能被 3 整除的子字符串数 的全部内容， 来源链接： utcz.com/z/297243.html
