个人技术分享

LeetCode 198 打家劫舍

题目链接：198. 打家劫舍 - 力扣（LeetCode）

【解题思路】

• 1.确定dp数组含义

  • dp[i]:考虑下标i能偷的最大的金币数dp[i]

  • 最终返回的是dp[nums.size-1]

• 2.确定递推公式

  • 偷i

    • dp[i-2]+nums[i]

  • 不偷i

    • dp[i-1]

  • dp[i] = max(dp[i-2]+nums[i],dp[i-1])

• 3.dp数组初始化

  • dp[0]=nums[0]

    • 只有一个房间有金币时，必偷

  • dp[1] = max(nums[0],nums[1])

    • 因为相邻房间只能偷一个，所以得选前两个之中最大的那个偷

• 4.确定遍历顺序

  • 因为0，1已经初始化，所以要从2开始遍历

  • 从小到大遍历，因为当前状态需要由前面推导

• 5.打印dp数组

  • 检查是否按照我们的想法进行状态转移

【解题步骤】

• 1.如果nums为空，或者nums的长度为0，return0

• 2.如果nums的长度为1，返回nums[0]

• 3.创建一个dp数组，长度为nums的长度

• 4.初始化dp数组

• 5.遍历

• 7.返回dp[nums.length-1]

【代码部分】

class Solution {
    public int rob(int[] nums) {
		if(nums == null || nums.length == 0)return 0;
		if(nums.length == 1)return nums[0];
		int[] dp = new int[nums.length];
		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];
    }
}

LeetCode 213 打家劫舍II

题目链接：213. 打家劫舍 II - 力扣（LeetCode）

【解题思路】

• 1.确定dp数组含义

  • dp[i]:考虑下标i能偷的最大的金币数dp[i]

  • 最终返回的是dp[nums.size-1]

• 2.确定递推公式

  • 偷i

    • dp[i-2]+nums[i]

  • 不偷i

    • dp[i-1]

  • dp[i] = max(dp[i-2]+nums[i],dp[i-1])

• 3.dp数组初始化

  • dp[0]=nums[0]

    • 只有一个房间有金币时，必偷

  • dp[1] = max(nums[0],nums[1])

    • 因为相邻房间只能偷一个，所以得选前两个之中最大的那个偷

• 4.确定遍历顺序

  • 因为0，1已经初始化，所以要从2开始遍历

  • 从小到大遍历，因为当前状态需要由前面推导

• 5.打印dp数组

  • 检查是否按照我们的想法进行状态转移

• 可以将打家劫舍I的代码封装成函数，再在主函数截取首尾两个数组，传入函数，取其最大值

【解题步骤】

• 主函数

  • 1.如果nums.size==0,返回0

  • 2.如果nums.size==1,返回nums[0]

  • 3.定义一个res1存放不包含尾元素的数组传入函数后得出的值

  • 4.定义一个res2存放不包含首元素的数组传入函数后得出的值

  • 5.返回res1和res2比较最大的那个

• 打家劫舍I函数

  • 1.如果nums为空，或者nums的长度为0，return0

  • 2.如果nums的长度为1，返回nums[0]

  • 3.创建一个dp数组，长度为nums的长度

  • 4.初始化dp数组

  • 5.遍历

  • 7.返回dp[nums.length-1]

【代码部分】

class Solution {
    public int rob(int[] nums) {
		if(nums.length == 0)return 0;
		if(nums.length == 1)return nums[0];
		int res1 = robRange(nums,0,nums.length - 2);
		int res2 = robRange(nums,1,nums.length - 1);
		return Math.max(res1,res2);
    }

	public int robRange(int[] nums,int start,int end) {
		if(end == start)return nums[start];
		int[] dp = new int[nums.length];
		dp[start] = nums[start];
		dp[start+1] = Math.max(nums[start],nums[start+1]);
		for(int i = start+2 ; i <= end ; i++){
			dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
		}
		return dp[end];
	}
}

LeetCode 337 打家劫舍III

题目链接：337. 打家劫舍 III - 力扣（LeetCode）

【解题思路】

• 1.确定dp数组含义

  • dp[i]:考虑下标i能偷的最大的金币数dp[i]

• 2.确定递推公式

  • 用递归

    • 1.确定参数和返回值

      • 返回值：数组

      • 参数：根节点cur

    • 2.确定终止条件

      • 如果当前遍历的值为空，return初始化为0的数组

    • 3.确定单层递归逻辑

      • 递归调用函数，用leftdp和rightdp接收

      • 定义变量：

        • val1 = cur.val+leftdp[0]+rightdp[0]

          • 偷当前遍历节点

        • val2 = max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1])

          • 不偷当前遍历节点

        • return{val2,val1}

• 4.确定遍历顺序

  • 已经在递归中实现

• 5.打印dp数组

  • 检查是否按照我们的想法进行状态转移

【解题步骤】

• 主函数

  • 1.定义一个res，接收递归函数返回的值

  • 2.返回res[0]和res[1]的最大值

• 递归函数

  • 1.定义一个res数组，长度为2

  • 2.如果传入节点为空，直接返回res{0,0}

  • 3.向左递归

  • 4.向右递归

  • 5.res[1]=当前节点加上左右节点不选

    • res[1]为选当前节点的状态

  • 6.res[0]=前两个左节点的最大值加上前两个右节点的最大值

    • res[0]为不选当前节点的状态

【代码部分】

class Solution {
    public int rob(TreeNode root) {
		int[] res = robTree(root);
		return Math.max(res[0],res[1]);
    }

	int[] robTree(TreeNode cur){
		int res[] = new int[2];
		if(cur == null)return res;

		int[] left = robTree(cur.left);
		int[] right = robTree(cur.right);

		res[1]=cur.val + left[0] + right[0];
		res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
		return res;
	}
}