第一题 1221. 分割平衡字符串
归纳法证明贪心
题目描述
解题报告
因为我不太会贪心（以前听y总讲课说贪心比较难，就战术性的逃避了贪心）。 这个题对于我而言，我首先想法的是一种模拟栈的玩法：
当扫描到R的时候，想象进栈，也就是top ++
当扫描到L的时候，想象出渣，也就是top --
当top又等于栈底(栈底规定为0吧)的时候，就是找到了一组符合要求的了
下面进入解法二，老老实实学贪心了，我现在也不会证明，先模仿宫水大大的吧，需要的友友们也可以直接看他的证明
宫水三叶の相信科学系列】归纳法证明从「最小分割点」进行分割可以得到最优解
先模拟出两种选择，一种局部最优，一种不是。
① 证明起始时（第一次分割）将「从 b 分割点将 s 断开」调整为「从 a 分割点将 s 断开」结果不会变差：
① 从 b点首次分割调整为从 a 点首次分割，两种分割形式分割点两端仍为合法 LR 子串，因此不会从有解变成无解；
② 从 b 分割后的剩余部分长度小于从 a 分割后的剩余部分，同时由 b 分割后的剩余部分会被由 a 分割后的剩余部分所严格覆盖，因此「对 a 分割的剩余部分再分割所得的子串数量」至少 与「从 b 点分割的剩余部分再分割所得的子串数量」相等（不会变少）。
到这里为止，证明了对于首次分割，将任意合格分割点调整为最小分割点，结果不会变得更差（当 a < b 时还会更好）。
继续使用归纳来模拟其他剩余合格LR字串，得到的结果也是一样的，因此，就证明了只要每一次都从最小分割点进行分割，就可以得到最优解
参考代码(C++版本)
解法①——常规模拟
class Solution { public: int balancedStringSplit(string s) { //扫一遍？ int len = s.size(); int top= 0,ans = 0; for(int i = 0; i < len;i++) { if(s[i] == 'R') top++; if(s[i] == 'L') top--; if(top == 0) ans ++; } return ans; } };
解法② —— 贪心
class Solution { public: int balancedStringSplit(string s) { int len = s.size(); int ans = 0; for(int i = 0; i < len;) { //其实本质也就是我模拟的代码，只是我模拟的时候就根据生活经验来的 int j = i+1; //遇到R就标记-1，遇到L就标记+1 int flag = (s[i] == 'L' ? 1 : -1); while(j < len && flag != 0) flag += (s[j++] == 'L'? 1 : -1); //匹配出一组0了，也即是找到局部最优了，调整起点，统计结果 i = j; ans ++; } return ans; } };
第二题 1827. 最少操作使数组递增
题目描述
解题报告
题目的意思是求解需要变换多少次，使数组中的每一个元素要比前一个元素大1，至于证明，现在能力微弱，后续补上吧
参考代码(C++版本)
class Solution { public: int minOperations(vector<int>& nums) { int len = nums.size(); int ans = 0; if(len == 1) return ans; for(int i = 1; i < len;i++) { if(nums[i-1] < nums[i]) continue; else { //统计前后相邻的两个数字需要加几次1才能够实现前一个比后一个大1 int tmp = nums[i-1] + 1 - nums[i]; ans += tmp; //更新较大数字的值 nums[i] = nums[i-1]+1; } } return ans; } };
第三题 2144. 打折购买糖果的最小开销
题目描述
解题报告
因为题目的要求是送咱的糖果只能是小于等于购买的两个糖果价格的 较小值 ，那么我们可以考虑降序排序，这种方便拿价格较大的两个糖果。
买两个，送一个，其实就可以看做是三个一组，比如拿样例来说，[3，2，1]的降序排序，买3和2 ，送1 ，那么这三个一组中，数组索引是2的糖果就送了，其他的样例也可以这种理解。
贪心的题，能够想出来吧，想证明了，还缺火候
参考代码(C++版本)
class Solution { public: int minimumCost(vector<int>& cost) { int len = cost.size(); int ans = 0; if(len == 1) return cost[0]; if(len == 2) return cost[0]+cost[1]; //三个一组，降序排序，拿到大的，两个，最后一个就可以送了 sort(cost.begin(),cost.end(),greater<int>()); for(int i = 0; i < len;i++) if(i % 3 == 2) continue; else ans += cost[i]; return ans; } };
第四题 1400. 构造 K 个回文字符串
哈希表(可用数组模拟，可用STL吧)+模拟
题目描述
解题报告
这个感觉更像是一个观察规律的题吧，因为题目要咱们构造，没有让咱们找出回文串，那么难度其实就降低很多了。
首先，出现频率是偶数的字母，是一定可以形成回文串的，它怎么放都可以。
但是出现频率是奇数的字母，它是没法匹配的，所以必须放在回文串的中间。
那么对于每一个出现频率为奇数的字母，都需要单独一个回文串来容纳它。我们只要保证，题目要求构造的回文串的数目k，比出现频率为奇数的字母的个数num大。
参考代码(C++版本)
class Solution { public: bool canConstruct(string s, int k) { int len = s.size(); if(len < k) return false; if(len == k) return true; //这个题是让咱们构造 //看到字符串的东西了，条件反射的去做映射吧 int cnt[26]; memset(cnt,0,sizeof(cnt)); for(int i = 0; i < len;i++) cnt[s[i]-'a'] ++; int num = 0; for(int i = 0; i < 26;i++) //记录出现次数为奇数的字母 if(cnt[i] % 2 == 1) num++; return num <= k; } };
