LeetCode第 227 場(chǎng)周賽題解

檢查數(shù)組是否經(jīng)排序和輪轉(zhuǎn)得到

原題鏈接

https://leetcode-cn.com/problems/check-if-array-is-sorted-and-rotated/

解題思路

直接進(jìn)行測(cè)試就行，因?yàn)閿?shù)組的數(shù)據(jù)范圍很小，直接進(jìn)行$O(N^2）$算法即可，注意數(shù)組下標(biāo)的求余

AC代碼

class Solution { public:bool Check(vector<int> a, vector<int> b, int k){for (int i = 0; i < a.size(); i ++ ){static int u, v;if (i + k < a.size()) u = a[i + k];else u = a[(i + k) % a.size()];v = b[i];if(u != v)return false;}return true;}bool check(vector<int>& nums) {vector<int> tmp = nums;sort(tmp.begin(), tmp.end()); // 記得先排個(gè)序for (int i = 0; i < tmp.size(); i ++ ){if (Check(tmp, nums, i))return true;}return false;} };

移除石子的最大得分

原題鏈接

https://leetcode-cn.com/problems/maximum-score-from-removing-stones/

解題思路

首先，貪心的來(lái)講，每一次操作為了保證最終得分最高，都會(huì)取當(dāng)前最大和次最大，因?yàn)閿?shù)據(jù)范圍不大，也可以直接進(jìn)行模擬.

• 首先對(duì),a, b, c進(jìn)行排序，保證$a\le b\le c$
• 最大值c和次最大值a進(jìn)行操作，直到$a=b$
• 重復(fù)進(jìn)行上述兩個(gè)操作，直到$a,b,c$至少$?$兩個(gè)零
  下面是一種更為優(yōu)秀的解法
  從不同堆石子中各取出一個(gè)，加一分，也就是說(shuō)在遵循該規(guī)則的情況下，剩余的石子最少即可。
• 倘若$a+b\le c$，分?jǐn)?shù)最高為$a+b$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$c$堆石子中肯定會(huì)剩下的，最多取出的成對(duì)石子為$a+b$
• 倘若$a+b\ge c$，那么肯定有一種方法，可以使得$a,b,c$的絕對(duì)值最大差為$1$，也就是說(shuō)$a=b=c$或$a=b=c?1$，形成這種局面之后，我們可以通過(guò)每次取最大值和次最大值，依舊可以使得差的絕對(duì)值位置在$1$之內(nèi)。那么最后剩余的局面為$(0,0,0);(0,0,1),(0,1,1)$。其中$(0,1,1)?(0,0,0)$。最終結(jié)論可得為 $res=（a+b+c）/2$

AC代碼

模擬解法

