文章目录
- 前言
- 一、打家劫舍（力扣198）【相邻两间房不能偷】
- 二、打家劫舍 II（力扣213）【围成一圈 相邻两间房不能偷】
- 三、打家劫舍 III（力扣337）【树形DP】
- 每日一题day81：链表中的下一个更大节点（力扣1019）
前言
1、打家劫舍
2、打家劫舍Ⅱ
3、打家劫舍Ⅲ
4、链表中的下一个更大节点
一、打家劫舍（力扣198）【相邻两间房不能偷】
分析：
注意：dp[i]表示第i间房时，此时已经偷到的最大金额
每一间房都有偷和不偷两种情况
偷：需要确保不触发警报 dp[i-2]+nums[i]
不偷：dp[i-1]；
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
class Solution {
public int rob(int[] nums) {
int[]dp = new int[nums.length];
if(nums.length ==1){
return nums[0];
}
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for( int i=2;i<nums.length;i++){
//前一间没偷 前一间偷了
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
}
二、打家劫舍 II（力扣213）【围成一圈 相邻两间房不能偷】
分析：
分为左右两个部分 例如 1，2，3
可以分为左边：1，2；
右边：2，3；
对于左右两边分别进行1的操作，最后求最大值即可。
为什么要分两边： 原因在于首尾相连，如果包含首元素，不管偷不偷首元素，都不能包含尾元素。
同理 如果包含尾元素，不管偷不偷尾元素，都不能包含首元素。
需要额外处理 nums.length==2时的情况，因为不会执行右半部分，所以直接返回前两个元素的较大值即可
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
class Solution {
public int rob(int[] nums) {
if(nums.length==1){
return nums[0];
}
int[] dp = new int[nums.length];
int[] dp2 = new int[nums.length];
dp[0] = nums[0];
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
dp[1] = Math.max(nums[0],nums[1]);
//分为左右两个部分
//左半部分
for(int i=2;i<nums.length-1;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
//右半部分
dp2[1] = nums[1];
dp2[2] = Math.max(nums[1],nums[2]);
for(int j=3;j<nums.length;j++){
dp2[j] = Math.max(dp2[j-2]+nums[j],dp2[j-1]);
}
return Math.max(dp[nums.length-2],dp2[nums.length-1]);
}
}
三、打家劫舍 III（力扣337）【树形DP】
分析：
注意选清楚二叉树的遍历方式，
其次，dp[]数组只需要记录当前结点偷与不偷的两个状态
dp[]数组不需要记录是哪一个结点，交给递归去做
注意：当不偷根节点时，左右结点不是必须要偷，左右结点也可以不偷，取决于左右节点偷的值大还是不偷的值大。
//偷根节点
val[0] = current.val+left[1]+right[1];
//不偷根节点
val[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = new int[2];
res = robTree(root);
return Math.max(res[0],res[1]);
}
public int[] robTree(TreeNode current){
int[] val = new int[2];
if(current == null) return val;
int[] left = new int[2];
int[] right = new int[2];
left = robTree(current.left);
right = robTree(current.right);
//偷根节点
val[0] = current.val+left[1]+right[1];
//不偷根节点
val[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
return val;
}
}
每日一题day81：链表中的下一个更大节点（力扣1019）
分析：
典型单调栈
public static int[] nextLargerNodes(ListNode head) {
//单调栈？
//求链表长度
if(head == null) return null;
ListNode cur = head;
int size =1;
while(cur.next!=null){
cur = cur.next;
size++;
}
int[] temp = new int[size];
int[] res = new int[size];
cur = head;
int i = 0;
while(cur!=null){
temp[i] = cur.val;
cur = cur.next;
i++;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int j=1;j<size;j++){
//栈内是递增的
if(!stack.isEmpty() && temp[stack.peek()]>=temp[j]){
//直接入栈即可
stack.push(j);
}
while(!stack.isEmpty() && temp[stack.peek()]<temp[j]){
i = stack.pop();
res[i] = temp[j];
}
stack.push(j);
}
return res;
}
