LC376 Wiggle Subsequence

Problem

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

1
2
3
Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

1
2
3
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

1
2
Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

Think
  • Approach 1

DP

up[i]表示以第i个元素作为结尾的最长摇摆数组，且结尾处为上扬；

down[i]表示以第i个元素作为结尾的最长摇摆数组，且结尾处为下降；

若nums[j] < nums[i]，则up[i] = max(down[j] + 1)；

若nums[j] > nums[i]，则down[i] = max(up[j] + 1)；

最终返回max(up.back(), down.back()) + 1

  • Approach 2

DP改进版

up[i]表示前i个元素的最长摇摆数组，且结尾处为上扬；

down[i]表示前i个元素的最长摇摆数组，且结尾处为下降；

若nums[i - 1] < nums[i]，则up[i] = down[i - 1] + 1, down[i] = down[i - 1]；

若nums[i - 1] > nums[i]，则up[i] = up[i - 1], down[i] = up[i - 1] + 1；

否则up[i] = up[i - 1]，down[i] = down[i - 1]；

最后返回max(up.back(), down.back())

  • Approach 3

Greedy

设置preDiff记录上一次的相邻两个数字的差值，如果preDiff >= 0则需要找下一组diff < 0的相邻数字，如果preDiff <= 0则需要找下一组diff > 0的相邻数字；找到距离最近的一组，然后置preDiff = diff，直至运行到数组尾端。

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if(n < 2) return n;
    vector<int> up(n, 0);
    vector<int> down(n, 0);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                up[i] = max(up[i], down[j] + 1);
            }
            else if(nums[i] < nums[j]){
                down[i] = max(down[i], up[j] + 1);
            }
        }
    }
    return max(up.back(), down.back()) + 1;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if(n < 2) return n;
    vector<int> up(n, 1);
    vector<int> down(n, 1);
    for(int i = 1; i < n; i++){
        if(nums[i - 1] < nums[i]){
            up[i] = down[i - 1] + 1;
            down[i] = down[i - 1];
        }
        else if(nums[i - 1] > nums[i]){
            up[i] = up[i - 1];
            down[i] = up[i - 1] + 1;
        }
        else{
            up[i] = up[i - 1];
            down[i] = down[i - 1];
        }
    }
    return max(up.back(), down.back());
}
  • Approach 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if(n < 2) return n;
    int prevDiff = nums[1] - nums[0];
    int count = prevDiff ? 2 : 1;
    for(int i = 2; i < n; i++){
        int diff = nums[i] - nums[i - 1];
        if((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)){
            count += 1;
            prevDiff = diff;
        }
    }
    return count;
}

LC55 Jump Game

Problem

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:

