一、连续的房子不能抢
题目
You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money stashed, the only constraint stopping you
from robbing each of them is that adjacent houses have security system connected
and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house,
determine the maximum amount of money you can rob tonight without alerting the police.
给定一个非负数组表示每间房子的现金数量，确定在不惊动警察的情况下最多可以抢多少钱。
题目解析
动态规划，递推规则：
到当前房子为止可以抢到的最大金额是不抢上一个房子，抢当前房子 和 抢了上一个房子，不抢当前房子的最大值
max_cur = max( prev_max, prev_prev_max + cur )
或者表示为
max_cur = max( cur_rob, cur_not_rob)
复杂度分析
时间复杂度都是O(n)，空间复杂度都是O(1)
方法一实现
class Solution {
public int rob(int[] nums) {
int prev_prev_max = 0, prev_max = 0, cur_max = 0;
for(int num : nums){
cur_max = Math.max(prev_max, prev_prev_max + num);
prev_prev_max = prev_max;
prev_max = cur_max;
}
return cur_max;
}
}
方法二实现
class Solution {
public int rob(int[] nums) {
int prev_no = 0, prev_yes = 0;
for(int num : nums){
int tmp = prev_no;
prev_no = Math.max(prev_yes, prev_no); //这里的是cur的意思了
prev_yes = tmp + num;
}
return Math.max(prev_no, prev_yes);
}
}
二、连续的房子不能抢 + 街道是一个环
题目
After robbing those houses on that street, the thief has found himself a new place for his thievery
so that he will not get too much attention.
This time, all houses at this place are arranged in a circle.
That means the first house is the neighbor of the last one.
Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house,
determine the maximum amount of money you can rob tonight without alerting the police.
给定一个首位相接的数组，里面包含每个房间的金额，不能偷相邻房间的金额，则能偷到的最大金额是多少
题目解析
因为首位相接，所以首选了尾不能选，尾选了首不能选，就是在0-n-1和1-n上偷取更大的结果。
复杂度分析
时间复杂度为O(n)，空间复杂度为O(1)
实现
public int rob(int[] nums) {
//分两种情况，第一个被选择了,就是从1到n-1, 和第一个没被选择是2到n
int n = nums.length;
if(n == 0) return 0;
if(n == 1) return nums[0];
return Math.max(rob(nums, 0, n-1), rob(nums, 1, n));
}
public int rob(int[] nums, int start, int end){
int include = 0, exclude = 0;
for(int i = start; i < end; ++i){
int in = include, ex = exclude;
include = ex + nums[i];
exclude = Math.max(in, ex); //注意：不包括这一轮则取，上一轮最大的
}
return Math.max(include, exclude);
}
三、连续的房子不能抢 + 街道是一颗二叉树
题目
The thief has found himself a new place for his thievery again.
There is only one entrance to this area, called the "root."
Besides the root, each house has one and only one parent house.
After a tour, the smart thief realized that "all houses in this place forms a binary tree".
It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
题目表示街道是二叉树，连接的两个房屋不能同时被抢。题目描述有点意思，盗贼游了一圈发现街道是二叉树形式，23333
题目分析
以某一个节点为例分析，当前节点的最大值无非出自下面两种情况：
- 不抢当前节点： 左边最大值 + 右边最大值
- 抢当前节点： 不抢左孩子的最大值 + 不抢右孩子的最大值 + 当前节点值
所以采用后序遍历，每次返回两个值，一个是当前节点不被抢的最大值，一个是当前节点被抢的最大值，可以构造一个长度为2数组存储。
复杂度分析
时间复杂度为O(n)，空间复杂度为O(1)
代码
class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}
public int[] helper(TreeNode root){
if(root == null) return new int[]{0, 0};
int[] leftRes = helper(root.left);
int[] rightRes = helper(root.right);
int[] res = new int[2];
res[0] = Math.max(leftRes[1], leftRes[0]) + Math.max(rightRes[1], rightRes[0]);
res[1] = root.val + leftRes[0] + rightRes[0];
return res;
}
}
总结
分析问题是最重要的
网友评论