배열 A의 배열 요소를 인쇄하는 데 사용되는 프로그램이 있지만 프로그램에 약간의 실수가 있다고 가정합니다. 그 프로그램에서 각 요소 뒤에 공백이 없었습니다. 그래서 우리가 하나의 인쇄된 문자열을 가지고 있다면, 배열을 다시 생성할 수 있습니까? 배열 요소가 1에서 k 범위에 있다는 것을 알고 있습니다.
문자열 s와 정수 k가 주어집니다. 어레이를 복원할 수 있는 방법의 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 S ="1318" 및 k =2000과 같으면 출력은 8이 됩니다. [1318], [131,8], [13,18],[1,318과 같은 8개의 다른 배열을 형성할 수 있기 때문입니다. ],[1,3,18],[1,31,8],[13,1,8],[1,3,1,8]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
상수 정수 m =1e9 + 7
-
하나의 맵 dp 정의
-
add() 함수를 정의하면, b,
-
return ((a mod m) + (b mod m)) mod m
-
help() 함수를 정의하면 idx, s, num, k,
가 필요합니다. -
idx>=크기가 s이면 -
-
1 반환
-
-
idx가 dp에 있고 num이 dp[idx]에 있으면 -
-
반환 dp[idx, num]
-
-
ret :=0
-
num>=1이고 num>=k이고 s[idx]가 '0'과 같지 않으면 -
-
ret :=add(help(idx, s, 0, k), ret)
-
-
num * 10 + (s[idx] - '0') <=k이면 -
-
ret :=add(help(idx + 1, s, num * 10 + (s[idx] - '0'의 ASCII), k), ret)
-
-
dp[idx, num] :=ret
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
n :=s
의 크기 -
크기가 n + 1인 배열을 정의하십시오.
-
답변[0] :=1
-
s :=s 앞에 공백 하나 연결
-
ks :=k를 문자열로 변환
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
cnt :=1
-
temp :=빈 문자열
-
j>=1 및 cnt <=10일 때 j>=1 및 cnt <=10일 때 초기화 j :=i에 대해 업데이트(j를 1만큼 감소), (cnt를 1만큼 증가) 다음을 수행합니다. -
-
온도 :=s[j] + 온도
-
s[j]가 '0'과 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
temp 크기> ks 크기이면 -
-
루프에서 나오세요
-
-
val :=숫자로 나타낸 온도
-
val>=1이고 val <=k이면 -
-
ans[i] :=add(ans[i], ans[j - 1])
-
-
-
-
반환 [n]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
unordered_map<int, unordered_map<lli, int> > dp;
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int help(int idx, string& s, lli num, int k){
if (idx >= s.size())
return 1;
if (dp.count(idx) && dp[idx].count(num))
return dp[idx][num];
int ret = 0;
if (num >= 1 && num <= k && s[idx] != '0') {
ret = add(help(idx, s, 0, k), ret);
}
if (num * 10 + (s[idx] - '0') <= k) {
ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
ret);
}
return dp[idx][num] = ret;
}
int numberOfArrays(string s, int k){
int n = s.size();
vector<lli> ans(n + 1);
ans[0] = 1;
s = " " + s;
string ks = to_string(k);
for (lli i = 1; i <= n; i++) {
lli cnt = 1;
string temp = "";
for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
temp = s[j] + temp;
if (s[j] == '0')
continue;
if (temp.size() > ks.size())
break;
lli val = stol(temp);
if (val >= 1 && val <= k) {
ans[i] = add(ans[i], ans[j - 1]);
}
}
}
return ans[n];
}
};
main(){
Solution ob;
cout << (ob.numberOfArrays("1318",2000));
} 입력
"1318", 2000
출력
8