成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

leetcode198,213 house robber

whidy / 2380人閱讀

摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問(wèn)可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問(wèn)題一般化，然后再找到初始情況開(kāi)始這個(gè)由一般到特殊的計(jì)算過(guò)程。

House Robber I 
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, 
the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police 
if two adjacent houses were broken into on the same night.

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.

假設(shè)你現(xiàn)在是一個(gè)小偷，想要一整條街上的人家。你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)nums數(shù)組存放著每一家中的可偷金額，問(wèn)可以偷的最大金額為多少？

這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問(wèn)題一般化，然后再找到初始情況開(kāi)始這個(gè)由一般到特殊的計(jì)算過(guò)程。
我們先考慮一般情景，假設(shè)已經(jīng)經(jīng)過(guò)了i-1戶(hù)人家，現(xiàn)在決定是否要偷第i家，
有兩種選擇：偷 or 不偷
如果偷的話(huà)，就意味著前一戶(hù)人家不能偷，因此我們需要知道前一戶(hù)人家不偷的話(huà)我們可以獲得的最大收益，也就是rob=notRub+nums[i]
如果不偷的話(huà)，就意味著著前一戶(hù)人家可以是偷過(guò)或者沒(méi)有偷過(guò)，那么我們只需要保留二者的最大值就可以了，也就是notRob = max(rob, notRob)
在這個(gè)基礎(chǔ)上，我們來(lái)尋找一般情況，也就是第一次作案時(shí)候的選擇，則rob=nums[0],notRob=0

現(xiàn)在來(lái)舉一個(gè)具體的例子，假設(shè)我現(xiàn)在nums的值為[4,2,3,9]，我們按照上面的思路，將rob和notRob分別初始化為4和0，則rob和notRob的變化如下
rob : notRob
4 : 0
2 : 4
7 : 4(max(2,4))
13 : 7
則可以獲得最大值為13

代碼如下：

    public int rob(int[] nums) {
        if(nums==null || nums.length ==0) return 0;
        //搶劫了前一個(gè)房子可以獲得的最大收入
        int rob = nums[0];
        //沒(méi)有搶劫前一個(gè)房子可以獲得的最大收入
        int notRob = 0;
        for(int i = 1 ; i
House Robber II

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.


和第一題需求的區(qū)別在于，這個(gè)街區(qū)的房子為環(huán)形的。也就是說(shuō)首尾的房子也只能二選一。這個(gè)問(wèn)題其實(shí)可以直接從第一個(gè)問(wèn)題升華。我們可以把這個(gè)問(wèn)題直接拆解為選擇第一個(gè)房子而忽略最后一個(gè)房子可以獲得的最大收入，以及選擇最后一個(gè)房子而忽略第一個(gè)房子可以獲得的最大收入。
至于如果最好的情況是二者都不選的話(huà)，那么前一類(lèi)和后一類(lèi)都會(huì)覆蓋這種情況，所以說(shuō)這種分類(lèi)可以覆蓋全部的情況。


代碼如下：


    public int rob(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        return Math.max(rob(nums, 0, nums.length-2),rob(nums, 1, nums.length-1));
    }
    
    public int rob(int[] nums, int low, int high){
        int rob = 0;
        int notRob = 0;
        while(low<=high){
            int temp = rob;
            rob = notRob + nums[low];
            notRob = Math.max(temp, notRob);
            low++;
        }
        return Math.max(rob, notRob);
    }



想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70899.html

相關(guān)文章

  • leetcode 198 House Robber

    摘要：但是任何臨近的兩個(gè)房子被偷就會(huì)觸發(fā)警報(bào)。要求我們求出在不觸發(fā)警報(bào)的情況下偷到的最多的錢(qián)。每個(gè)房子里的錢(qián)通過(guò)輸入的數(shù)組表示。 題目詳情 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only...

    jzman 評(píng)論0 收藏0

  • [LeetCode] House Robber I II

    摘要：注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

    qpal 評(píng)論0 收藏0

  • [Leetcode] House Robber 打家劫舍

    摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路一般來(lái)說(shuō)，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。另外我們可以做一點(diǎn)優(yōu)化，本來(lái)我們是要用一個(gè)數(shù)組來(lái)保存之前的結(jié)果的。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了?？梢詮?fù)用的代碼。 House Robber I You are a professional robber planning to rob houses along a ...

    golden_hamster 評(píng)論0 收藏0

  • LeetCode[337] House Robber III

    摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來(lái)說(shuō)，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過(guò)的進(jìn)行保留，避免重復(fù)計(jì)算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...

    Dr_Noooo 評(píng)論0 收藏0

  • [LintCode/LeetCode] House Robber II

    摘要：因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對(duì)數(shù)組循環(huán)兩次，一個(gè)從取到，一個(gè)從取到，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于時(shí)的情況。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...

    OnlyLing 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<