数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中能被8整除但不能被3整除的子串数量
给定一个0-9的字符串。对于这个问题，我们需要计算能被8整除但不能被3整除的字符串数量。这是一个两步问题，我们需要一步一步地编写代码来解决它，例如
输入
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<=2，因为模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++;
}
// 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整除的子串数量。一旦我们将它分成两部分，它就是一个非常直接的问题。
更新于：2022年3月7日
172 次浏览
广告