贪心算法采用贪心的策略，保证每步都是局部最优，最终达到全局最优
分配问题
455.Assign Cookies (Easy)
题目描述
有一群孩子和一堆饼干，每个孩子都有一个饥饿度，每个饼干都有一个大小，每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
输入输出样例
输入两个数组，分别代表孩子们的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。
1
2
| Input: [1, 2], [1, 2, 3]
Output: 2
|
c++:
1
2
3
4
5
6
7
8
9
10
| int findContentChildren(vector<int>& children, vector<int>& cookies) {
sort(children.begin(), children.end());
sort(cookies.begin(), cookies.end());
int child = 0, cookie = 0;
while (child < children.size() && cookie < cookies.size()) {
if (children[child] <= cookies[cookie]) ++child;
++cookie;
}
return child;
}
|
java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int findContentChildren(int[] g, int[] s) {
int max = 0;
Arrays.sort(g);
Arrays.sort(s);
for (int i = 0, j = 0; i < s.length & j < g.length; i++) {
if (g[j] <= s[i]) {
max++;
j++;
}
}
return max;
}
}
|
- Candy(Hard)
题目描述
一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果;所有的孩子至少要有一个糖果。求解最少需要多少个糖果。
输入输出样例
输入是一个数组，表示孩子的评分。输出是最少糖果的数量。
1
2
| Input: [1, 0, 2]
Output: 5
|
c++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int candy(vector<int>& ratings) {
int size = ratings.size();
if (size < 2) {
return size;
}
vector<int> num(size, 1);
for (int i = 1; i < size; ++i) {
if (ratings[i] > ratings[i - 1])
num[i] = ratings[i - 1] + 1;
}
for (int i = size - 1; i > 0; --i) {
if (ratings[i] < ratings[i - 1])
num[i - 1] = max(num[i - 1], num[i] + 1);
}
return accumulate(num.begin(), num.end(), 0);
}
|
java:
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 candy(int[] ratings) {
int[] rating = new int[ratings.length];
Arrays.fill(rating, 1);
for (int i = 1; i < rating.length; i++) {
if (ratings[i] > ratings[i - 1]) {
rating[i] = rating[i - 1] + 1;
}
}
for (int i = rating.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
rating[i] = Math.max(rating[i + 1] + 1, rating[i]);
}
}
int sum = 0;
for (int rat : rating) {
sum += rat;
}
return sum;
}
}
|
区间问题
- Non-overlapping Intervals (Medium)
题目描述
给定多个区间，计算这些区间互不重叠所需要移除区间的最小个数，起止相连不算重叠。
输入输出样例
输入是一个数组，数组由多个长度固定为2的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。
1
2
| Input: [[1, 2], [2, 4], [1, 3]]
Output: 1
|
c++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
std::sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int>b) {
return a[1] < b[1];
});
int total = 0, prev = intervals[0][1];
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] < prev) {
total += 1;
} else {
prev = intervals[i][1];
}
}
return total;
}
|
java:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int invals = 0;
if (intervals.length <= 0) {
return invals;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int[] interval = intervals[0];
int max = 1;
for (int i = 1; i < intervals.length; i++) {
if (interval[1] <= intervals[i][0]) {
interval = intervals[i];
max++;
}
if(interval[1] > intervals[i][1]){
interval = intervals[i];
}
}
return intervals.length - max;
}
}
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int invals = 0;
if (intervals.length <= 0) {
return invals;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int[] nums = new int[intervals.length];
Arrays.fill(nums, 1);
for (int i = 1; i < intervals.length; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
nums[i] = Math.max(nums[i], nums[j] + 1);
}
}
}
int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
return nums.length - max;
}
}
|