电话语音聊天网站建设多少钱,网站推广做百度还是360,大型门户网站开发公司,网站优化就是seo198. 打家劫舍#xff1a;
题目链接 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报…198. 打家劫舍
题目链接 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 :
输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。解答
class Solution {public int rob(int[] nums) {int[] dp new int[nums.length1];if(nums.length1)return nums[0];if(nums.length2)return Math.max(nums[0],nums[1]);dp[0] 0;dp[1] nums[0];dp[2] nums[1];for (int i 3; i nums.length ; i) {dp[i] Math.max(dp[i-3],dp[i-2]) nums[i-1];}return Math.max(dp[nums.length],dp[nums.length-1]);}
}算法总结
打家劫舍Ⅰ问题比较基础就是考虑每个之间的间隔我们取i-3和i-2之间更大的值将其加入dp数组中即可。
213. 打家劫舍 II
题目链接 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 :
输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。解答
class Solution {public int rob(int[] nums) {if(nums.length1)return nums[0];if(nums.length2)return Math.max(nums[0],nums[1]);int max1 getrob(Arrays.copyOfRange(nums,0,nums.length-1));int max2 getrob(Arrays.copyOfRange(nums,1,nums.length));return Math.max(max1,max2);}public static int getrob(int[] nums) {int[] dp new int[nums.length1];if(nums.length1)return nums[0];if(nums.length2)return Math.max(nums[0],nums[1]);dp[0] 0;dp[1] nums[0];dp[2] nums[1];for (int i 3; i nums.length ; i) {dp[i] Math.max(dp[i-3],dp[i-2]) nums[i-1];}return Math.max(dp[nums.length],dp[nums.length-1]);}
}算法总结
打家劫舍Ⅱ涉及到头尾之间的问题则本题我们可以考虑去掉头去掉尾不认识对一个数组中0n-2进行打劫Ⅰ的思路处理再对1n-1做同样的处理处理结果进行一次最大值比较就是最终的结果。
337. 打家劫舍 III
题目链接 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。
示例 :
输入: root [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 3 1 7解答
class Solution {public int rob(TreeNode root) {int[] res robAction1(root);return Math.max(res[0], res[1]);}int[] robAction1(TreeNode root) {int res[] new int[2];if (root null)return res;int[] left robAction1(root.left);int[] right robAction1(root.right);res[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);res[1] root.val left[0] right[0];return res;}
}算法总结
打家劫舍Ⅲ是一道树形的动态规划问题根据题意我们可以知道我们要判断每个结点是否可以遍历则我们可以设置 int res[] new int[2]; 作为记录取或不取的最大值先将这个树遍历到叶子结点再从下开始往上遍历最后返回res[0]和res[1]
