我徽章沒了
下次再復仇
這次是題目太搞
faker也有版本不合的時候
你們給我等著
第一題
這兩個重複的數字
思路
建表遍歷後查詢
```cpp
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums)
{
vector<int> res;
int n = nums.size();
int paper[101] = {};
for(int i = 0 ; i < n ; i ++)
{
paper[nums[i]] ++;
}
for(int i = 0 ; i < 101 ; i ++)
{
if(paper[i] == 2)res.push_back(i);
}
return res;
}
};
```
第二題
給你a陣列有四個數字
要跟b陣列的很多數字
依照“順序”相乘之後 加起來
能得到的最大數字是多少
思路
用dp
紀錄上一層最大的同時更新新的可能
```cpp
class Solution {
public:
long long maxScore(vector<int>& a, vector<int>& b)
{
int an = a.size();
int bn = b.size();
vector<vector<long long>> paper(an,vector<long long> (bn , 0));
for(int j = 0 ; j < bn-3 ; j ++)
{
paper[0][j] = (long long)a[0] * (long long)b[j];
}
for(int i = 1 ; i < 4 ; i ++)
{
long long mv = paper[i-1][i-1];
for(int j = i ; j < bn-3+i ; j ++)
{
long long now = (long long)a[i] * (long long)b[j];
paper[i][j] = now + mv;
mv = max(paper[i-1][j],mv);
}
}
long long res = paper[3][3];
for(int i = 3 ; i < bn ; i ++)
{
res = max(res,paper[3][i]);
}
return res;
}
};
```
第三題
可以用words裡面的字的前綴
要用多少次才可以組合出target
思路
用set記錄
但是我超記憶體了
因為字太多
我吐了
```cpp
class Solution {
public:
int minValidStrings(vector<string>& words, string target)
{
unordered_set<string> save;
int n = target.size();
for(string k : words)
{
int len = k.size();
for(int i = 1 ; i <= len ; i ++)
{
save.insert(k.substr(0,i));
}
}
vector<int> paper(n+1,99999999);
paper[0] = 0;
for(int i = 0 ; i < n ; i ++)
{
for(int j = i ; j >= 0 ;j