最简易的贪心算法

参考资料：谷歌高畅Leetcode刷题笔记。

题目网址：LeetCode。

算法解释

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。全局最优结果是局部最优结果的和，且局部结果互不相干！

例题及题解

分配问题

455.分发饼干 （简单）

题目大意：

给我们一堆饼干和一群孩子，要求我们把饼干分给孩子，每个孩子有一个饥饿值，每个饼干有一个饱腹值，且每个孩子只能分一个饼干，要求我们求出最多能吃饱的孩子数量。

解题思路：

首先可以分别将孩子饥饿值的数组和饼干饱腹值的数组升序排序，然后饥饿值最小的孩子吃饱腹值最少的饼 干，这样依次取值即可满足局部最优，局部最优加和即全局最优。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	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;
	}
}

135. 分发糖果（困难）

题目大意：

一群孩子站成一排，每个孩子有自己的评分，现在要求我们给这些孩子分发糖果，要求：

  • 1.每个孩子至少分配一个糖果。
  • 2.评分高于两侧的孩子得到的糖果数量必须高于两侧孩子得到的糖果数量。
  • 求出至少需要准备的糖果数。

解题思路：

这道题我们不再需要排序，只需要左右两次遍历即可，设数组cano记录每个孩子分得的糖果数量，数组ratings记录孩子的评分。首先我们初始化cano数组为1（即初始为糖果总数最小值），然后对数组ratings从左向右（左条件）进行遍历，当ratings[i+1]>ratings[i]时，cano[i+1]+1；最后对ratings进行从右向左（右条件）遍历，与左边不同的是，此次遍历不能直接更新数组cano的值，需要取更新值和原值中大的值，即:

这样做即可同时满足左条件和右条件。

解题代码：

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
class Solution {
	public int candy(int[] ratings) {
		int ct = ratings.length,cnt = 0,i,j;
		int []cano = new int[ct];
		for (i = 0;i < ct;i++)
		{
			cano[i] = 1;
		}
		for (i = 0;i < ct - 1;i++)
		{
			j = i + 1;
			if (ratings[j] > ratings[i]) cano[j]=cano[i]+1;
		}
		for (i = ct - 1;i >= 1;i--)
		{
			j = i - 1;
            //满足左规则后右规则可能会更新数据，因此取最大值保证同时满足左右规则
			if (ratings[j] > ratings[i]) cano[j]=Math.max(cano[j],cano[i]+1);
		}
		for(int it:cano)
		{
			cnt+=it;
		}
		return cnt;
	}
}

区间问题

435. 无重叠区间（中等）

题目大意：

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。注意：

  1. 可以认为区间的终点总是大于它的起点。
  2. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

解题思路：

这个区间的尾元素总是大于首元素，要保证最优，需要起始区间的尾元素最小，这样才能容纳最多的区间。所以首先需要根据区间的尾元素按照升序排序（此处用到自定义排序），然后设定一个起始数begin = intervals[0][1]；再遍历排序完成的区间数组，比较起始区间尾元素和第i（i = 1,2,3,…,intervals.length）个区间的首元素的大小，若：

则说明第i个区间与初始区间重合，故计数cnt++；反之满足不重合条件，不计数，并更新初始区间尾元素为：begin = intervals[i][1]，最后返回cnt即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0 || intervals.length == 1)
        return 0;
        Arrays.sort(intervals, ((o1,o2) -> o1[1]-o2[1])); //自定义排序
        int cnt = 0;
        int begin = intervals[0][1];
        for (int i = 1;i < intervals.length;i++)
        {
            if (begin > intervals[i][0])
            {
                cnt++;
            } 
            else{
                begin = intervals[i][1];
            }
        }
        return cnt;
    }
}

注：自定义排序

452. 用最少数量的箭引爆气球

题目大意：

给定一个数组points，包含points.length个区间，求不重叠区间的个数。

解题思路：

该题与上文中435. 无重叠区间有点类似，也可用lambda表达写，但有个坑：测试用例：[[-2147483646,-2147483645],[2147483646,2147483647]]，若直接用：

1
Arrays.sort(intervals, ((o1,o2) -> o1[1]-o2[1]));

排序，相减会溢出，导致排序错误，所以应该这样写：

1
Arrays.sort(points,(o1, o2) -> o1[0]>o2[0] ? 1:-1);

排序后和435题类似，先定义一个begin = points[0][1]，然后开始遍历，更新begin值。不同的是，要注意区间长度的影响，如测试用例：[[1,2],[4,5],[1,5]]，若排序为：

  • [1,5]
  • [1,2]
  • [4,5]

则计算出只需一箭就可射完，但实际需要两箭。解决方法：只需在判断begin > ponits[i][0]后再判断是否begin > points[i][1]，若是，则更新begin的值为points[i][1]，相当于缩小区间。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length == 0 || points == null) return 0;
        Arrays.sort(points,(o1, o2) -> o1[0]>o2[0] ? 1:-1);
        int cnt = 1;
        int begin = points[0][1];
        for (int i = 1;i < points.length;i++)
        {
            if (points[i][0] > begin)
            {
                cnt++;
                begin = points[i][1];
            }
            else if(points[i][1] < begin)
            {
                begin = points[i][1];
            }
        }
        return cnt;
    }
}

763. 划分字母区间

题目大意：

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。如：

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

解题思路：

首先我们可以将某个区间内所有出现的字母最后出现（需要不断更新）的位置用数组n记录，然后设一个begin和end分别表示取出的区间的首位和末尾的位置，然后遍历所有字母，每遇到一个字母，就更新end的值，end要求取最后出现该字母的位置，即数组n中对应字母下标的值（总是取最大），即：

1
end = Math.max(end,n[S.charAt(i) - 'a']);

当某一段字母遍历结束时（即i == end），end-begin+1就是该段字母中字母的数量，存入结果数组result，然后更新begin的值为begin=end+1。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] n = new int[26];
        Arrays.fill(n,-1);
        for (int i = 0;i < S.length();i++)
        {
            n[S.charAt(i) - 'a'] = i;
        }
        int begin = 0, end = 0;
        List result = new ArrayList();
        for (int i = 0;i < S.length();i++)
        {
            end = Math.max(end,n[S.charAt(i) - 'a']);
            if (i == end)
            {
                result.add(end-begin+1);
                begin=end+1;
            }
        }
        return result;
    }
}