0-9의 문자열이 제공됩니다. 이 문제의 경우 3이 아닌 8로 나눌 수 있는 문자열의 수를 계산해야 합니다. 이것은 2단계 문제이며 이를 해결하려면 한 번에 한 단계씩 코드를 수행해야 합니다. 예를 들면
입력
str = "80"
출력
2
입력
str = "7675636788"
출력
15
해결책을 찾기 위한 접근 방식
마지막 3자리의 숫자만 8의 배수이고 3의 배수인 자릿수의 합은 8의 배수입니다.
이제 접두사 모듈 3의 자릿수 합이 0,1 또는 2가 되도록 문자열의 접두사 합계를 저장합니다. 그런 다음 문자열은 i의 모든 위치에 대해 반복됩니다. 그런 다음 i에서 8로 나눌 수 있는 부분 문자열의 수를 계산합니다. 이제 이 값에서 3으로 나눌 수 있는 i에서 부분 문자열의 수를 뺍니다.
|에| X 3 크기의 2D 배열이 정의됨, |S| dp[i][j]와 같이 문자열의 크기입니다.
모든 인덱스에서 i dp[i][j]. 인덱스 i에서 시작하여 0까지 부분 문자열의 수는 출력 j를 갖습니다. 따라서 0<=j<=0, 모듈 3 이후입니다.
한 자리, 두 자리, 세 자리 숫자가 8로 나누어 떨어지는지 확인하기 위해 문자열을 반복해야 합니다.
-
인덱스에서 문자가 8인지 확인하려면 인덱스에서 숫자를 확인하십시오.
-
두 자리 숫자가 있는 경우 숫자를 3이 아닌 8로 나눕니다.
숫자를 8로 나눌 수 있다고 가정하겠습니다. 8로 나눌 수 있는 경우 2개의(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
결론
이번 문제에서는 C++ 코드와 함께 3이 아닌 8로 나눌 수 있는 부분 문자열의 수를 찾는 방법을 배웠습니다. 이 코드는 Java, python 및 기타 언어로도 작성할 수 있습니다. 이 문제를 해결하기 위해 문자열을 반대로 하여 8로 나눌 수 있지만 3으로 나눌 수 없는 부분 문자열의 수를 찾습니다. 두 부분으로 나누면 매우 간단한 문제입니다.