Posted Updated Leetcode8 minutes read (About 1230 words)0 visits

Greedy问题慢慢总结

Greedy慢慢总结：

  1. Jump Game：这道题还是很简单的，思路就是遍历数组找到最远能到的位置。
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
/*
55. Jump Game
Medium

2523

241

Favorite

Share
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
*/

class Solution {
    public boolean canJump(int[] nums) {
        int farest = 0;
        for(int i =0;i<=farest && i<=nums.length-1;i++){
            farest = Math.max(farest, i+nums[i]);
        }
        
        return farest >= nums.length-1;
    }
}
  1. Jump Game II:我们需要记录的是我们跳出一步所能走的最远距离，同时在走到这个局部最远距离的过程中，我们会记录下来下一次的局部最短距离，当我们行进到本次的局部最远距离的时候，我们知道是时候该跳下一步了，所以我们step++并更新局部最远距离。所以这道题我们的i要小于nums.length-1，因为nums.length-1这个点是最后一个我们可能在跳的点
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
/*
45. Jump Game II
Hard

1539

87

Favorite

Share
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:

You can assume that you can always reach the last index.
*/

class Solution {
    public int jump(int[] nums) {
        int step = 0;
        int lastLargest = 0;
        int curlargest = 0;
        for(int i =0;i<nums.length-1;i++){
            curlargest = Math.max(curlargest, i+nums[i]);
            if(i==lastLargest){
                lastLargest = curlargest;
                step++;
            }
                
        }
        
        return step;
        
    }
}
  1. Task Scheduler:https://leetcode.com/problems/task-scheduler/discuss/104500/Java-O(n)-time-O(1)-space-1-pass-no-sorting-solution-with-detailed-explanation
    Greedy点：最大频率的一定要先被选择，被选择后在里面的idle位置填充其他小于最大频率的任务。corner case：存在多个最大频率的任务，解决方法是没存在一个最大频率的任务，相当于我们idle的间隔减一。
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
/*
621. Task Scheduler
Medium

2060

382

Favorite

Share
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

 

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
 

Note:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].
*/

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int max = 0;
        int maxCount = 0;
        int[] chs = new int[26];
        for(char c:tasks){
            chs[c-'A']++;
            if(chs[c-'A']==max){
                maxCount++;
            }
            else if(chs[c-'A']>max){
                maxCount = 1;
                max = chs[c-'A'];
            }
        }
        
        int partitionNumber = max-1;
        int partitionCount = n-(maxCount-1);
        int taskNotHighestFreq = tasks.length - max*maxCount;
        int idleNumber = partitionNumber*partitionCount -taskNotHighestFreq;
        idleNumber = Math.max(0, idleNumber);
        
        return tasks.length+idleNumber;
    }
}
  1. Candy: https://leetcode.com/problems/candy/solution/
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
/*
135. Candy
Hard

623

131

Favorite

Share
There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.
*/
class Solution {
    public int candy(int[] ratings) {
        int[] nums = new int[ratings.length];
        Arrays.fill(nums, 1);
        for(int i =1;i<=nums.length-1;i++){
            if(ratings[i]>ratings[i-1]){
                nums[i] = nums[i-1]+1;
            }
        }
        for(int i =nums.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                nums[i] = Math.max(nums[i], nums[i+1]+1);
            }
        }
        int sum = 0;
        for(int i =0;i<=nums.length-1;i++){
            sum += nums[i];
        }
        return sum;
    }
}
  1. Gas Station:
    If car starts at A and can not reach B. Any station between A and B
    can not reach B.(B is the first station that A can not reach.)
    If the total number of gas is bigger than the total number of cost. There must be a solution.
    由以上两点，我们每次发现我们的油不够了，我们就把新起点放到当前位置(因为上一个起点到当前位置没有哪个点可以有可能油够：我们上一个起点的油一定大于起步距离，那么如果连上一个起点的油都不够开到当前位置，那么之间的点也都不可能作为起点)，并且清空我们的油桶，所以最后我们会逐步淘汰只剩一个最后的起点，如果这时我们发现总油量大于等于总里程，那么ok这个结果就是我们想要的，否则说明不可能有结果。
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
134. Gas Station
Medium

982

322

Favorite

Share
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
*/
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasCount = 0;
        int costCount = 0;
        int start = 0;
        int tank = 0;
        for(int i =0;i<=gas.length-1;i++){
            gasCount = gasCount + gas[i];
            costCount = costCount+cost[i];
            tank = tank+gas[i]-cost[i];
            if(tank<0){
                tank = 0;
                start = i+1;
            }
        }
        if(gasCount<costCount){
            return -1;
        }
        else {
            return start;
        }
        
    }
}
Follow

Catalogue

×