贪心算法

发表于 | 分类于

455. Assign Cookies

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.
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 findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int gi = g.length-1;
        int si = s.length-1;
        int res = 0;
        
        while(gi >= 0 && si >= 0){
            if(g[gi] <= s[si]){
                ++res;
                --gi;
                --si;
            }
            else{
                --gi;
            }
        }
        
        return res;
    }
}

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example:

1
2
3
4
5
s = "abc", t = "ahbgdc"
Return true.
s = "axc", t = "ahbgdc"
Return false.
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 boolean isSubsequence(String s, String t) { 
        int sLen = s.length();
        int tLen = t.length();
        
        if(sLen > tLen){
            return false;
        }
        
        int si = 0;
        int ti = 0;
        while(si < s.length() && ti < t.length()){
            if(s.charAt(si) == t.charAt(ti)){
                ++si;
                ++ti;
            }
            else{
                ++ti;
            }
        }
        
        return si == sLen;
    }
}

435. Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

  • You may assume the interval’s end point is always bigger than its start point.
  • Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

解题思路:

动态规划之最长上升子序列
贪心算法：按照区间的结尾排序，每次选择结尾最早的，且和前一个区间不重叠的区间，这样留给后面的空间才能最大

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    
    class MyComparator implements Comparator<Interval>{
        @Override
        public int compare(Interval o1, Interval o2){
            if(o1.end != o2.end){
                return o1.end - o2.end;
            }
            else{
                return o1.start - o2.start;
            }
        }
    }
    
    public int eraseOverlapIntervals(Interval[] intervals) {
        
        if(intervals.length == 0){
            return 0;
        }
        
        Arrays.sort(intervals, new MyComparator());
        
        int cnt = 1;
        int pre = 0;
        for(int i = 1; i < intervals.length; ++i){
            if(intervals[i].start >= intervals[pre].end){
                ++cnt;
                pre = i;
            }
            
        }
        
        return intervals.length - cnt;
    }
}