力扣打卡----打家劫舍

今天在做力扣题目的时候，看到了这个题目，然后第一眼就被这个名字吸引了，哈哈哈哈，很新奇（没有别的意思）

那么接下来我将根据我看了某位大佬的解答之后一个一个的自己来解答这三个题目

1. 打家劫舍Ⅰ

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

这个题目可以算是属于动态规划的题目了，也就是我需要得到最优解，那就简单回顾一下什么是动态规划

所谓动态规划就是将问题划分为子问题然后求解，他相比于分治法的区别在于分治法的子问题之间是相互独立的但是他不是，同时动态规划解决了重叠子问题的情况。

动态规划适用于重叠子问题和最优子结构的情况。

详细分析

 

 变量说明

那么有了上面一个简单的分析，我们来看看我们需要什么元素？首先我们知道我们需要一个dp[i]表示到达元素i的时候的最大值

然后我们需要一个变量result来表示我们最后的值，因为我们的dp是用来存储当前的值的，一直会变动，我们就需要一个result来存储每次dp[i]计算完之后对比之下的最大值。

代码展示

class Solution {
    public int rob(int[] nums) {
        //首先如果数组只有一个元素的时候我们的直接返回，同时我们在这里也可以考虑不含有元素的情况
        if(nums.length<=1) return nums.length==0?0:nums[0];
        //我们需要一个变量来存储到达i的时候我们当前的最大值
        int[] dp=new int[nums.length];
        //我们需要result来存储到达当前位置所有情况下的最大值
        int result=Math.max(nums[0],nums[1]);

        for(int i=0;i<nums.length;i++)
        {
            if(i==0)  { dp[0]==nums[0]; continue; }
            if(i==1)  { dp[1]==Math.max(nums[0],nums[1]); continue;}
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
            result=Math.max(dp[i],result);
        }      
        return result; 
    }

    }

2. 打家劫舍Ⅱ

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

详细分析

这个题目相比于上一个题目的不同之处在于它是连起来的，也就是说我们选头就不能选尾，选尾就不能选头。

所以在这里我们可以分为这几种情况

①选头不选尾

②选尾不选头

③不选头也不选尾

然后我们只需要调用javaAPI就可以得到我们想要的情况，我们使用Arrays.copyOfRange()函数来实现

代码展示

class Solution {
    public int rob(int[] nums) {
        //首先我们判断边界条件，还是会存在当只有一个元素或者没有元素的时候的情况
        if(nums.length<=1) return nums.length==0?0:nums[0];

        //然后我们来实现选头不选尾
        int []nums1=Arrays.copyOfRange(nums,0,nums.length-1);
        int []nums2=Arrays.copyOfRange(nums,1,nums.length);
        int []nums3=Arrays.copyOfRange(nums,1,nums.length-1);
        return Math.max(helper(nums1),Math.max(helper(nums2),helper(nums3)));
    }
    public int helper(int nums[]){
       if(nums.length<=1) return nums.length==0?0:nums[0];
       //这里就像之前的操作一样
       //首先我们需要一个变量来存储到了第i个位置之后的最大值
       int []dp=new int[nums.length];
       int result=Math.max(nums[0],nums[1]);
       for(int i=0;i<nums.length;i++)
        {
            if(i==0) {dp[i]=nums[0]; continue;}
            if(i==1) {dp[i]=Math.max(nums[0],nums[1]); continue;}
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
            result=Math.max(result,dp[i]);
        }
    return result;       
    }
}

3.打家劫舍Ⅲ

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

 详细分析

在这里我们可以设置一个二元数组，表示选择和不选择，因为他需要的是选择一个点的时候据不能选择和他相邻的点，比如上面的我们选择3就不能选择它的两个子节点

所以我们要怎么做？

我们可以分别选择当前节点和不选择当前节点

如果我们选择当前节点的话，我们就不能选择他的两个子节点，但是如果我们不选择当前节点，我们是可以选择当前节点的两个子节点的（并且是可以同时选择，因为他们一定不相连）

代码展示

/**
 * 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) {

        //res 二元数组        res 0   res1 
        //res 0    不抢劫当前节点的最大值
        //res 1     抢劫当前节点的最大值
        int[] res = dp(root);

        return Math.max(res[0], res[1]);
    }

    /*
        返回一个res
        res 
    */
    public int[] dp(TreeNode root){
        if(root == null)    return new int[]{0,0};
        int[] left  = dp(root.left);
        int[] right = dp(root.right);

        int rob     = root.val + left[0] + right[0];
        int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]) ;

        return new int[]{not_rob, rob};
    }
}