家人們 我這次大概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]; } };``` -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 1.162.7.44 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1720325466.A.931

推 mrsonic: 你有甚麼用 07/07 12:15

→ oin1104: 幹你娘機掰 07/07 12:15

→ Rushia: 你好優秀 07/07 12:18

推 Furina: 我好崇拜你 07/07 12:18

推 smart0eddie: 大師 我聯註冊都忘記 07/07 12:26

推 dewaro: 包養開心結交知心異性友人。 07/07 12:26