贪心算法
贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法没有模板可以套用，感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
力扣题目
455.分发饼干
力扣题目链接
本题一上手就两层for循环解决战斗。不对，你就没有理解题意。
题目的目标是尽可能多的满足数量多的孩子，换句话说就是大饼干给胃口大的孩子，小饼干给胃口小的孩子。
局部最优解就是大饼干喂给大胃口孩子（或者小饼干喂给小胃口），那么全局最优解就是满足尽可能多的小孩。
题解
//第一种：小饼干喂胃口小的孩子class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int index = 0; //孩子的指针for (int i = 0; i < s.length && index < g.length; i++) {if (s[i] >= g[index]) {count++;index++;//当前孩子吃饱了换下一个孩子}}return count;}}
//大饼干给胃口大的孩子class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int index = s.length - 1; //饼干的指针for (int i = g.length - 1; i >= 0 && index >= 0; i--) {if (s[index] >= g[i]) {count++;index--;}}return count;}}
376. 摆动序列
力扣题目链接
易错点：
- 仅有一个元素或者含两个不等元素的序列也视作摆动序列。
最开始元素之差为0的话应该如何处理。（这点一开始没有考虑进去）
题解
class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length < 2) return nums.length;int previous = nums[1] - nums[0];int count = previous != 0 ? 2 : 1;for (int i = 2; i < nums.length; i++) {int current = nums[i] - nums[i - 1];if ((current > 0 && previous <= 0) || (current < 0 && previous >= 0)) {count += 1;previous = current;}}return count;}}
53. 最大子序和
力扣题目链接
用暴力解法试了一下会超时。如何把遍历过程中的当前最大值保存下来。
class Solution {public int maxSubArray(int[] nums) {int res = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) { //设置起始位置int temp = 0;for (int j = i; j < nums.length; j++) { //每次从起始位置i开始遍历temp += nums[j];res = temp > res ? temp : res;}}return res;}}
题解
每一步计算中如果当前和count为负数，那么就将当前和count清零，从下一个元素重新开始计算。
class Solution {public int maxSubArray(int[] nums) {if (nums.length == 1){return nums[0];}int sum = Integer.MIN_VALUE;int count = 0;for (int i = 0; i < nums.length; i++){count += nums[i];sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）if (count <= 0){count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}}return sum;}}
122.买卖股票的最佳时机II
力扣题目链接
第i天到第j天的利润怎样计算？
把利润分解成每天为单位，而不是第i天到第j天整体去考虑。
每天的正利润累计起来就是最后的最大利润。class Solution {public int maxProfit(int[] prices) {int res = 0;for (int i = 1; i < prices.length; i++) {int temp = prices[i] - prices[i - 1];res += Math.max(temp, 0);}return res;}}
55. 跳跃游戏
力扣题目链接
不要纠结每次跳几部，看他每次最大能跳几步。
每次取跳跃的最大步数，每移动一步就更新最大覆盖的范围。看最后是否能覆盖到最后一个元素。class Solution { public boolean canJump(int[] nums) { if (nums.length == 1) { return true; } //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的 int coverRange = 0; //在覆盖范围内更新最大的覆盖范围 for (int i = 0; i <= coverRange; i++) { coverRange = Math.max(coverRange, i + nums[i]); if (coverRange >= nums.length - 1) { return true; } } return false; } }45.跳跃游戏II
题解
class Solution { public: int jump(vector<int>& nums) { int curDistance = 0; // 当前覆盖的最远距离下标 int ans = 0; // 记录走的最大步数 int nextDistance = 0; // 下一步覆盖的最远距离下标 for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在 nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标 if (i == curDistance) { // 遇到当前覆盖的最远距离下标 curDistance = nextDistance; // 更新当前覆盖的最远距离下标 ans++; } } return ans; } };1005.K次取反后最大化的数组和
题解
不断对最小值取k次反（别人的答案）。真是妙蛙种子进了米奇妙妙屋。
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
for(int i = 0; i < k; i++){
changeNums(nums);
}
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
public void changeNums(int[] nums){
Arrays.sort(nums);
nums[0] = -nums[0];
}
}
134. 加油站
题解
class Solution {
int rest = 0;
int sum = 0;
int index = 0;
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < gas.length; i++) {
rest += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (rest < 0) {
index = i + 1;
rest = 0;
}
}
if (sum < 0) return -1;
return index;
}
}
135. 分发糖果
力扣题目链接
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
再确定左孩子大于右孩子的情况（从后向前遍历）
那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。
题解
class Solution {
public int candy(int[] ratings) {
int[] candyNum = new int[ratings.length];
candyNum[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candyNum[i] = candyNum[i - 1] + 1;
} else {
candyNum[i] = 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyNum[i] = Math.max(candyNum[i], candyNum[i + 1] + 1);
}
}
int res = 0;
for (int num : candyNum) {
res += num;
}
return res;
}
}
860.柠檬水找零
- 账单是5，收下。
- 账单是10，找零5。
-
题解
class Solution { public boolean lemonadeChange(int[] bills) { int five = 0; int ten = 0; for (int i = 0; i < bills.length; i++) { if (bills[i] == 5) { five++; } if (bills[i] == 10) { if (five <= 0) return false; ten++; five--; } if (bills[i] == 20) { if (ten > 0 && five > 0) { ten--; five--; } else if (five >= 3) { five -= 3; } else return false; } } return true; } }406.根据身高重建队列
力扣题目链接
遇到两个维度权衡的时候，一定要先确定一个再考虑另一个。 身高从大到小排（身高相同的k小的排前面）
-
题解
class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator<int[]>() { @Override public int compare(int[] p1, int[] p2) { if (p1[0] != p2[0]) return p2[0] - p1[0]; return p1[1] - p2[1]; } }); List<int[]> list = new LinkedList<>(); for (int[] p : people) { list.add(p[1], p); } return list.toArray(new int[people.length][]); } }452. 用最少数量的箭引爆气球
力扣题目链接
让气球尽可能多的重叠，对数组进行排序。题解
class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, Comparator.comparing(point -> point[0])); int count = 1; for (int i = 1; i < points.length; i++) { if (points[i][0] > points[i - 1][1]) { //气球i和i-1不挨着 count++; } else { points[i][1] = Math.min(points[i][1], points[i - 1][1]);//更新最小右边界 } } return count; } }435. 无重叠区间
力扣题目链接
按照右边界排序来考虑题解
class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> { return a[1] - b[1]; }); int count = 0; int edge = Integer.MIN_VALUE; for (int i = 0; i < intervals.length; i++) { if (edge <= intervals[i][0]) { edge = intervals[i][1]; } else { count++; } } return count; } }763.划分字母区间
力扣题目链接
找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。 记录每一个字符最后出现的位置（一个for循环）
从头遍历字符（另一个for循环），更新字符出现的最远下标（Math.max），如果字符最远出现的位置下标等于当前循环的i，则找到了分割点。
题解
class Solution { public List<Integer> partitionLabels(String s) { LinkedList<Integer> list = new LinkedList<>(); int[] maxPos = new int[26]; for (int i = 0; i < s.length(); i++) { maxPos[s.charAt(i) - 'a'] = i; //每一个字符最后出现的位置 } //左右指针 int left = 0; int right = 0; for (int i = 0; i < s.length(); i++) { right = Math.max(right, maxPos[s.charAt(i) - 'a']);//更新字符出现的最远下标 if (i == right) { list.add(right - left + 1); left = i + 1; } } return list; } }738.单调递增的数字
力扣题目链接 ```java //将int型的n转化为char[] String s = String.valueOf(n)； char[] arr = s.toCharArray(); //或者 char[] arr = Integer.toString(n).toCharArray;
//将数字字符串转化成原生整型数据 int a = Integer.parseInt(“1231”);
<a name="Q0X5l"></a>
#### 题解
```java
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
char[] chars = s.toCharArray();
int start = chars.length;
for (int i = chars.length - 1; i > 0; i--) {
if (chars[i] < chars[i - 1]) {
chars[i - 1]--;
start = i;
}
}
for (int i = start; i < chars.length; i++) {
chars[i] = '9';
}
return Integer.parseInt(String.valueOf(chars));
}
}
714. 买卖股票的最佳时机含手续费
力扣题目链接
买入日期：遇到更低点就记录一下。
卖出日期：只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
class Solution {
public int maxProfit(int[] prices, int fee) {
int buy = prices[0] + fee;
int profit = 0;
for (int p : prices) {
if (buy > p + fee) { //买入
buy = p + fee;
} else if (buy < p) { //卖出
profit += p - buy;
buy = p;
}
}
return profit;
}
}
若有收获，就点个赞吧
0 人点赞
