資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告