自己做的砍价网站,搭建网站费用是多少,优化软件下载,成都搜狗seo198. 打家劫舍
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个…198. 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 1
输入[1,2,3,1] 输出4 解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。 偷窃到的最高金额 1 3 4 。 示例 2
输入[2,7,9,3,1] 输出12 解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。 偷窃到的最高金额 2 9 1 12 。
方法一
// 动态规划
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];}
}这段代码是一个Java类实现了一个名为Solution的类其中包含一个名为rob的公共方法。这个方法使用动态规划算法来解决“打家劫舍”问题LeetCode上的第198题。这个问题描述的是你是一个小偷沿街有一排房子每个房子都有一定数量的钱。相邻的房子有防盗系统连接如果两间相邻的房子都被抢劫则会自动联系警察。给定一个整数数组 nums代表每间房子存放的金额返回在不触动警报的情况下你能抢劫到的最大金额。
在这个方法中
首先检查输入数组是否为空或长度为0如果是则返回0。如果数组长度为1直接返回该元素的值。初始化一个与输入数组长度相同的动态规划数组dp用于存储计算过程中的最大值。设置dp[0]和dp[1]的初始值。使用for循环遍历输入数组从下标2开始对于每个位置idp[i]等于dp[i - 1]和dp[i - 2] nums[i]中的较大值。最后返回dp数组的最后一个元素即为最大可抢金额。
这种方法的时间复杂度是O(n)空间复杂度也是O(n)其中n是输入数组的长度。不过可以进一步优化空间复杂度至O(1)只用两个变量来替代整个dp数组。
方法二
// 使用滚动数组思想优化空间
// 分析本题可以发现所求结果仅依赖于前两种状态此时可以使用滚动数组思想将空间复杂度降低为3个空间
class Solution {public int rob(int[] nums) {int len nums.length;if (len 0) return 0;else if (len 1) return nums[0];else if (len 2) return Math.max(nums[0],nums[1]);int[] result new int[3]; //存放选择的结果result[0] nums[0];result[1] Math.max(nums[0],nums[1]);for(int i2;ilen;i){result[2] Math.max(result[0]nums[i],result[1]);result[0] result[1];result[1] result[2];}return result[2];}
}这段代码同样实现了“打家劫舍”问题的解决方案但采用了滚动数组的思想来优化空间复杂度。在原版的动态规划解法中我们使用了一个与输入数组等长的数组来保存中间状态。然而通过观察动态转移方程我们可以发现当前状态只依赖于前两个状态因此没有必要保存所有的历史状态只需要保留最近的两个状态即可。
在这个优化版本中
首先进行边界条件判断处理输入数组为空、只有一个元素或只有两个元素的情况。创建一个长度为3的数组result来保存最近三个状态的值。初始化result[0]和result[1]的值。使用for循环遍历输入数组从下标2开始对于每个位置i更新result[2]为result[0] nums[i]和result[1]中的较大值。在每次迭代结束后将result[0]更新为上一轮的result[1]将result[1]更新为当前轮的result[2]。循环结束后result[2]即为最大可抢金额。
这种方法的空间复杂度被优化到了O(1)因为无论输入数组的长度如何都只需要常数级别的额外空间。时间复杂度仍然是O(n)其中n是输入数组的长度。这种优化在处理大规模数据时尤为重要因为它减少了内存使用提高了程序的效率。
方法三
// 进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
class Solution {public int rob(int[] nums) {if (nums.length 1) {return nums[0];}// 初始化dp数组// 优化空间 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];}
}这段代码进一步优化了“打家劫舍”问题的解决方案其目标是将空间复杂度降至最低。这里使用了一个长度为2的数组dp来存储动态规划过程中所需的最近两个状态而不是之前示例中长度为3的数组。这样做的原因是我们只需保存前两个状态的信息就能计算出下一个状态的值。
具体来说
首先处理边界情况当输入数组长度为1时直接返回该元素的值。初始化长度为2的dp数组dp[0]和dp[1]分别初始化为数组的前两个元素的值。声明一个变量res用于临时存储计算结果。使用for循环遍历输入数组从下标2开始对于每个位置i计算res为dp[0] nums[i]和dp[1]中的较大值。更新dp[0]和dp[1]的值dp[0]更新为上一轮的dp[1]dp[1]更新为当前计算得到的res。循环结束后dp[1]即为最大可抢金额作为最终结果返回。
这种方法的空间复杂度进一步优化到了O(1)因为我们只使用了固定大小的数组无论输入数组的长度如何。时间复杂度仍然是O(n)其中n是输入数组的长度。这种优化策略在处理大数据量时特别有效因为它极大地减少了内存消耗同时保持了较高的计算效率。
213. 打家劫舍 II
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 1
输入nums [2,3,2] 输出3 解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。 示例 2
输入nums [1,2,3,1] 输出4 解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。 偷窃到的最高金额 1 3 4 。 示例 3
输入nums [1,2,3] 输出3
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));}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;}
}这段代码是针对“打家劫舍 II”问题LeetCode上的第213题的一个解决方案。这个问题与原始的“打家劫舍”问题LeetCode上的第198题类似但是添加了一个额外的约束房子排列成一个圈这意味着第一间房子和最后一间房子是相邻的不能同时被抢劫。因此解决问题的方法略有不同。
在代码中
首先检查输入数组是否为空或长度为0如果是则返回0。如果输入数组长度为1直接返回该元素的值。然后调用robAction函数两次第一次考虑从第一个元素到最后一个元素前一个即不包括最后一个元素第二次考虑从第二个元素到最后一个元素即不包括第一个元素。这是因为如果抢劫了第一个房子就不能抢劫最后一个房子反之亦然。最后取这两次调用robAction函数返回值中的最大值作为最终结果因为我们要找的是所有可能情况下的最大抢劫金额。
robAction函数是一个辅助函数它接受一个整数数组nums以及开始和结束的索引然后使用滚动数组思想来计算从start到end不包括end的最大可抢金额。具体来说
初始化三个变量x、y和z分别表示前前一个状态、前一个状态和当前状态的最大可抢金额。使用for循环遍历数组从start到end - 1对于每个位置i更新y和z的值。y被更新为上一轮的z而z被更新为y和x nums[i]中的较大值。循环结束后z即为从start到end - 1的最大可抢金额。
这种方法的时间复杂度是O(n)空间复杂度是O(1)其中n是输入数组的长度。通过使用滚动数组思想我们能够有效地减少空间使用提高程序性能。
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 输入: root [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 3 1 7 输入: root [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 5 9
方法一
class Solution {// 1.递归去偷超时public int rob(TreeNode root) {if (root null)return 0;int money root.val;if (root.left ! null) {money rob(root.left.left) rob(root.left.right);}if (root.right ! null) {money rob(root.right.left) rob(root.right.right);}return Math.max(money, rob(root.left) rob(root.right));}这段代码是解决“打家劫舍 III”问题LeetCode上的第337题的一种尝试但使用了简单的递归方法这种方法虽然逻辑上正确但在实际运行时会遇到性能问题特别是在树的规模较大时可能会导致超时错误。
在这个问题中你需要在一个二叉树中最大化你的收益但你不能抢劫任何具有直接父子关系的节点。给定一棵以TreeNode表示的二叉树的根节点root返回你能获得的最大金额。
代码中定义的rob方法采用递归方式解决这个问题
首先检查根节点是否为空如果是则返回0因为没有节点可以抢劫。然后计算抢劫当前节点所能获得的金额money即当前节点的值加上其左子树和右子树的孙子节点所能提供的最大金额。接着递归地计算左子树和右子树不抢劫根节点所能提供的最大金额。最后返回money和左右子树不抢劫根节点所能提供的最大金额的较大值。
然而这种方法存在重复计算的问题即同一子树会被多次计算导致时间复杂度过高。为了优化这个问题可以使用动态规划或记忆化搜索的方法来避免重复计算将已经计算过的子树的结果缓存起来从而显著提高算法的效率。
例如可以使用一个哈希表或者在TreeNode结构中增加一个额外的字段来存储每个节点所能提供的最大金额这样就可以避免重复计算将时间复杂度降低到O(n)其中n是树中节点的数量。
方法二 // 2.递归去偷记录状态// 执行用时3 ms , 在所有 Java 提交中击败了 56.24% 的用户public int rob1(TreeNode root) {MapTreeNode, Integer memo new HashMap();return robAction(root, memo);}int robAction(TreeNode root, MapTreeNode, Integer memo) {if (root null)return 0;if (memo.containsKey(root))return memo.get(root);int money root.val;if (root.left ! null) {money robAction(root.left.left, memo) robAction(root.left.right, memo);}if (root.right ! null) {money robAction(root.right.left, memo) robAction(root.right.right, memo);}int res Math.max(money, robAction(root.left, memo) robAction(root.right, memo));memo.put(root, res);return res;}这段代码是对“打家劫舍 III”问题LeetCode上的第337题的优化解法通过引入记忆化搜索也称为备忘录方法来避免重复计算从而显著提高了算法的效率。
在代码中
定义了一个HashMap叫做memo用来存储已经计算过的节点及其对应的最大可抢金额以此来避免重复计算。rob1方法是对外提供的接口它接收树的根节点作为参数并返回最大可抢金额。它首先创建一个空的memo哈希表然后调用robAction方法来计算结果。robAction方法是核心的递归函数它接收一个树节点和memo哈希表作为参数。如果当前节点已经在memo中直接返回对应的值否则计算当前节点的最大可抢金额将结果存储到memo中并返回。
具体来说在robAction方法中
如果节点为空返回0。如果memo中已经存在当前节点的值直接返回该值。计算抢劫当前节点所能获得的金额money即当前节点的值加上其左子树和右子树的孙子节点所能提供的最大金额。递归地计算左子树和右子树不抢劫根节点所能提供的最大金额。将计算出的最大金额res存储到memo中并返回。
通过这种方式每个节点只被计算一次避免了原始递归方法中的大量重复计算从而将时间复杂度降低到O(n)其中n是树中节点的数量。空间复杂度主要由memo哈希表决定最坏情况下为O(n)即所有节点都需要被存储。这种优化使得算法在处理大规模数据时表现更佳避免了超时错误。
方法三 // 3.状态标记递归// 执行用时0 ms , 在所有 Java 提交中击败了 100% 的用户// 不偷Max(左孩子不偷左孩子偷) Max(右孩子不偷右孩子偷)// root[0] Math.max(rob(root.left)[0], rob(root.left)[1]) // Math.max(rob(root.right)[0], rob(root.right)[1])// 偷左孩子不偷 右孩子不偷 当前节点偷// root[1] rob(root.left)[0] rob(root.right)[0] root.val;public int rob3(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;}
}这段代码提供了一种解决“打家劫舍 III”问题LeetCode上的第337题的高效方法采用了状态标记的递归策略。这种方法不仅避免了重复计算还通过在每次递归调用中返回两个状态信息偷与不偷的最大金额从而简化了后续的决策过程。
在代码中
rob3方法是主入口它调用robAction1方法并返回最终的最大可抢金额。robAction1方法返回一个长度为2的数组其中第一个元素表示不抢劫当前节点时的最大金额第二个元素表示抢劫当前节点时的最大金额。robAction1方法实现了核心的递归逻辑它接收一个树节点作为参数递归地计算其左右子树的状态并基于这些状态计算当前节点的两个状态。
具体来说在robAction1方法中
如果节点为空返回一个全是0的数组。对于当前节点递归地获取其左右子树的状态信息。根据左右子树的状态信息计算当前节点的两个状态 res[0]表示不抢劫当前节点时的最大金额等于左右子树中偷与不偷的最大金额之和的较大值。res[1]表示抢劫当前节点时的最大金额等于当前节点的值加上左右子树不抢劫时的最大金额之和。
最后rob3方法返回robAction1方法返回的数组中两个元素的较大值即整个树的最大可抢金额。
这种方法的时间复杂度为O(n)空间复杂度也为O(n)其中n是树中节点的数量。相比于原始的简单递归方法这种方法通过避免重复计算显著提高了效率而且通过返回两个状态信息简化了决策过程使得代码更加简洁和易于理解。
