关键词：
在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
注意事项
这题是House Robber的扩展，只不过是由直线变成了圈
样例
给出nums = [3,6,4], 返回 6， 你不能打劫3和4所在的房间，因为它们围成一个圈，是相邻的．
思路：动态规划，从第I题可以得出递推关系式为A[i] = max(A[i-1],A[i-2]+A[i]);这里由于这题变成了一个圈，所以头尾两个数不能同时取到，所以把这个圈分成[0,n-1]和[1,n]两部分分别计算所能得到的最大值然后取较大值就可以了。
1 class Solution 2 public: 3 /** 4 * @param nums: An array of non-negative integers. 5 * @return: The maximum amount of money you can rob tonight 6 */ 7 int houseRobber2(vector<int> &nums) 8 // write your code here 9 int size = nums.size(); 10 if(size == 0) return 0; 11 if(size == 1) return nums[0]; 12 13 vector<int> L(size,0);//两个数组做动态规划 14 vector<int> R(size,0); 15 L[1] = nums[0];//初始化 16 R[1] = nums[1]; 17 for(int i=2;i<size;++i)//递推公式，注意nums中数的顺序先后 18 L[i] = max(L[i-2]+nums[i-1],L[i-1]); 19 R[i] = max(R[i-2]+nums[i], R[i-1]); 20 21 return max(L[size-1],R[size-1]);//取较大值 22 23 ;
lintcode--011(打劫房屋2）
在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子... 查看详情
lintcode-515-房屋染色(代码片段)
publicclassSolution/***@paramcosts:nx3costmatrix*@return:Aninteger,theminimumcosttopaintallhouses*/publicintminCost(int[][]costs)//writeyourcodehereintn=costs.length;if(n==0)return0;int[][]dp=newint[n][3];dp[0][0]=costs[0][0];dp[0][1]=costs[0][1];dp[0][2]=costs[0][2];for(inti=1;i<n;++i)for(intj=0... 查看详情
lintcode6---合并排序数组ii(代码片段)
importjava.util.Arrays;publicclassLint6/**合并两个排序的整数数组A和B变成一个新的数组。新数组也要有序。*/publicstaticvoidmain(String[]args)publicint[]mergeSortedArray(int[]A,int[]B)int[]C=newint[A.length+B.length];for(inti=0;i 查看详情
算法-打劫房屋iii(深搜)
...所以要记录下，这个题的解法真是太巧妙了题意：在上次打劫完一条街道之后和一圈房屋之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子组成的区域比较奇怪，聪明的窃贼考察地形之后，发现这次的地形是一颗... 查看详情
lintcode570.寻找丢失的数ii(代码片段)
给一个由1- n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。 注意事项n<=30样例给出n= 20,str= 19201234567891011121314151618丢失的数是 17 ，返回这个数。思路：回溯法进行深度优先搜索... 查看详情
213.打家劫舍ii(代码片段)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如... 查看详情
213.打家劫舍ii(代码片段)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如... 查看详情
java求解打家劫舍ii(代码片段)
...总结一、题目你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗... 查看详情
lintcode666.猜数游戏ii(代码片段)
我们正在玩猜数游戏,游戏内容如下:我在1到n的范围内选择一个数作为待猜的数,你需要来猜这个数,每次你猜错的时候,我会告诉你我选择的这个数是比你说的数要高还是低,但是,当你猜这个数为x并且猜错的时候你需要支付$x.当你... 查看详情
leetcode刷题python213.打家劫舍ii(代码片段)
1题目你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统... 查看详情
lintcode-房屋染色
1classSolution{2public:3/*4*@paramcosts:nx3costmatrix5*@return:Aninteger,theminimumcosttopaintallhouses6*/7constintinf=0x3f3f3f3f;8vector<vector<int>>dp;9intminCost(vector<vector<int 查看详情
单词接龙ii(代码片段)
单词接龙II（来自lintecode：https://www.lintcode.com/problem/word-ladder-ii/?_from=ladder&&fromId=1）给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。变换规则如下：1.每次只能改变一个字母。2.变换过程中的中... 查看详情
java求解打家劫舍ii(代码片段)
...总结一、题目你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗... 查看详情
63搜索旋转排序数组ii(代码片段)
原题网址：https://www.lintcode.com/problem/search-in-rotated-sorted-array-ii/description描述跟进“搜索旋转排序数组”，假如有重复元素又将如何？是否会影响运行时间复杂度？如何影响？为何会影响？写出一个函数判断给定的目标值是否出现... 查看详情
代码随想录算法训练营第四十八天|198.打家劫舍213.打家劫舍ii337.打家劫舍iii(代码片段)
...III198.打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会... 查看详情
刷题记录|day48●198.打家劫舍●213.打家劫舍ii●337.打家劫舍iii(代码片段)
...劫舍题目描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会... 查看详情
2021-10-28：打家劫舍ii。你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装(代码
...a;打家劫舍II。你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗... 查看详情
力扣337——打家劫舍iii(代码片段)
...质还是动态规划，优化时需要考虑数据结构。原题在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房... 查看详情