LeetCode刷题之贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法基本思路
- 建立数学模型来描述问题
- 把求解的问题分成若干个子问题
- 对每个子问题求解，得到子问题的局部最优解
- 把子问题的解局部最优解合成原来问题的一个解
1221. 分割平衡字符串
在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。
示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
题解：
class Solution {
public int balancedStringSplit(String s) {
String restStr = s;
ArrayList<String> list = new ArrayList<>();
while (restStr.length()>0) {
restStr = getPinghengStr(restStr)[1]; //获取剩余字符串循环处理
list.add(getPinghengStr(restStr)[0]); //存储各个生成的平衡字符串
}
return list.size();
}
/**
* 传入一个字符串，截取平衡字符串，同时返回剩余字符串
* @param str
* @return
*/
private String[] getPinghengStr(String str) {
String jugeStr;
for (int i=1;i<str.length();i++) {
jugeStr = str.substring(0, i);
//判断R和L出现的次数是否相等
int rCount = 0; //R出现的次数
int lCount = 0; //L出现的次数
for (int j=0;j<jugeStr.length();j++) {
if (jugeStr.charAt(j) == 'R') {
rCount++;
} else if (jugeStr.charAt(j) == 'L') {
lCount++;
}
}
if (rCount == lCount) {
//判断是平衡字符串，返回结果
return new String[]{jugeStr, str.substring(i)};
} else {
//继续循环加长字符判断
continue;
}
}
return new String[]{"", ""};
}
}
944. 删列造序
给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。
你需要选出一组要删掉的列 D，对 A 执行删除操作，使 A 中剩余的每一列都是 非降序 排列的，然后请你返回 D.length 的最小可能值。
删除 操作的定义是：选出一组要删掉的列，删去 A 中对应列中的所有字符，形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。（可以参见 删除操作范例）
示例 1：
输入：["cba", "daf", "ghi"]
输出：1
解释：
当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。
题解：
class Solution {
/**
* 思路：
* 将字符串数组排成字符矩阵，
* 需要满足的条件是每一列从上到下需要按照字母顺序排列，如果不是字母顺序，就记录该列
* 返回记录的列数
* @param A
* @return
*/
public int minDeletionSize(String[] A) {
int count = 0;
a: for (int c=0;c<A[0].length();c++) { //列数 colum
for (int r=1;r<A.length;r++) { //行数 row
//将第j行i列和j-1行i列字符对比，同列后一个字符比前一个小，则不符合规则，该列c需要被删除
if (A[r].charAt(c)<A[r-1].charAt(c)) {
//不满足条件，记录该列
count++;
continue a;
}
}
}
return count;
}
}
1403. 非递增顺序的最小子序列
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例 1：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
题解：
class Solution {
/**
* 思路：
* 1.对nums数组进行从小到大排序
* 2.遍历从nums中从尾端依次取出数到sublist集合中，如果sublist中数的和大于剩余数的和，则返回该sublist，否则继续取数
* @param nums
* @return
*/
public List<Integer> minSubsequence(int[] nums) {
List<Integer> subList = new ArrayList<>(); //抽出来的子序列
Arrays.sort(nums); //对nums排序
int total = 0; //计算nums数组的总大小
int subNum = 0; //计算抽出来数的和的值
for (int num : nums) {
total += num;
}
for (int i=nums.length-1;i>=0;i--) {
//从最后一个数开始抽取
subList.add(nums[i]);
subNum += nums[i];
if (subNum > total/2) {
//判断抽出的数的和是否比剩下的数的和大
return subList;
}
}
return subList;
}
}
1518. 换酒问题
小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
请你计算 最多 能喝到多少瓶酒。
示例 1：
输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
题解：
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
//把现有买来的酒喝完
int drinkCount = numBottles; //现有喝酒数量
int bottleCount = numBottles; //手里现有酒瓶数量
//开始兑换，判断空瓶数量是否大于等于numExchange
while (bottleCount >= numExchange) {
int curExchangeCount = bottleCount/numExchange; //本次换酒数量
//计算是否有剩余换不了的几个酒瓶 restBottleCount<numExchange
int restBottleCount = bottleCount%numExchange;
drinkCount += curExchangeCount; //把酒喝掉，喝过的酒累加上本次换酒的数量
bottleCount = curExchangeCount + restBottleCount; //然后换来的酒瓶+剩余不够换一瓶酒的酒瓶就是现有的空瓶数量
}
return drinkCount;
}
}
