五月集训（第4天）——贪心

前言

内容出自：
《英雄算法联盟：算法集训》
每天四道题，逐步掌握算法为己用！

一.解题思路

1221. 分割平衡字符串
题目描述：

在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

返回可以通过分割得到的平衡字符串的 最大数量 。

解题思路：
这道题实质上就是’L’,'R’配对问题（括号配对），可以简单模拟栈操作来进行模拟。

1827. 最少操作使数组递增
题目描述：

给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。

比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。 请你返回使 nums
严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] <
nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

解题思路：
从1开始到数组中最后一个数开始遍历，若nums[i] <= nums[i-1]则说明nums[i]需要num[i-1]-num[i]+1个1，将其用计数器记录下来，并将nums[i-1]+1赋值给nums[i]。

2144. 打折购买糖果的最小开销
题目描述：

一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。

免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。

比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1
的糖果，但不能获得价格为 4 的糖果。 给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i
个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。

解题思路：
将价格数组排序，由高到低遍历，将价格加入到计数器中，每三个下标跳过一次相加。

1400. 构造 K 个回文字符串
题目描述：

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

解题思路：
字符串s可构造的回文串数量为[left,right]；
right显而易见为s的字符串长度，也就是说每个字符作为一个回文串；
left的求解需要观察字符串的规律，对以一个回文串，可以分为两种"aabcc"和"abccba"，通过观察可知如果 s 中有 p 个字符出现了奇数次，qq个字符出现了偶数次，那么 s 最少可以构造的回文串个数就为 p，这是因为每一种出现了奇数次的字符都必须放在不同的回文串中。特别地，如果 p=0，那么最少构造的回文串个数为 1。
由此我们可以确定left为max(p,1);
最后只需要判断k是否在区间[left,right]之内即可。

二.代码以及结果

1.代码：

class Solution {    public int balancedStringSplit(String s) { int num = 0; int n = 0; for(int i = 0;i < s.length();i++){     if(s.charAt(i) == 'L'){  n++;     }else if(s.charAt(i) == 'R'){  n--;     }     if(n == 0){  num++;     } } return num;    }}

结果：

2.代码：

class Solution {    public int minOperations(int[] nums) { int count = 0; for(int i = 1;i < nums.length;i++){     if(nums[i] <= nums[i-1]){  count += nums[i-1] - nums[i] + 1;  nums[i] = nums[i-1] + 1;     } } return count;    }}

结果：

3.代码：

class Solution {    public int minimumCost(int[] cost) { Arrays.sort(cost); int count = 0,n = 0; for(int i = cost.length - 1;i >= 0;i--){     n++;     if(n == 3){  n = 0;  continue;     }     count += cost[i]; } return count;    }}

结果：

4.代码：

class Solution {    public boolean canConstruct(String s, int k) { if(s.length() == k){     return true; }else if(s.length() < k){     return false; } int[] hash = new int[26]; char[] index = s.toCharArray(); int count = 0; for(char x : index){     hash[x-'a']++; } for(int i : hash){     if(i % 2 == 1){  count++;     } } int left = Math.max(count,1); return left <= k && s.length() >= k;    }}

结果：

总结

贪心算法主要考察的是我们的思维能力，如何求得局部最优解，这个能力只能靠做题锻炼自己的逻辑思维能力才能提升。
今天是第四天，继续加油！！！