网站开发视频压缩上传,wordpress 插件如何使用,网站建设公司是什么意思,青浦网络公司网站①、打家劫舍 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。 给定一个代表每个房…①、打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 事例 输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。 思路 使用动态规划对于每个房间只有两种选择偷还是不偷若选择偷的话则只能加上前两个房间偷取的最大金额即上一个房间不偷若不偷则为从第一个房间到前一个房间偷取的最大金额两者取最大值即可。
动态规划 dp定义及含义dp[j]表示从第一个房间到第j个房间能偷取的最大金额 状态转移方程dp[j] Math.max(dp[j - 1],dp[j - 2] nums[j]) 初始化dp[0] nums[0] 只能投第一个房间 dp[1] Math.max(nums[0],num[1])前两个房间就选个钱多的。 遍历顺序房间从小到大遍历 dp[nums.length - 1]即为答案。
代码
public int rob(int[] nums) {if(nums.length 1) return nums[0];int[] dp new int[nums.length];dp[0] nums[0];dp[1] nums[0] nums[1] ? nums[0] : nums[1];for(int i 2;i dp.length;i){dp[i] Math.max(dp[i - 2] nums[i],dp[i - 1]);}return dp[nums.length - 1];}
②、打家劫舍Ⅱ 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 事例 输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。 思路 与上一题类似只是首尾多了个环形判断需要进行解环操作。可以将环截成两个链如对第一家到最后第二家进行打劫然后再从头开始对第二家到最后一家进行打劫最后返回两个打劫的最大值即可。打劫代码跟上题一致。
代码
public int rob(int[] nums) {if(nums.length 1) return nums[0];return Math.max(robOne(nums,0,nums.length - 2),robOne(nums,1,nums.length - 1));}public int robOne(int[] nums,int left,int right) {if(left right) return nums[left];int[] dp new int[right - left 1];dp[0] nums[left];dp[1] Math.max(nums[left],nums[left 1]);for(int i 2;i dp.length;i){dp[i] Math.max(dp[i - 2] nums[left i],dp[i - 1]);}return dp[dp.length - 1];}
③、打家劫舍Ⅲ 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。 除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 事例 输入: root [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 3 1 7思路 这道题的社区结构变成了树形对于树我们得选择一种遍历方式打劫该结点与否取决于左右孩子是否打劫的金额最大值故可以采用递归返回值为处理左右孩子的数据以便后续判断故选择后序遍历。
递归 使用后序遍历 返回值int[]约定int[0]为该不打劫该节点int[1]为打劫该结点返回参数可以直接给根结点构造成新参数层层返回到最终结果。 最后返回root[0],root[1]中的最大值即为答案。
动态规划 dp定义及含义dp其实就是递归函数的返回值其中dp[0]表示不打劫当前结点的最大金额dp[1]表示打劫当前结点的最大金额。 状态转移方程构造dp数组dp[0] Math.max(leftDp[0],left[1]) Math.max(rightDp[0],rightDp[1])dp[1] root.val leftDp[0] rightDp[1] 初始化遇到空节点时返回new int[]{0,0} 遍历顺序后序遍历因为根节点是否打劫需要根据左右孩子是否打劫 最终返回的值为根节点是否打劫的最大金额返回其中的最大值即可。
代码
public int rob(TreeNode root) {int[] resDp dpRoot(root);int res Math.max(resDp[0],resDp[1]);return res;}public int[] dpRoot(TreeNode root){if(root null) return new int[]{0,0};int[] leftDp dpRoot(root.left);int[] rightDp dpRoot(root.right);int value1 root.val leftDp[0] rightDp[0];int value0 Math.max(leftDp[0],leftDp[1]) Math.max(rightDp[0],rightDp[1]);return new int[]{value0,value1};}
参考代码随想录 (programmercarl.com)
