呼和浩特网站建设费用,html编辑器怎么用,冀州网站建设代理,wordpress音乐外链LeetCode:
198. 打家劫舍 - 力扣#xff08;LeetCode#xff09;
1.思路
边界思维#xff0c;只有一个元素和两个元素的初始化考虑 当元素数大于3个时#xff0c; 逆向思维#xff0c;是否偷最后一个元素#xff0c;倒序得出递推公式dp[i] Math.max(dp[i - 1], dp[i …LeetCode:
198. 打家劫舍 - 力扣LeetCode
1.思路
边界思维只有一个元素和两个元素的初始化考虑 当元素数大于3个时 逆向思维是否偷最后一个元素倒序得出递推公式dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]);前者不偷后者偷两者取较大值。
2.代码实现 1// 递推公式逆向思考可以得出2class Solution {3 public int rob(int[] nums) {4 int len nums.length;5 if (len 0) {6 return 0;7 } else if (len 1) {8 return nums[0];9 }
10
11 int[] dp new int[len];
12 dp[0] nums[0];
13 dp[1] Math.max(dp[0], nums[1]);
14
15 for (int i 2; i len; i) {
16 dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]);
17 }
18 return dp[len - 1];
19 }
20}
21// 滚动数组有些小坑得踩一下
22class Solution {
23 public int rob(int[] nums) {
24 int len nums.length;
25
26 if (len 0) {
27 return 0;
28 } else if (len 1) {
29 return nums[0];
30 } else if (len 2) {
31 return Math.max(nums[0], nums[1]);
32 }
33
34 int[] result new int[3];
35 result[0] nums[0];
36 result[1] Math.max(nums[0], nums[1]);
37
38 for (int i 2; i len; i) {
39 result[2] Math.max(result[0] nums[i], result[1]);
40
41 result[0] result[1];
42 result[1] result[2];
43 }
44 return result[2];
45 }
46}3.复杂度分析
时间复杂度O(n). 空间复杂度O(1).
LeetCode:
213. 打家劫舍 II - 力扣LeetCode
1.思路
考虑首元素和不考虑首元素即可将环形进行拆解为两个线性数组取两者之间的较大值即可
2.代码实现 1class Solution {2 public int rob(int[] nums) {3 if (nums null || nums.length 0) {4 return 0;5 }67 int len nums.length;8 if (len 1) {9 return nums[0];
10 }
11 return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
12 }
13
14 int robAction(int[] nums, int start, int end) {
15 int x 0, y 0, z 0;
16 for (int i start; i end; i) {
17 y z;
18 z Math.max(y, x nums[i]); //
19 x y;
20 }
21 return z;
22 }
23}3.复杂度分析
时间复杂度O(n). 空间复杂度O(1).
LeetCode:
337. 打家劫舍 III - 力扣LeetCode
1.思路
分两种情况选择根节点和不选根节点分别计算两种情况的较大值并选择两者之间的较大值存入map集合中返回结果。
2.代码实现 1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val val;
11 * this.left left;
12 * this.right right;
13 * }
14 * }
15 */
16class Solution {
17 public int rob(TreeNode root) {
18 // 创建一个 Map 来保存已经计算过的节点的最大金额
19 MapTreeNode, Integer map new HashMap();
20 // 调用递归方法计算能够偷取的最大金额
21 return robAction(root, map);
22 }
23 // 构建递归方法计算以 root 为根节点的子树能够偷取的最大金额
24 int robAction(TreeNode root, MapTreeNode, Integer map) {
25 // 如果 root 为空返回 0
26 if (root null) {
27 return 0;
28 }
29 // 如果map中已经存在以 root 为根节点的子树的最大金额直接返回该值
30 if (map.containsKey(root)) {
31 return map.get(root);
32 }
33 // money 来保存以 root 为根节点的子树能够偷取的最大金额
34 int money root.val;
35 // 左判断 root 的左子节点是否存在存在则计算左子节点的左子节点和右子节点的最大金额并加到 money 中
36 if (root.left ! null) {
37 money robAction(root.left.left, map) robAction(root.left.right, map);
38 }
39 // 右同理
40 if (root.right ! null) {
41 money robAction(root.right.left, map) robAction(root.right.right, map);
42 }
43 // 结果从选择根节点和不选择根节点之中选取最大值
44 int res Math.max(money, robAction(root.left, map) robAction(root.right, map));
45 // 将结果res 存入map中以便下次使用
46 map.put(root, res);
47 return res;
48 }
49}3.复杂度分析
时间复杂度O(n). 空间复杂度O(logn).
