"122. The Best Time to Buy and Sell Stocks II"
You are given an integer array prices , where prices[i] represents the price of a certain stock on day i.
On each day, you can decide whether to buy and/or sell stocks. You can hold no more than one share of stock at any one time. You can also buy first and sell later on the same day.
Returns the maximum profit you can get.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), this trade can make profit = 5 - 1 = 4. Then, buy on the 4th day (stock price = 3) and sell on the 5th day (stock price = 6), this transaction can make a profit = 6 - 3 = 3 . The total profit is 4 + 3 = 7 .
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the transaction can make profit = 5 - 1 = 4. The total profit is 4 .
Example 3:
Input: prices = [7,6,4,3,1] output: 0 Explanation: In this case, the transaction cannot obtain a positive profit, so the maximum profit can be obtained by not participating in the transaction, and the maximum profit is 0.
//greedy: // Greedy thinking class Solution { public int maxProfit(int[] prices) { int result = 0; for (int i = 1; i < prices.length; i++) { result += Math.max(prices[i] - prices[i - 1], 0); } return result; } } //Dynamic programming: class Solution { // dynamic programming public int maxProfit(int[] prices) { // [Number of days][Whether to hold stocks] int[][] dp = new int[prices.length][2]; // base case dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { // dp formula dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[prices.length - 1][0]; } }
55. Jumping Game
Given an array nums of non-negative integers, you are initially at the first index of the array.
Each element in the array represents the maximum length you can jump at that position.
Determine whether you can reach the last subscript.
Example 1:
Input: nums = [2,3,1,1,4] Output: true Explanation: You can jump 1 step first, from subscript 0 to subscript 1, and then jump 3 steps from subscript 1 to the last subscript.
Example 2:
Input: nums = [3,2,1,0,4] output: false Explanation: No matter what, the position with subscript 3 will always be reached. But the maximum jump length for this subscript is 0 , so it is never possible to reach the last subscript.
class Solution { public boolean canJump(int[] nums) { if (nums.length == 1) { return true; } //Coverage, the initial coverage should be 0, because the following iterations start from subscript 0 int coverRange = 0; //Update max coverage in coverage for (int i = 0; i <= coverRange; i++) { coverRange = Math.max(coverRange, i + nums[i]); if (coverRange >= nums.length - 1) { return true; } } return false; } }
45. Jumping Game II
Given a zero-indexed integer array nums of length n. The initial position is nums[0].
Each element nums[i] represents the maximum length to jump forward from index i. In other words, if you are at nums[i], you can jump to any nums[i + j]:
- 0 <= j <= nums[i]
- i + j < n
Returns the minimum number of hops to reach nums[n - 1]. Generated test cases can reach nums[n - 1].
Example 1:
enter: nums = [2,3,1,1,4] output: 2 Explanation: The minimum number of hops to get to the last position is 2. Jump from index 0 to index 1, jump 1 step and jump 3 step to the last position of the array.
Example 2:
Input: nums = [2,3,0,1,4] output: 2
// version one class Solution { public int jump(int[] nums) { if (nums == null || nums.length == 0 || nums.length == 1) { return 0; } //Record the number of jumps int count=0; //Current maximum coverage area int curDistance = 0; //largest coverage area int maxDistance = 0; for (int i = 0; i < nums.length; i++) { //Update the largest coverage area within the coverage area maxDistance = Math.max(maxDistance,i+nums[i]); //Indicates the current step, skip another step to reach the end if (maxDistance>=nums.length-1){ count++; break; } //When reaching the maximum area currently covered, update the maximum area that can be reached in the next step if (i==curDistance){ curDistance = maxDistance; count++; } } return count; } } // version two class Solution { public int jump(int[] nums) { int result = 0; // The farthest distance subscript currently covered int end = 0; // Subscript of the furthest distance covered in the next step int temp = 0; for (int i = 0; i <= end && end < nums.length - 1; ++i) { temp = Math.max(temp, i + nums[i]); // The number of changes in the reachable position is the number of jumps if (i == end) { end = temp; result++; } } return result; } }