什么是贪心？
本质：每一阶段局部取优，从而达到全局最优
极端：可能在处理贪心问题时不会考虑到使用贪心 且贪心并无套路
贪心算法更考验的思考过程的递进性，逻辑链 更倾向于实际生活出现的问题
lc
分发饼干
思路：先对数组进行排序，从最大处返回，双指针处理即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int result = 0;
int gr = g.length - 1;
int sr = s.length - 1;
while(gr >= 0){
if(sr >= 0 && s[sr] >= g[gr]){
result++;
sr--;
}
gr--;
}
return result;
}
}
|
376. 摆动序列
需求：求有多少个差值处于正负摆动的位置
思路：循环，将所有差值进入一个栈，若pop元素对比现在进入这个为不同正负，则当前元素入，否则执行pop 最后返回栈的大小+1
这是我个人的思路，时间复杂度是O(n)，每个元素处理应该是不超过两次2n也是O(n)，但是使用了stack作为额外空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int wiggleMaxLength(int[] nums) {
Stack<Integer> stack = new Stack<>();
boolean flag1 = true,flag2 = true;
int deffer = 0;
for (int i = 0; i < nums.length; i++) {
if(i > 0){
deffer = nums[i] - nums[i-1];
if(deffer > 0){
flag1 = true;
} else if (deffer < 0) {
flag1 = false;
}else {
continue;
}
}
if(!stack.isEmpty()){
int temp = stack.peek();
if(temp > 0){
flag2 = true;
}else {
flag2 = false;
}
if(flag2 != flag1){
stack.push(deffer);
}
}else if (deffer != 0 && stack.isEmpty()){
stack.push(deffer);
}
}
return stack.size() + 1;
}
}
|
53. 最大子序和
特征：连续变化的起始点 —》 滑动窗口的思想去重置起始位置，实际上就是用0作为新的起始点
需求：连续的数组相加最大
思路：贪心 局部取优，对于这题如果相加出现负数，就将当前舍弃 从下一个重新开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int count = 0;
int result = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
result = count > result ? count : result;
if(count < 0){
count = 0;
}
}
return result;
}
}
|
122.买卖股票的最佳时机II
思路：贪心 当天直接买 第二天若比今天多就直接卖，若小就留着
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i-1]){
result += prices[i] - prices[i-1];
}
}
return result;
}
}
|
55. 跳跃游戏
思路：贪心策略 不去考虑跳跃长度 直接跳跃当前最大的长度，同时更新现在能到的最远距离 更新是随着i的数值进行变化，若大于当前范围则替换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1){
return true;
}
int range = 0;
for (int i = 0; i <= range; i++) {
if(nums[i] + i > range){
range = nums[i] + i;
}
if(range >= nums.length - 1){
return true;
}
}
return false;
}
}
|
45.跳跃游戏II
思路：对于本题和上题的不同之处是你需要知道在所在范围之内跳到哪才能使得下步也能获得最优，取得最大范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int jump(int[] nums) {
if(nums == null || nums.length == 1 || nums.length == 0){
return 0;
}
int curRange = 0;
int nextRange = 0;
int result = 0;
for (int i = 0; i < nums.length; i++) {
nextRange = Math.max(nextRange,nums[i] + i);
if(nextRange >= nums.length - 1){
result++;
break;
}
if(i == curRange){
curRange = nextRange;
result++;
}
}
return result;
}
}
|
方法二：进行代码简化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int jump(int[] nums) {
if(nums == null || nums.length == 1 || nums.length == 0){
return 0;
}
int curRange = 0;
int nextRange = 0;
int result = 0;
for (int i = 0; i < nums.length - 1; i++) {
nextRange = Math.max(nextRange,nums[i] + i);
if(i == curRange){
curRange = nextRange;
result++;
}
}
return result;
}
}
|
1005.K次取反后最大化的数组和
思路：考虑贪心 取局部最优 给数组排序（快排 nlogn 不可 ，要进行绝对值排列）从后往前遇到负数直接取反 若剩余k为偶数直接对最后一个元素进行反复变化
若为奇数直接处理第一个nums[i] 似乎可以统一，剩余次数直接对第一个数字
思路优化：直接绝对值排序，思考两次贪心即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int result = 0;
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o1) - Math.abs(o2))
.mapToInt(Integer::intValue).toArray();
for (int i = nums.length - 1; i >= 0; i--) {
if(nums[i] < 0 && k > 0){
nums[i] = -nums[i];
k--;
}
}
if(k % 2 == 1){
nums[0] = -nums[0];
}
return Arrays.stream(nums).sum();
}
}
|
134. 加油站
思路：贪心，只考虑当前这次油量是否够用，如果够用则继续，不够则从下一个重新开始 用一个变量记录这个初始值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = start; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0){
curSum = 0;
start = i + 1;
}
}
if(totalSum < 0){
return -1;
}
return start;
}
}
|
135. 分发糖果
思路：本题出现两个维度的比较，此时不可能做到兼顾，所以这里可以分类处理，先处理从左向右，再考虑从右向左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyNum = new int[len];
candyNum[0] = 1;
for (int i = 1; i < len; i++) {
candyNum[i] = (ratings[i] > ratings[i - 1]) ? candyNum[i - 1] + 1 : 1;
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyNum[i] = Math.max(candyNum[i], candyNum[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyNum) {
ans += num;
}
return ans;
}
}
|
860.柠檬水找零
思路：当没有思路时，考虑细节去进行分类讨论是个不错的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public boolean lemonadeChange(int[] bills) {
int[] times = new int[3];
Arrays.fill(times,0);
for (int i = 0; i < bills.length; i++) {
if(bills[i] == 5){
times[0]++;
}
else if(bills[i] == 10){
times[0]--;
times[1]++;
}
else if (bills[i] == 20){
if(times[1] > 0){
times[1]--;
times[0]--;
}else {
times[0] -= 3;
}
}
if(times[0] < 0 || times[1] < 0){
return false;
}
}
return true;
}
}
|
406.根据身高重建队列
思路：同样是出现两个方面的维度，此时应该确定优先处理的维度,处理k的维度之后发现依旧无序，没有意义，所以转而处理h 身高有序之后处理k 直接将元素插入到k下标处
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(a,b)->{
if(a[0] == b[0]) return a[1] - b[1];
return b[0] - a[0];
});
LinkedList<int[]> list = new LinkedList<>();
for (int[] person : people) {
list.add(person[1],person);
}
int[][] result = list.toArray(new int[people.length][]);
return result;
}
}
|
452. 用最少数量的箭引爆气球
思路：贪心 如何才能是局部使用的箭最少呢？
本题误区：在处理贪心问题时，如果你对于局部的处理方式能出现多个反例，则说明是逻辑的问题，需要优化一下处理局部的逻辑，而非去对反例存在的部分特殊性进行特殊处理，这样处理下来反而会愈加复杂，这样是没有什么意义的
优化思路比执着的想用之前的思路重要的多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points,(a,b) -> Integer.compare(a[0], b[0]));
int result = 1;
for (int i = 1; i < points.length; i++) {
if(points[i][0] > points[i-1][1]) {
result++;
}else {
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return result;
}
}
|
435. 无重叠区间
思路：一上来看到重叠区间，思考进行排序操作，这里按照两边排序都是一样可以的
目的是：主要就是为了让区间尽可能的重叠
我更喜欢按照左边界进行排序，如果出现重叠部分，计数 + 1 之后更新比较边界
这里有个细节，重叠的两个更新边界是使用谁的边界，换句话说也就是需要除去谁，那必然是除去边界更大的那个元素，使用边界更小的边界。
why？
因为不光要考虑当前比较的两个元素，还需要考虑下一个比较的元素，小边界意外的好用呢~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a,b)-> Integer.compare(a[0],b[0]));
int remove = 0;
int pre = intervals[0][1];
for(int i = 1; i < intervals.length; i++) {
if(pre > intervals[i][0]) {
remove++;
pre = Math.min(pre, intervals[i][1]);
}
else pre = intervals[i][1];
}
return remove;
}
}
|
763.划分字母区间
思路：在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了
- 统计碰到的每个元素的最后位置 数据结构使用map即可 2. 遍历过程中更新当前数组的最后位置 3. 二次遍历对比map中的值进行更新比较
优化处理方式：
- 直接使用数组即可 使用ascll编码去对应下标遍历时更新即可
- 二次遍历对比边界值大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public List<Integer> partitionLabels(String s) {
int[] end = new int[27];
List<Integer> result = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
end[s.charAt(i) - 'a'] = i;
}
int right = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
if(end[s.charAt(i) - 'a'] > right){
right = end[s.charAt(i) - 'a'];
}
if(i == right){
result.add(i - left + 1);
left = i + 1;
}
}
return result;
}
}
|
56. 合并区间
需求：寻找重叠数组 进行合并
思路：按照左边界排序，相同的不管 遍历如果存在 p[i][0] <= p[i-1][0] 的进行合并操作
[start][end] start是p[i-1][0] end是二者的 1 中最大的一个
思路优化：这里的问题是我差点陷入处理细节的困境 如果代码要多余优质解答，且多次处理特殊情况 此时优先优化思路 而非处理细节
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(o1, o2) -> Integer.compare(o1[0],o2[0]));
List<int[]> result = new LinkedList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if(intervals[i][0] > end){
result.add(new int[]{start, end});
start = intervals[i][0];
end = intervals[i][1];
}else {
end = Math.max(end,intervals[i][1]);
}
}
result.add(new int[]{start,end});
return result.toArray(new int[result.size()][]);
}
}
|
738.单调递增的数字
思路：贪心 优先处理n的最高位 置为相等，往后处理如果第二位数字大于第二位，直接将第一位数字减1 剩余位均置为数字9
思路优化：从后往前遍历的方式 防止出现处理后前位较小的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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));
}
}
|
968.监控二叉树
思路：1. 考虑在哪放置摄像头 2. 使用状态进行定义每个节点 3. 分类讨论父节点接收到的不同状态的情形
思考贪心：摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖，所以要从下往上遍历二叉树 且叶子节点不能进行放置摄像头
局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少
状态定义的技巧：如果在递归中需要判断每个节点是否为某种状态，直接让其返回一个特定的值即可
状态符号：0 未覆盖 1 覆盖 2 摄像头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private int result = 0;
public int minCameraCover(TreeNode root) {
if(backTrack(root) == 0){
result++;
}
return result;
}
public int backTrack(TreeNode root){
if(root == null){
return 1;
}
int left = backTrack(root.left);
int right = backTrack(root.right);
if(left == 1 && right == 1){
return 0;
}
if(left == 0 || right == 0){
result++;
return 2;
}
if(left == 2 || right == 2){
return 1;
}
return -1;
}
}
|
总结
贪心部分整体走过一遍之后发现贪心不存在套路是正确的
其实不用过于强调什么题目是贪心，什么不是贪心，如果找出局部最优并可以推出全局最优，就是贪心。