1
2
3
Input: nums = [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:

1
2
3
Input: nums = [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.

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i][j] <= 10^5
Think
  • Approach 1

DP，dp[i]表示从第i个元素开始能否跳到最后一个位置处

从i处所能跳到的位置范围为[i + 1, min(i + nums[i], n - 1)]，因此遍历这个范围内的每一个数字j，如果存在dp[j] = true，则dp[i] = true。

  • Approach 2

Greedy

设置最后可以跳到的位置为lastPos，初始化为n - 1。从后向前遍历数组的每一个元素nums[i]，如果nums[i] + i >= lastPos，说明在i这个位置可以跳到lastPos，因此将lastPos设置为i。最后判断lastPos是否等于0即可。

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool canJump(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n, false);
    dp[n - 1] = true;
    for(int i = n - 2; i >= 0; i--){
        int maxStep = min(n - 1, nums[i] + i);
        for(int j = i + 1; j <= maxStep; j++){
            if(dp[j]){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[0];
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
bool canJump(vector<int>& nums) {
    int n = nums.size();
    int lastPos = n - 1;
    for(int i = n - 1; i >= 0; i--){
        if(i + nums[i] >= lastPos){
            lastPos = i;
        }
    }
    return lastPos == 0;
}

LC45 Jump Game II

Problem

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:

1
2
3
4
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.

Think Greedy

设置两个变量maxPos和maxSteps，maxPos表示当前可以到达的最远的位置，maxSteps表示使用当前步数res可以达到的最远的位置。遍历数组，当发现maxSteps < i，即使用当前步数res到不了i的时候，就需要新的步数，也就是res++，并将maxSteps设为maxPos；同时更新maxPos为当前可以到达的最远位置max(maxPos, i + nums[i])。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int jump(vector<int>& nums) {
    int n = nums.size();
    if(n < 2) return 0;
    int maxPos = nums[0], maxSteps = nums[0];
    int res = 1;
    for(int i = 0; i < n; i++){
        if(maxSteps < i){
            res++;
            maxSteps = maxPos;
        }
        maxPos = max(maxPos, i + nums[i]);
    }
    return res;
}

LC134 Gas Station

Problem

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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.
Think

Greedy

设total_tank为总的gas[i] - cost[i]的和，curr_tank为从start_station到当前station的gas[i] - cost[i]的和，若curr_station < 0，则说明从start_station到当前位置是不可以实现的，因此将start_station置为i + 1，curr_tank重置为0。

最后若总的total_tank < 0，则说明整个环是不可能实现的，因此返回-1，否则返回start_station。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    int total_tank = 0, curr_tank = 0;
    int start_station = 0;
    for(int i = 0; i < n; i++){
        total_tank += gas[i] - cost[i];
        curr_tank += gas[i] - cost[i];
        if(curr_tank < 0){
            start_station = i + 1;
            curr_tank = 0;
        }
    }
    return total_tank >= 0 ? start_station : -1;
}

LC135 Candy

Problem

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:

1
2
3
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:

1
2
3
4
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.
Think
  • Approach 1

双数组法，left2right表示只关注每一个人左边的那个人的rating所求得的每个人的糖果数目的数组，right2left表示只关注每一个人右边的那个人的rating所求得的每个人的糖果数目的数组。

如果ratings[i] > ratings[i - 1]，则left2right[i] = left2right[i - 1] + 1，否则重置为1；

如果ratings[i] > ratings[i + 1]，则right2left[i] = right2left[i - 1] + 1，否则重置为1；

由于最终既要满足左边的rating的要求又要满足右边rating的要求，我们设置的糖果的数目只能多不能少，因此最终每个人的糖果的数目应当为max(left2right[i], right2left[i])。

  • Approach 2

Greedy

设置candies表示总共需要的糖果数目，up表示连续上升的rating的数目，down表示连续下降的rating的数目。

遍历数组，首先求得rating数组中当前元素与前一个元素的大小关系，设为new_slope。

如果old_slope > 0且new_slope = 0，或者old_slope < 0且new_slope >= 0，即表示如下两种情况：

1）之前的数组是上升的，而当前元素与前置元素相等

2）之前的数组是下降的，而当前元素大于等于前置元素

则可以计算这一部分的总糖果数目为(up * (up + 1)) / 2 + (down * (down + 1)) / 2 + max(up, down)，即计算1）中的前面的所有连续上升元素的总和，或是2）中前面先连续上升再连续下降的元素的总和

再根据new_slope的大小确定up++或者down++或者candies++；

最后加上最后一次的糖果数目，即(up * (up + 1)) / 2 + (down * (down + 1)) / 2 + max(up, down) + 1；

Code
  • Approach 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
int candy(vector<int>& ratings) {
    int res = 0;
    int n = ratings.size();
    vector<int> left2right(n, 1), right2left(n, 1);
    for(int i = 1; i < n; i++){
        if(ratings[i] > ratings[i - 1]){
            left2right[i] = left2right[i - 1] + 1;
        }
        else{
            left2right[i] = 1;
        }
    }
    for(int i = n - 2; i >= 0; i--){
        if(ratings[i] > ratings[i + 1]){
            right2left[i] = right2left[i + 1] + 1;
        }
        else{
            right2left[i] = 1;
        }
    }
    for(int i = 0; i < n; i++){
        res += max(left2right[i], right2left[i]);
    }
    return res;
}
  • Approach 2
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
int candy(vector<int>& ratings) {
    if(ratings.size() <= 1){
        return ratings.size();
    }
    int candies = 0;
    int up = 0, down = 0, old_slope = 0;
    for(int i = 1; i < ratings.size(); i++){
        int new_slope = 0;
        if(ratings[i] < ratings[i - 1]) new_slope = -1;
        else if(ratings[i] > ratings[i - 1]) new_slope = 1;
        
        if((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)){
            candies += (up * (up + 1)) / 2 + (down * (down + 1)) / 2 + max(up, down);
            up = 0;
            down = 0;
        }
        
        if(new_slope > 0){
            up++;
        }
        else if(new_slope < 0){
            down++;
        }
        else{
            candies++;
        }
        old_slope = new_slope;
    }
    candies += (up * (up + 1)) / 2 + (down * (down + 1)) / 2 + max(up, down) + 1;
    return candies;
}

Review

  • 对于可以用贪心算法解决的问题，主要有两种方式：

    1）当前元素和前一个元素的大小关系可以引申出不同的处理方式；

    2）当前元素和前面某一个元素的大小关系可以引申出不同的处理方式；

    一般情况下只需要遍历一遍数组就可以解决（前向或者后向）。

  • 不能用贪心算法的情况：

    1）中间结果会影响到最终的结果，而且不能通过跳过的方式解决；

    2）无法使用中间某一次的结果去计算后面的结果。