class Solution { public:int maximumScore(int a, int b, int c) {vector<int> t; t.push_back(a);t.push_back(b), t.push_back(c);sort(t.begin(), t.end());if (t[2] >= t[0] + t[1])return t[0] + t[1];else{int ans = 0;int tmp;tmp = t[1] - t[0];ans += tmp;t[1] -= tmp; t[2] -= tmp;while (true){sort(t.begin(), t.end());if (t[0] == 0 && t[1] == 0) break;tmp = t[1] - t[0];if (tmp == 0) // a = b && a >= 1 && b >= 1{if (t[2] >= 2){ans += 2;t[2] -= 2, t[1] -= 1, t[0] -= 1;}else // a = 1, b = 1, c = 1{ans += 1;break;}}else // b > a直接取到 b = a{tmp = t[1] - t[0];ans += tmp;t[1] -= tmp; t[2] -= tmp;}}return ans;}} };

---

線性解法

class Solution { public:int maximumScore(int a, int b, int c) {int d[] = {a, b, c};sort(d, d + 3);if (d[0] + d[1] <= d[2]) return d[0] + d[1];else return (d[0] + d[1] + d[2]) / 2;} };

構(gòu)造字典序最大的合并字符串

原題鏈接

https://leetcode-cn.com/problems/largest-merge-of-two-strings/

解題思路

思路介紹

首先看數(shù)據(jù)范圍，$O(N^2)$算法即可
對(duì)于兩個(gè)字符串$word1,word2$，關(guān)鍵在于判斷誰(shuí)的當(dāng)前首字符用于操作，放在$merge$串的末尾

• 倘若$Firs{t}_{word1}$為空（word1已經(jīng)被選完），當(dāng)然是選擇$word2$首字符
• 倘若$Firs{t}_{word2}$為空（word2已經(jīng)被選完），當(dāng)然是選擇$word1$首字符
• 倘若$Firs{t}_{word1}>Firs{t}_{word2}$那么，當(dāng)然是選擇$word1$首字符
• 同理，倘若$Firs{t}_{word1}<Firs{t}_{word2}$那么，當(dāng)然是選擇$word2$首字符
• 倘若$Firs{t}_{word1}=Firs{t}_{word2}$，那我們需要遞歸比較下面的字符。

思路證明

具體操作看下面的代碼

AC代碼

class Solution { public:bool Check(string &word1, string &word2, int pre, int nxt){if (pre == word1.size()) return false;else if (nxt == word2.size()) return true;if (word1[pre] > word2[nxt]) return true;else if (word1[pre] < word2[nxt]) return false;else return Check(word1, word2, pre + 1, nxt + 1);}string largestMerge(string word1, string word2) {string ret = "";int pre = 0, nxt = 0;while (pre < word1.size() || nxt < word2.size()){if (Check(word1, word2, pre, nxt)){ret += word1[pre];pre ++;}else{ret += word2[nxt];nxt ++;}}return ret;} };

最接近目標(biāo)值的子序列和

原題鏈接

https://leetcode-cn.com/problems/closest-subsequence-sum/

解題思路

首先，我們觀察數(shù)據(jù)范圍，發(fā)現(xiàn)$num.length\le 40$很有可能使用$dfs$，但是在觀察題目，暴力的情況是無(wú)法剪枝的，考慮一下將其進(jìn)行一半分開，$dfs$前一半，$dfs$后一半，然后進(jìn)行將dfs結(jié)果排序去重后進(jìn)行二分，使其更加接近于$goal$

AC代碼

vector<int> ved1, ved2, num1, num2; int sum = 0; class Solution { public:void dfs1(int cur) // dfs num1部分{if (cur >= num1.size()){return;}sum += num1[cur]; // 選ved1.push_back(sum); // 放入dfs1(cur + 1);sum -= num1[cur]; // 不選dfs1(cur + 1);}void dfs2(int cur) // dfs num2部分{if (cur >= num2.size()){return;}sum += num2[cur];ved2.push_back(sum);dfs2(cur + 1);sum -= num2[cur];dfs2(cur + 1);}int minAbsDifference(vector<int>& nums, int goal) {int n = nums.size();num1.clear(), num2.clear(), ved1.clear(), ved2.clear();ved1.push_back(0);ved2.push_back(0);for (int i = 0; i < n / 2; i ++ ) num1.push_back(nums[i]);for (int i = n / 2; i < n; i ++ ) num2.push_back(nums[i]);// dfssum = 0; dfs1(0);sum = 0; dfs2(0);// 排序去重sort(ved1.begin(), ved1.end());ved1.erase(unique(ved1.begin(), ved1.end()), ved1.end());sort(ved2.begin(), ved2.end());ved2.erase(unique(ved2.begin(), ved2.end()), ved2.end());/*for (auto i : ved1) cout << i << " "; cout << endl;for (auto i : ved2) cout << i << " "; cout << endl;*/int l, r, mid, k;int res = 0x3f3f3f3f;for (auto x : ved1){// 對(duì)于每一個(gè)元素兩次二分操作答案l = 0, r = ved2.size() - 1;k = goal - x;// x + y >= goal --> y >= goal - x (min)if (ved2[r] >= k){while (l < r){mid = l + r >> 1;if (ved2[mid] >= k){r = mid;}else{l = mid + 1;}}res = min(res, abs(x + ved2[l] - goal));}// x + y <= goal --> y <= goal - x (max)l = 0, r = ved2.size() - 1;if (ved2[l] <= k){while (l < r){mid = l + r + 1 >> 1;if (ved2[mid] <= k){l = mid;}else{r = mid - 1;}}res = min(res, abs(x + ved2[l] - goal));}if (res == 0) break;}return res;} };

小結(jié)

• int d[] = {a, b, c}; 挺好使的
• 證明的時(shí)候反證法加上調(diào)整法，直接整挺好

參考

• 部分證明參考y總講解，鏈接如下
• https://space.bilibili.com/7836741?from=search&seid=1124809430476024150

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode第 227 场周赛题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。