明天出門 所以今天先寫 這次6000名左右 前兩題太簡單 後兩題太難 第三題再給我10分鐘dedug我就寫出來了 我寫出來 就保底前500了 操機掰 第一題: 拿錢 沒得拿的人輸 思路: 照做 ```cpp class Solution { public: string losingPlayer(int x, int y) { int k = 0; while(1) { if(x>0 && y>3) { k++; x--; y-=4; } else { break; } } if(!(k&1))return "Bob"; return "Alice"; } };``` 第二題: 更改字串 有三個字的話可以削掉兩個字 最短的字串多短 思路: 照做 ```cpp class Solution { public: int minimumLength(string s) { int res=0; vector<int> save(26,0); for(char k : s) { save[k-'a']++; } for(int i = 0 ; i < 26 ; i ++) { while(save[i]>=3) { save[i]-=2; } } for(int i = 0 ; i < 26 ; i ++) { res += save[i]; } return res; } }; ``` 第三題: 給你一串數字 1,2,3,3,6,5 你可以把每個數字進行一次操作 改成0~k之間的次數 讓那個index = i的數字跟 倒數第i個數字 相差為X 請問要最少多少次操作 讓所有數字相差都是相差為X 思路: 先把數字分成n/2組 首先 要知道每組都有自己的 不用更改的相差值 要更改兩次的相差值 我稱呼 這是他的0,2 紀錄每種0,2 接下來要用陣列 每個格子的初始值是n/2 這是他的基礎更改值 接下來 因為有不用改的數字 跟要改的數字 對於2的值 接下來用prefix sum 在用來記錄的vector的k處 增加 對於0的值 就直接過去那邊-- 思路大概是這樣 要細講的話 很累 幹你娘機掰 我明明寫出來了 明明寫出來了 卻出了錯 因為我太急 沒有檢查好 錯了很白癡的地方 幹 ```cpp class Solution { public: int minChanges(vector<int>& nums, int k) { int n = nums.size(); int len = n / 2; unordered_map<int, int> zero; unordered_map<int, int> two; for (int i = 0; i < len; i++) { int ze = abs(nums[i] - nums[n-1-i]); int tw = max(k - min(nums[i], nums[n - 1 - i]), max(nums[i], nums[n - 1 - i])); zero[ze]++; if (tw < k) two[tw+1]++; } vector<int> prefix(k+1, 0); vector<int> paper(k+1, len); for (auto kv : two) { // cout << kv.first << "," << kv.second<<endl; prefix[kv.first] += kv.second; } // cout<<endl; for (auto kv : zero) { // cout << kv.first << "," << kv.second<<endl; paper[kv.first] -= kv.second; } int pre = 0; for (int i = 0 ; i <= k ; i++) { pre += prefix[i]; paper[i] += pre; // cout<<paper[i]<<" "; } // cout<<endl; int res = paper[0]; for (int i = 0; i <= k ; i++) { res = min(paper[i], res); } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 1.162.58.218 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1721494562.A.B49

推 sustainer123: 大師 07/21 00:56

→ RinNoKareshi: 大師 07/21 00:56

推 DJYOSHITAKA: 別捲了 07/21 01:01