偷懒总结篇|贪心算法|动态规划|单调栈|图论
由于这周来不及了,先过一遍后面的思路,具体实现等下周再开始详细写。
贪心算法
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里
剩下的明天做