程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode] House Robber II

[LeetCode] House Robber II

編輯:C++入門知識

[LeetCode] House Robber II


 

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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

解題思路:

這個是偷東西的升級版。偷東西1版是一條街上一排房子,每個房子裡面有金錢若干,其警報系統很怪,只有觸發相鄰的兩個房間,警報系統才發出警報。問如何偷才能得到最大的值。

這個升級版就是這條街不再是一字排開,而是一個環形街,第一個房子與最後一個房子相鄰。問如何偷才能得到最大值?

最初的想法是,記錄第一個房間是否被偷了,若被偷了,那麼最後一個房間就不能偷。然後分情況討論。但是如何記錄第一個房間被偷了呢?似乎比較麻煩。

其實可以有雙向掃描法,第一次從左向右掃描,采用動態規劃,若d[len-2]==d[len-1],說明最後一個房間我們並沒有偷,這種情況跟線性街道是一樣的,返回d[len-1]即可,若不相等,說明線性街道時,最後一個房間需要偷,但是我們並不知道第一個房間是否偷了,因此我們還需要掃描一次,從左往右掃描,同樣采用動態規劃,得出dr[]。

此時有兩個動態規劃數組d[]和dr[],注意d[]中d[len-1]!=d[len-2]。我們不知道第一間房是否偷了。假如第一間房間偷了,最後一間房不能偷,那麼我們返回d[len-2]。假如第一間房沒有偷,我們返回dr[1],而不管最後一間房是否被偷。因此,我們只需要返回dr[1]和d[len-2]的較大值即可。

代碼比較好懂,發現自己越解釋越難懂,唉~ps,leetCode計時壞了嗎?為何我的代碼跑出來只需0ms?

 

class Solution {
public:
    int rob(vector& nums) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        if(len == 2){
            return max(nums[0], nums[1]);
        }
        int d[len];
        d[0]=nums[0];
        d[1]=max(nums[0], nums[1]);
        for(int i=2; i=0; i--){
            dr[i]=max(dr[i+1], nums[i]+dr[i+2]);
        }
        return max(dr[1], d[len-2]);
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved