LeetCode题解_贪心

2022-06-19 1470 words 3 minutes

Contents

贪心

leetcode_455_easy

问题描述
给胃口值为g[i]的孩子i分配尺寸为s[j]的饼干j，s[j] >= g[i]满足分配条件。每个孩子最多一块饼干，求分配孩子的最大数值。

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

解法：贪心算法

两种贪心方法
- 1、优先把尺寸更小的饼干满足胃口更小的孩子。
- 2、优先把尺寸更大的饼干满足给胃口更大的孩子。
原理

每次操作局部最优,且最后结果全局最优。

采用反证法，对第一种方法，假设存在一种更优的策略在分配第i个孩子时，饼干尺寸n大于贪心所用的饼干尺寸m，那么剩余的更大胃口的孩子可能导致m尺寸无法分配，结果可能更少。

对第二种方法，假设存在一种更优的策略在分配第i个孩子时，饼干尺寸n小于贪心所用的饼干尺寸m，并不能分配到更多的孩子，因为当前分配的孩子胃口已经是最大了，剩下更大的尺寸也只能分配给其他胃口更小的孩子。

代码

//方法1
public int findContentChildren(int[] g, int[] s) {
	Arrays.sort(g);
	Arrays.sort(s);
	int i=0,j=0;
	while (i < g.length && j < s.length) {
		if (s[j] >= g[i]) {
			i++;
		} 
		j++;
	}

	return i;
}

//方法2
public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i=g.length-1,j=s.length-1;
    while (i >=0 && j >= 0) {
        if (s[j] >= g[i]) {
            j--;
        } 
        i--;
    }

return s.length-1-j;
}

leetcode_435_middle

<leetcode_link>

问题描述
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。
```
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
```
解法：贪心算法
原理

意识到区间的start端并不能决定问题，将数组按end端升序排序，每次取end端最小的且不与前一个区间重叠的区间作为下一个区间，这是因为需要留下尽量多的区间，优先舍弃end端大的，以此类推。

代码

public int eraseOverlapIntervals(int[][] intervals) {
    //按end升序排序
	Arrays.sort(intervals, new Comparator<int[]>() {
		@Override
		public int compare(int[] a, int[] b) {
			return a[1] - b[1];
		}
	});
	int count = 1, end = intervals[0][1], j = 1;
	while (j < intervals.length) {
		if (end <= intervals[j][0]) {
			end = intervals[j][1];
			count++;
		}
		j++;
	}

	return intervals.length - count;
}

leetcode_452_middle

<leetcode_link>

问题描述
XY平面上的气球用整数数组 points 表示，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。

在坐标x处射出一支箭，若满足 xstart ≤ x ≤ xend，则该气球会被引爆，弓箭可以无限地前进且无限数目。求返回引爆所有气球所必须射出的 最小弓箭数 。
```
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
```
解法：贪心算法
原理

问题可以转化为求不重叠的区间数，因为重叠的气球区间均用一个弓箭即可引爆。

发现原先的compare方式用减法会导致溢出，改为比较形式。
测试用例：[[-2147483646,-2147483645],[2147483646,2147483647]]

代码

public int findMinArrowShots(int[][] points) {
	Arrays.sort(points, new Comparator<int[]>() {
		@Override
		//不用减法防止溢出
		public int compare(int[] o1, int[] o2) {
			return (o1[1]<o2[1])?-1:(o1[1]==o2[1]?0:1);
		}
	});

	int count=1,i=1,end=points[0][1];
	while(i<points.length) {
		if(end<points[i][0]) {
			end=points[i][1];
			count++;
		}
		i++;	

	}   	
	return count;
}

leetcode_406_middle

<leetcode_link>

问题描述
数组(乱序) people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

重新构造并返回队列queue 使其满足规定的顺序。
```
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
```
解法：贪心算法
原理

如果按身高升序排列，身高最矮且kj最大的人应该先被排列，因为后面的人身高都比他高，或者kj比他小也会影响到他。

实现时发现反过来按身高降序排列，kj升序排列更为简单，只需要一个链表队列即可。每次插入身高最高的人，相同身高时需要优先插入kj小的人，因此每步都是局部最优解，后续的插入都对它没有影响。

代码

public int[][] reconstructQueue(int[][] people) {

	int[][] sorted_people = new int[people.length][2];
	//按身高hi降序，数量ki升序排序
	Arrays.sort(people, new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			if(o1[0]==o2[0])
				return o1[1]-o2[1];				
			return o2[0]-o1[0];
		}
	});

	List<int[]> list= new LinkedList<int[]>();
	//每次插入都是局部最优
	for(int[] p:people) {
		list.add(p[1], p);
	}
	list.toArray(sorted_people);

	return sorted_people;
}

Contents

LeetCode题解_贪心

贪心

leetcode_455_easy

leetcode_435_middle

leetcode_452_middle

leetcode_406_middle

References