資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中陣列的還原
假設有一個程式用於列印陣列A的元素，但程式中存在一個小錯誤。該程式在每個元素後沒有空格，所以如果我們有一個列印的字串，我們能否重新生成陣列？我們知道陣列元素的範圍是1到k。
給定字串s和整數k。我們必須找到可以還原陣列的方法數量。答案可能非常大，所以返回它模10^9 + 7。
因此，如果輸入類似於S = "1318"且k = 2000，則輸出將為8，因為我們可以形成8個不同的陣列，例如[1318]，[131,8]，[13,18]，[1,318]，[1,3,18]，[1,31,8]，[13,1,8]，[1,3,1,8]
為了解決這個問題，我們將遵循以下步驟：
const int m = 1e9 + 7
定義一個map dp
定義一個函式add()，它將接收a, b,
返回((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'), k), ret)
dp[idx, num] := ret
返回ret
在主方法中執行以下操作：
n := s的大小
定義一個大小為n + 1的陣列ans
ans[0] := 1
s := 在s之前連線一個空格
ks := 將k轉換為字串
對於初始化i := 1，當i <= n，更新（i增加1），執行：
cnt := 1
temp := 空字串
對於初始化j := i，當j >= 1且cnt <= 10，更新（j減少1），（cnt增加1），執行：
temp := s[j] + temp
如果s[j]與'0'相同，則：
忽略以下部分，跳到下一次迭代
如果temp的大小 > ks的大小，則：
退出迴圈
val := temp作為數字
如果val >= 1且val <= k，則：
ans[i] := add(ans[i], ans[j - 1])
返回ans[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
328 次瀏覽
