当前位置：首页 > news >正文

偷懒总结篇|贪心算法|动态规划|单调栈|图论

news 2025/7/4 13:53:22

由于这周来不及了，先过一遍后面的思路，具体实现等下周再开始详细写。

贪心算法

这个图非常好

122.买卖股票的最佳时机 II(妙，拆分利润)

把利润分解为每天为单位的维度，需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

55. 跳跃游戏(妙，覆盖范围)

不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

45.跳跃游戏 II(难)

还是要看最大覆盖范围。

以最小的步数增加最大的覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

1005.K次取反后最大化的数组和(简单)

先让绝对值大的负数变为正数，当前数值达到最大；然后如果K依然大于0，只找数值最小的正整数进行反转。

第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

将数组按照绝对值大小从大到小排序

nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();

对int[]数组元素求和

Arrays.stream(nums).sum()

        int ans = 0;for (int num : nums) {ans += num;}

134. 加油站(妙)

（补充：for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！）

当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

135. 分发糖果(妙，2次贪心)

先确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

两次贪心的策略：

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

分两个阶段
1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，
此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 
和 右边糖果数 + 1 二者的最大值，这样才符合 
它比它左边的大，也比它右边大

860.柠檬水找零(简单)

直接统计five,ten的count就好了

情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

406.根据身高重建队列(难，妙，2次贪心)

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。

如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

那么只需要按照k为下标重新插入队列就可以了

二维数据排序

// 身高从大到小排（身高相同k小的站前面）Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列return b[0] - a[0];   //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列});

Linkedlist.add()

Linkedlist.add(index, value)，会将value插入到指定index里

452. 用最少数量的箭引爆气球(重叠区间)

重叠区间问题：本质就是更新区间的边界

按照气球的起始位置排序

// int[][] points
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭

不需要移走气球，直接记录res++即可。

技巧：寻找重复的气球，寻找重叠气球最小右边界

points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界

435. 无重叠区间(重叠区间)

本质还是排序+更新边界

有452，本题很好理解

763.划分字母区间(妙，重叠区间)

用最远出现距离模拟了圈字符的行为。思路很巧妙

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

统计字符串S中每个字母char出现的最远位置

int[] edge = new int[26];char[] chars = S.toCharArray();for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i;}

idx = Math.max(idx,edge[chars[i] - 'a']); // 更新right下标

56. 合并区间(简单，重叠区间)

没什么好说的，简单

//按照左边界排序
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));

738.单调递增的数字(妙，flag的运用)

例如N=98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
从后向前遍历：
举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
用一个flag(start)来标记从哪里开始赋值9。

// flag用来标记赋值9从哪里开始
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行

将一个 `int` 类型的整数 `N` 转换为字符串，然后将这个字符串按字符拆分为一个字符数组。

String[] strings = (N + "").split("");

String, char 与 int 的转换使用

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}