Leetcode 213 House Robber II

Note: This is an extension of House Robber.

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.

抢劫犯的第二题,第一题题解链接 http://blog.csdn.net/accepthjp/article/details/61918299

与第一题不同在于这次是一个换,首尾不能同时抢。

那么可以变通一下,将这个问题转化为0-n-2下标和1-n-1下标两个子问题的最大值问题。

这样就可以保证首尾不会同时被抢,相当于做了两次抢劫犯第一题的过程。

class Solution {
public:
    int rob(vector<int>& nums) {
        int a1 = 0;
        int b1 = 0;
        int a2 = 0;
        int b2 = 0;
        if(nums.size() == 1) return nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(i != nums.size() - 1)
            {
                if(i & 1) a1 = max(a1 + nums[i], b1);
                else b1 = max(b1 + nums[i], a1);
            }
            if(i != 0)
            {
                if(i & 1) a2 = max(a2 + nums[i], b2);
                else b2 = max(b2 + nums[i], a2); 
            }
        }
        return max(max(a1, b1), max(a2, b2)); 
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊storm的maxSpoutPending

storm-2.0.0/storm-client/src/jvm/org/apache/storm/Config.java

2205
来自专栏菩提树下的杨过

温故而知新:设计模式之原型模式(Prototype)

原型模式个人以为最适合的场景:参照现有的某一个对象实例,快速得到多个完整的实例副本。(通常是深拷贝的副本) 深拷贝在c#中实现的最简单方式莫过于通过反序列化得到...

2395
来自专栏菩提树下的杨过

[c#]Webservice中如何实现方法重载(overload)以及如何传送不能序列化的对象作参数

1。Webservice中的方法重载问题 (1)在要重载的WebMethod上打个MessageName标签 比如: [WebMethod(Message...

19510
来自专栏wOw的Android小站

[设计模式]之十四:备忘录模式

在不破坏封装性的前提下,捕获一个对象的内部状态,并在该状态之外保存这个状态。这样以后就可将该对象恢复到原先保存的状态。

721
来自专栏码匠的流水账

聊聊flink的CheckpointScheduler

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/checkpoint/Checkp...

1373
来自专栏10km的专栏

thrift:返回null的解决办法

最的项目用到swift:thrift做RPC框架,开始也没有了解太深,就开始干了,今天开始测试了,发现thrift居然不允许服务接口返回null。跟踪源码到下面...

3926
来自专栏算法修养

CodeForces 157A Game Outcome

A. Game Outcome time limit per test 2 seconds memory limit per test 256 me...

3457
来自专栏aoho求索

由散列表到BitMap的概念与应用(二)

在前一篇文章中我们介绍了散列表和BitMap的相关概念与部分应用。本文将会具体讲解BitMap的扩展:布隆过滤器(Bloom filter)。

893
来自专栏java、Spring、技术分享

java应用CAS

  CAS(Compare and Swap),即比较并替换。jdk里的大量源码通过CAS来提供线程安全操作,比如AtomicInteger类。下面我们来分析一...

1313
来自专栏LeetCode

LeetCode <dp>62&63.Unique Paths I&II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

1584

扫码关注云+社区

领取腾讯云代金券