韩国的电商网站,旅游网站信息门户建设方案,成都网站设计制作公司,做网站必须用tomcat算法题
Leetcode 198.打家劫舍
题目链接:198.打家劫舍
大佬视频讲解#xff1a;198.打家劫舍视频讲解 个人思路 偷还是不偷#xff0c;这取决于前一个和前两个房是否被偷了#xff0c;这种存在依赖关系的题目可以用动态规划解决。 解法
动态规划
动规五部曲#xff1… 算法题
Leetcode 198.打家劫舍
题目链接:198.打家劫舍
大佬视频讲解198.打家劫舍视频讲解 个人思路 偷还是不偷这取决于前一个和前两个房是否被偷了这种存在依赖关系的题目可以用动态规划解决。 解法
动态规划
动规五部曲
1.确定dp数组dp table以及下标的含义
dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。 2.确定递推公式 决定dp[i]的因素就是第i房间偷还是不偷 如果偷第i房间那么dp[i] dp[i - 2] nums[i] 即第i-1房一定是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间那么dp[i] dp[i - 1]即考 虑i-1房 然后dp[i]取最大值即dp[i] max(dp[i - 2] nums[i], dp[i - 1]); 3.dp数组如何初始化 从递推公式dp[i] max(dp[i - 2] nums[i], dp[i - 1]);可以看出递推公式的基础就是dp[0] 和 dp[1] 从dp[i]的定义上来讲dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1]); 4.确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的所以是从前到后遍历 5.举例推导dp数组
以示例二输入[2,7,9,3,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(dp[0], nums[1]);//初始化for (int i 2; i nums.length; i) {dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]);//考虑是否偷当前的}return dp[nums.length - 1];}
}时间复杂度:O(n)遍历数组 空间复杂度:O( n);存储一个长度为n1的dp数组 滚动数组优化动规
// 进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
class Solution {public int rob(int[] nums) {if (nums.length 1) {return nums[0];}// 优化空间 dp数组只用2格空间 只记录与当前计算相关的前两个结果int[] dp new int[2];dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);int res 0;for (int i 2; i nums.length; i) { // 遍历res Math.max((dp[0] nums[i]) , dp[1] );dp[0] dp[1];dp[1] res;}return dp[1];}
} 时间复杂度:O(n)遍历数组 空间复杂度:O( 1);无使用其他大的额外空间 Leetcode 213.打家劫舍II
题目链接:213.打家劫舍II
大佬视频讲解213.打家劫舍II视频讲解 个人思路 这道题与上面那道题是类似的只不过这里的房屋成环了还是用动态规划解决。 解法
动态规划
对于题目中的数组成环的话主要有如下三种情况
情况一考虑不包含首尾元素 情况二考虑包含首元素不包含尾元素 情况三考虑包含尾元素不包含首元素 注意这里用的是考虑情况一二三是“考虑”的范围而具体房间偷与不偷交给递推公式去抉择 例如情况三虽然是考虑包含尾元素但不一定要选尾部元素 对于情况三取nums[1] 和 nums[3]就是最大的。而情况二 和 情况三 都包含了情况一了所以只考虑情况二和情况三就可以了。剩下的和上面那题198打家劫舍一样的了。 以下代码使用的了滚动数组去优化空间复杂度 class Solution {public int rob(int[] nums) {if (nums null || nums.length 0)//判空return 0;int len nums.length;//数组长度if (len 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));//情况2,3包括情况1}int robAction(int[] nums, int start, int end) {int x 0, y 0, z 0;for (int i start; i end; i) {y z;z Math.max(y, x nums[i]);x y;}return z;}
} 时间复杂度:O(n)遍历数组 空间复杂度:O(1);无使用其他大的额外空间 Leetcode 337.打家劫舍 III
题目链接:337.打家劫舍 III
大佬视频讲解337.打家劫舍 III视频讲解 个人思路
思路不清晰... 解法
动态规划 本题可以使用动态规划使用状态转移容器来记录状态的变化这里可以使用一个长度为2的数组记录当前节点偷与不偷所得到的的最大金钱。 这道题目算是树形dp的入门题目因为是在树上进行状态转移所以使用递归三部曲为框架其中融合动规五部曲的内容来解题。 递归加动规
1.确定递归函数的参数和返回值,dp数组dp table以及下标的含义 用一个节点记录偷与不偷的两个状态所得到的金钱那么返回值就是一个长度为2的数组即dp数组。 dp数组dp table以及下标的含义下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。 2.确定终止条件-dp数组的初始化
在遍历的过程中如果遇到空节点的话无论偷还是不偷都是0所以就返回 3.确定遍历顺序
首先明确的是使用后序遍历因为要通过递归函数的返回值来做下一步计算。
通过递归左节点得到左节点偷与不偷的金钱。
通过递归右节点得到右节点偷与不偷的金钱。 4.确定单层递归的逻辑 如果是偷当前节点那么左右孩子就不能偷即 val1 cur-val left[0] right[0]; 如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的所以val2 max(left[0], left[1]) max(right[0], right[1]); 最后当前节点的状态就是{val2, val1}; 即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱} 5.举例推导dp数组
以示例1为例dp数组状态如下图-用的后序遍历的方式推导
class Solution {// 状态标记递归public int rob(TreeNode root) {int[] res robAction(root);return Math.max(res[0], res[1]);}int[] robAction(TreeNode root) {int res[] new int[2];if (root null)return res;int[] left robAction(root.left);int[] right robAction(root.right);// 不偷Max(左孩子不偷左孩子偷) Max(右孩子不偷右孩子偷)res[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);// 偷左孩子不偷 右孩子不偷 当前节点偷res[1] root.val left[0] right[0];return res;}
} 时间复杂度:O(n)这里的n是树的高度 空间复杂度:O( n);输入数组大小 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
