1-leetcode121. 买卖股票的最佳时机
注意：×
- Labuladong的套路太厉害了，分析的很清晰
- 状态转移方程
public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];for (int i = 0; i < n; i++) {if (i-1 == -1){// base casedp[i][0] = 0;dp[i][1] = -prices[i];continue;}dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = Math.max(dp[i-1][1], - prices[i]);}return dp[n-1][0];}
2-leetcode55. 跳跃游戏
注意：√
- 自己写的，debug一下过了，注意
dp[i+j+1]部分，j从0开始，下标不对，注意调整 - Labuladong的方法很巧妙的转化
这道题表面上不是求最值，但是可以改一改：请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回 true，否则返回 false。所以解题关键在于求出能够跳到的最远距离。
public boolean canJump(int[] nums) {int n = nums.length;boolean[] dp = new boolean[n];dp[n-1] = true;for (int i = n-2; i >= 0; i--) {for (int j = 0; j < nums[i]; j++) {if (i + j < n){dp[i] = (dp[i] || dp[i+j+1]);if (dp[i] == true){break;}} else {break;}}}return dp[0];}public boolean canJump(int[] nums) {int n = nums.length;int farthest = 0;for (int i = 0; i < n - 1; i++) {// 不断计算能跳到的最远距离farthest = Math.max(farthest, i + nums[i]);// 可能碰到了 0，卡住跳不动了if (farthest <= i) {return false;}}return farthest >= n - 1;}
3-leetcode45. 跳跃游戏 II
注意：√
- 自己写的，依旧一趟过，debug了一下，注意
i+j >= n判断一下防止越界
public int jump(int[] nums) {int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, -1);dp[n-1] = 0;for (int i = n-2; i >= 0; i--) {for (int j = nums[i]; j > 0; j--) {if (i+j >= n || dp[i+j] == -1){continue;}if (dp[i] == -1){dp[i] = dp[i+j] + 1;} else {dp[i] = Math.min(dp[i], dp[i+j] + 1);}}}return dp[0];}
4-leetcode763. 划分字母区间
注意：×
- 思路比较重要，数组的复写得到字符的最后出现位置
- for里面发现end到头也就到这里了，那就输出结果，重置
start end
public List<Integer> partitionLabels(String s) {int[] alpha = new int[26];for (int i = 0; i < s.length(); i++) {alpha[s.charAt(i) - 'a'] = i;}List<Integer> res = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {end = Math.max(end, alpha[s.charAt(i) - 'a']);if (i == end) {res.add(end - start + 1);start = end + 1;end = 0;}}return res;}
