LeetCode 213 —— 打家劫舍 II

本文主要是介绍LeetCode 213 —— 打家劫舍 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 解题思路

此题是 LeetCode 198—— 打家劫舍 的升级版，多了一个首尾相连的设定。

因为首尾相连，所以第一个房屋和最后一个房屋只能偷窃其中一个。

所以，第一种方案就是不偷窃最后一个房屋，那么我们从第一个房屋偷到倒数第二个房屋，看看这样能偷窃到的最大值是什么。

第二种方案则是从最后一个房屋偷到第二个房屋，这样也有一个最大的偷窃金额。

而这两种方案的较大值也就是我们题目所求。

3. 代码实现

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1) {return nums[0];}int stole_value = 0;int not_stole_value = 0;int max_value_1 = 0;for (int i = 0; i < nums.size()-1; ++i) {int temp = not_stole_value;not_stole_value = max(stole_value, not_stole_value);stole_value = temp + nums[i];max_value_1 = max(max_value_1, stole_value);}stole_value = 0;not_stole_value = 0;int max_value_2 = 0;for (int i = nums.size()-1; i > 0; --i) {int temp = not_stole_value;not_stole_value = max(stole_value, not_stole_value);stole_value = temp + nums[i];max_value_2 = max(max_value_2, stole_value);}return max(max_value_1, max_value_2);}
};

这篇关于LeetCode 213 —— 打家劫舍 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---