包子君top 5油管中文up主 & Leetcode solution 213. House Robber II
包子君top 5油管中文up主 & Leetcode solution 213. House Robber II
咳咳，标题党一下。。。仅仅是包子君(行者)的最近喜好，不代表包子其他老师。哎，书是读的越来越少了，youtube看的越来越多了，应该是快废了。。。
都不是那种家喻户晓，带货几个亿的大up主啦。
Top 1: 毒角show。
东北老乡，做了很多我想做的事儿，拖鞋大裤衩，球打得好还会rap，小伙子很有前途。
Top 2: 李自然说。
胶东口音我听起来也特别熟悉，牛13 吹得很好
Top 3: 冲浪普拉斯
视频很严谨，小伙子思路很好
Top 4: 跟我一起来谈钱。
一开始姐姐说的挺好，后来有点啰嗦了，比较适合做饭刷碗的时候用2.0x的速度来听
Top 5: 大象放映室。
文案非常好，而且电影风格很符合我伪文青的口味
好了，赶紧做题吧~ 如果你还没有subscribe包子的油管，翻个墙呗兄弟，谢谢！
Leetcode solution 213. House Robber II
Blogger: http://blog.baozitraining.org/2020/06/leetcode-solution-213-house-robber-ii.html
Youtube: https://youtu.be/FZq3YHzvUa4
博客园: https://www.cnblogs.com/baozitraining/p/13128835.html
B站: https://www.bilibili.com/video/BV1k54y1B7mD/
Problem Statement
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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.
Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.Problem link
Video Tutorial
You can find the detailed video tutorial here
- Youtube
- B站
Thought Process
This is very similar to House Robber I problem where the only difference is the houses now form a circle (French fancy way calls it cul-de-sac). It's same DP algorithm except now we need to consider two cases: whether we rob the first house or not. If we rob the first house, we should not rob the last house. If we do not rob the first house, we can rob the last house. We can even reuse the rob() function in House Robber I problem
Solutions
Use DP
1 public int rob(int[] nums) {
2 if (nums == null || nums.length == 0) {
3 return 0;
4 }
5 if (nums.length == 1) {
6 return nums[0];
7 }
8
9 // rob first house, so need to remove the last house
10 int[] rob_first_nums = new int[nums.length - 1];
11 for (int i = 0; i < rob_first_nums.length; i++) {
12 rob_first_nums[i] = nums[i];
13 }
14
15 // do not rob first house, start from the 2nd and rob to the end of the house
16 int[] rob_no_first_nums = new int[nums.length - 1];
17 for (int i = 1; i < nums.length; i++) {
18 rob_no_first_nums[i - 1] = nums[i];
19 }
20
21 int rob_first_max = this.robFlatRow(rob_first_nums);
22 int rob_no_first_max = this.robFlatRow(rob_no_first_nums);
23
24 return Math.max(rob_first_max, rob_no_first_max);
25 }
26
27 public int robFlatRow(int[] num) {
28 if (num == null || num.length == 0) {
29 return 0;
30 }
31
32 int n = num.length;
33 int[] lookup = new int[n + 1]; // DP array size normally larger than 1
34 lookup[0] = 0;
35 lookup[1] = num[0];
36
37 for (int i = 2; i <= n; i++) {
38 lookup[i] = Math.max(lookup[i - 1], lookup[i - 2] + num[i - 1]);
39 }
40
41 return lookup[n];
42 }Time Complexity: O(N), N is the array size Space Complexity: O(N) since we use extra arrays