家人們
我這次大概5000名
沒救了
下輩子再一起拿徽章
※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
:
: 第一題
: 給你一個字串s和數字k 把所有的s字串替換成他的索引+k，索引越界就從左邊繼續走。
```cpp
class Solution {
public:
string getEncryptedString(string s, int k)
{
int len = s.size();
string res;
for(int i = 0 ; i < len ; i ++)
{
res.push_back(s[(i+k)%len]);
}
return res;
}
};
```
: 第二題
: n才10，直接用回溯法窮舉二進制字串，然後把符合條件的加入結果集。
:
要弄出長度為n的bot串
然後0不能相鄰
思路
寫一寫 幹你娘好麻煩
丟給gpt 過
```cpp
class Solution {
public:
unordered_set<string> save;
void find(string k, int pos)
{
int len = k.size();
for (int i = pos; i < len; i++)
{
if (k[i] == '0') continue;
if ((i > 0 && k[i - 1] == '0') || (i < len - 1 && k[i + 1] == '0'))
continue;
k[i] = '0';
if (save.find(k) == save.end()) {
save.insert(k);
find(k, i + 1);
}
k[i] = '1';
}
}
vector<string> validStrings(int n)
{
string pre(n,'1');
if(n == 1)return {"1","0"};
find(pre, 0);
save.insert(pre);
vector<string> res(save.begin(), save.end());
return res;
}
};
```
: 第三題
: 簡單dp，因為起始點在左上所以一列一列的掃就好。
:
多少個包含grid最左上角的子矩陣
xy數量一樣
思路
這算前綴和還是dp
反正加起來看就好
```cpp
class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid)
{
int res = 0;
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> xcount(n,vector<int>(m,0));
vector<vector<int>> ycount(n,vector<int>(m,0));
if(grid[0][0] == 'X')xcount[0][0] =1;
if(grid[0][0] == 'Y')ycount[0][0] =1;
for(int i = 1 ; i < m ; i ++)
{
xcount[0][i] += xcount[0][i-1];
if(grid[0][i]=='X')xcount[0][i]++;
ycount[0][i] += ycount[0][i-1];
if(grid[0][i]=='Y')ycount[0][i]++;
}
for(int i = 1 ; i < n ; i ++)
{
xcount[i][0] += xcount[i-1][0];
if(grid[i][0]=='X')xcount[i][0]++;
ycount[i][0] += ycount[i-1][0];
if(grid[i][0]=='Y')ycount[i][0]++;
}
for(int i = 1 ; i < n ; i ++)
{
for(int j = 1 ; j < m ; j ++)
{
xcount[i][j] += xcount[i-1][j];
xcount[i][j] += xcount[i][j-1];
xcount[i][j] -= xcount[i-1][j-1];
if(grid[i][j]=='X')xcount[i][j]++;
ycount[i][j] += ycount[i-1][j];
ycount[i][j] += ycount[i][j-1];
ycount[i][j] -= ycount[i-1][j-1];
if(grid[i][j]=='Y')ycount[i][j]++;
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
if(xcount[i][j] > 0)
{
if(xcount[i][j]==ycount[i][j])res++;
}
}
}
return res;
}
};
```
: 第四題
: 我看了一下感覺是dp 然後看看測資大小我選擇死亡
: 遇到困難睡大覺
:
給你一堆小字串
跟他們的cost
要用最少的錢組合出大字串
思路
先找到位子然後紀錄然後dp
然後我TLE + MLE
漬鯊
這題聽我朋友說
確實是記錄後dp
但是要用字典樹來記錄才可以
幹你娘
我又沒學過字典樹
狗屎爛題目
```cpp
class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs)
{
int tlen = target.size();
int len = words.size();
unordered_map<int, vector<pair<int,int>>> save;
for(int i = 0 ; i < len ; i ++)
{
int po = target.find(words[i]);
while(po != std::string::npos)
{
save[po].push_back({costs[i], po + words[i].size()});
po = target.find(words[i], po + 1);
}
}
vector<int> paper(tlen+1,INT_MAX);
paper[0]=0;
for(int i = 0 ; i < tlen+1 ; i ++)
{
if(paper[i] == INT_MAX) continue;
for(auto& k : save[i])
{
if(k.second <= tlen)
{
paper[k.second] = min(paper[k.second], paper[i] + k.first);
}
}
}
if(paper[tlen] == INT_MAX)return -1;
return paper[tlen];
}
};```