百度蜘蛛不爬取网站/google关键词排名查询

​小龙是一个资深程序员，年纪轻轻头发就凋零不堪了，看到身边的朋友们在大厂一个个拿到了高薪，决定出去面试看看，毕竟看发型咱就是资深程序员不是…

这不，马上就迎来了一家国内某大厂的面试邀请，小龙怀着忐忑的心情复习了一周，走进了面试的会议室，咦，，，这个面试官好凶，，不会问一些有的没的吧

面试官：

**龙是吧？说说你的经历。

小龙：

你好，面试官，我叫**龙，巴拉巴拉…很希望能加入咱们公司。

面试官：

嗯，你还没30，怎么看着和40似的。

小龙：

额，平时敲代码熬夜比较多，嗯… 买买皮。

面试官：

好，那么我们开始今天的面试吧，假如你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

小龙：

嗯，，，你才是小偷，你全家都是。

嗯，你好面试官，这个问题是一个典型的动态规划，dp的问题，我们可以把这个问题转换成一个数组，不能取相邻的两个数，求在这种情况下，最大的和是多少。比如下面这个数组就代表这个村子

那么，我，呸… 这个小偷选择偷一号屋子和三号屋子是最合适的，一共可以偷4块钱，嗯…

面试官：

嗯嗯，不错不错，你继续说。

小龙：

那么就可以使用一个数组来记录当前这家之前最多能偷多少钱，首先，第一家肯定是确定的，如果只有第一家的话，那么肯定要偷，那么这个数组dp[0]=1，如果是前两家的话，那么就要看一下，第一家和第二家哪家的钱比较多了，取Math.max(num[0],num[1])，所以dp[1]=2，从第三家开始，我们就要考虑两种情况了，就是第三家这家我们要不要偷，如果偷的话，第二家我们就不能偷了，因为有可能偷到相邻的两家了，会触发警报，所以有两种偷法，第一种就是偷第三家和第一家，第二种就是不偷第三家，那我们就要看看nums[0]+nums[3]和nums[2]哪个更大了，就是到第三家钱最多的偷法，于是乎，状态转移方程就出来了。

至此，我，，呸，那个小偷就可以偷到最多的钱了。
代码如下：

public class Rob {
​public static void main(String[] args) {System.out.println(rob(new int[]{2, 7, 9, 3, 1}));}
​private static int rob(int[] nums) {if (Objects.isNull(nums) || nums.length == 0) {return 0;} else if (nums.length == 1) {return nums[0];} else if (nums.length == 2) {return Math.max(nums[1], nums[0]);}int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[1], nums[0]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);}return dp[nums.length - 1];}
}

面试官：
嗯，嗯，小伙子可以，那么这个村子是环形的呢，第一家和最后一家挨着，连着偷也报警。

小龙：

嗯，这个问题也是很好处理的，这个我们只需要考虑一种情况，就是首尾相连的，那么我们把刚才的方法抽象出来，然后在不考虑这个村子第一家的情况下，算出我最多能偷得的金额p1，再不考虑最后一家的情况下，算得我能偷到的最多的金额p2，p1和p2中的最大值就是答案。
代码如下

public class Rob2 {
​public static void main(String[] args) {System.out.println(rob(new int[]{2, 3, 2}));}
​private static int rob(int[] nums) {if (Objects.isNull(nums) || nums.length == 0) {return 0;} else if (nums.length == 1) {return nums[0];}return Math.max(helper(Arrays.copyOfRange(nums, 0, nums.length - 1)), helper(Arrays.copyOfRange(nums, 1, nums.length)));}
​private static int helper(int[] nums) {if (Objects.isNull(nums) || nums.length == 0) {return 0;} else if (nums.length == 1) {return nums[0];} else if (nums.length == 2) {return Math.max(nums[1], nums[0]);}int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[1], nums[0]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);}return dp[nums.length - 1];}
​
}

面试官：
（内心）这小子有点东西，怪不得这么秃，看来我要使用杀手锏了。
嗯嗯，好，那么在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。就比如这个村子是这么分布的

那么，你就得这么偷

才能获取最多的钱，就是3+3+1=7块钱

小龙：
（内心）嗯，，，做个小偷还要懂二叉树，也是不容易。

这个问题就是一个二叉树，如果子节点的值被用到了，父节点的值就不能再用了，那么我们就可以采用后序遍历的方式，因为后序遍历根节点是最后一个遍历到的，我们更容易获取到最后的结果。

我们可以给每个节点一个长度的数组，分别记录着，我当前这个节点偷与不偷的最大金额。

那么它的父节点就有两种的这个数组，第一个元素就要选择子节点的不偷来加上当前节点的金额，第二个元素就是把左右两个节点偷和不偷的中间的最大值拿来相加。这样整颗树递归上去就是这个样子。

最后返回根节点两个元素的最大值，就是答案。
代码如下

public class Rob3 {
​public static int rob(TreeNode root) {int[] res = helper(root);return Math.max(res[0], res[1]);}
​private static int[] helper(TreeNode root) {if (Objects.isNull(root)) {return new int[2];}int[] l = helper(root.left);int[] r = helper(root.right);int[] res = new int[2];res[0] = root.val + l[1] + r[1];res[1] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);return res;}
​
}

面试官：

早就看你骨骼惊奇，明天过来二面，我要让你手写LRU…

至此，力扣198、213、337题已团灭。