专业模板建站软件,深圳企业专业网站设计,友链通,百度公司推广LeetCode第 227 场周赛题解
检查数组是否经排序和轮转得到
原题链接
https://leetcode-cn.com/problems/check-if-array-is-sorted-and-rotated/
解题思路
直接进行测试就行#xff0c;因为数组的数据范围很小#xff0c;直接进行O(N2#xff09;O(N^2#xff09;O(…LeetCode第 227 场周赛题解
检查数组是否经排序和轮转得到
原题链接
https://leetcode-cn.com/problems/check-if-array-is-sorted-and-rotated/
解题思路
直接进行测试就行因为数组的数据范围很小直接进行O(N2O(N^2O(N2算法即可注意数组下标的求余
AC代码
class Solution {
public:bool Check(vectorint a, vectorint 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(vectorint nums) {vectorint tmp nums;sort(tmp.begin(), tmp.end()); // 记得先排个序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/
解题思路
首先贪心的来讲每一次操作为了保证最终得分最高都会取当前最大和次最大因为数据范围不大也可以直接进行模拟.
首先对,a, b, c进行排序保证a≤b≤ca\leq b\leq ca≤b≤c最大值c和次最大值a进行操作直到ababab重复进行上述两个操作直到a,b,ca, b, ca,b,c至少∃\exists∃两个零 下面是一种更为优秀的解法 从不同堆石子中各取出一个加一分也就是说在遵循该规则的情况下剩余的石子最少即可。倘若ab≤ca b \leq cab≤c分数最高为aba bab因为ccc堆石子中肯定会剩下的最多取出的成对石子为ababab倘若ab≥ca b \geq cab≥c那么肯定有一种方法可以使得a,b,ca, b, ca,b,c的绝对值最大差为111也就是说abcabcabc或abc−1abc-1abc−1形成这种局面之后我们可以通过每次取最大值和次最大值依旧可以使得差的绝对值位置在111之内。那么最后剩余的局面为(0,0,0);(0,0,1),(0,1,1)(0, 0, 0); (0, 0, 1), (0, 1, 1)(0,0,0);(0,0,1),(0,1,1)。其中(0,1,1)⇒(0,0,0)(0, 1, 1) \Rightarrow(0, 0, 0)(0,1,1)⇒(0,0,0)。最终结论可得为 resabc/2res abc/ 2resabc/2
AC代码
模拟解法
class Solution {
public:int maximumScore(int a, int b, int c) {vectorint 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;}
};构造字典序最大的合并字符串
原题链接
https://leetcode-cn.com/problems/largest-merge-of-two-strings/ 解题思路
思路介绍
首先看数据范围O(N2)O(N^2)O(N2)算法即可 对于两个字符串word1,word2word1, word2word1,word2关键在于判断谁的当前首字符用于操作放在mergemergemerge串的末尾
倘若Firstword1First_{word1}Firstword1为空word1已经被选完当然是选择word2word2word2首字符倘若Firstword2First_{word2}Firstword2为空word2已经被选完当然是选择word1word1word1首字符倘若Firstword1Firstword2First_{word1} First_{word2}Firstword1Firstword2那么当然是选择word1word1word1首字符同理倘若Firstword1Firstword2First_{word1} First_{word2}Firstword1Firstword2那么当然是选择word2word2word2首字符倘若Firstword1Firstword2First_{word1} First_{word2}Firstword1Firstword2那我们需要递归比较下面的字符。
思路证明 具体操作看下面的代码
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;}
};最接近目标值的子序列和
原题链接
https://leetcode-cn.com/problems/closest-subsequence-sum/
解题思路
首先我们观察数据范围发现num.length≤40num.length \leq 40num.length≤40很有可能使用dfsdfsdfs但是在观察题目暴力的情况是无法剪枝的考虑一下将其进行一半分开dfsdfsdfs前一半dfsdfsdfs后一半然后进行将dfs结果排序去重后进行二分使其更加接近于goalgoalgoal
AC代码
vectorint 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(vectorint 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){// 对于每一个元素两次二分操作答案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;}
};小结
int d[] {a, b, c}; 挺好使的证明的时候反证法加上调整法直接整挺好
参考
部分证明参考y总讲解链接如下https://space.bilibili.com/7836741?fromsearchseid1124809430476024150
