Day 24

Best Time to Buy and Sell Stock II

1
2
3
4
5
6
7
8
9
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            res += Math.max(prices[i] - prices[i - 1], 0);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
func maxProfit(prices []int) int {
	res := 0
	for i := 1; i < len(prices); i++ {
		profit := prices[i] - prices[i-1]
		if profit > 0 {
			res += profit
		}
	}
	return res
}

Jump Game

Use range coverage method

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(i + nums[i], cover);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
func canJump(nums []int) bool {
	cover := 0
	for i := 0; i <= cover; i++ {
		if i+nums[i] > cover {
			cover = i + nums[i]
		}
		if cover >= len(nums)-1 {
			return true
		}
	}
	return false
}

Jump Game II

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 jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        int currCover = 0;
        int maxCover = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            maxCover = Math.max(i + nums[i], maxCover);
            if (maxCover >= nums.length - 1) {
                res++;
                break;
            }

            if (i == currCover) {
                currCover = maxCover;
                res++;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func jump(nums []int) int {
	if nums == nil || len(nums) == 0 || len(nums) == 1 {
		return 0
	}

	res, maxCover, currCover := 0, 0, 0
	for i := 0; i < len(nums); i++ {
		if (i + nums[i]) > maxCover {
			maxCover = i + nums[i]
		}

		if maxCover >= (len(nums) - 1) {
			res++
			break
		}

		if i == currCover {
			currCover = maxCover
			res++
		}
	}
	return res
}