【刷算法】LeetCode.198-打家劫舍

whinc 發(fā)布于2019-08-23 14:08 / 481人閱讀

摘要：你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。示例輸入輸出解釋偷竊號(hào)房屋金額，然后偷竊號(hào)房屋金額。偷竊到的最高金額。

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4 。

示例 2:

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0)
        return 0;
    if(nums.length === 1)
        return nums[0];
    
    let prepre = nums[0], pre = Math.max(nums[0], nums[1]);
    
    for(let i = 2;i < nums.length;i++) {
        let temp = pre;
        pre = Math.max(prepre + nums[i], pre);
        prepre = temp;
    }
    
    return pre;
};

GPU云服務(wù)器云服務(wù)器刷應(yīng)用刷VPS 刷cdn 刷alexa

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

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

相關(guān)文章

【算法解析LeetCode by Javascript】213. 打家劫舍 II

摘要：偷竊到的最高金額。世紀(jì)年代初美國(guó)數(shù)學(xué)家等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。 showImg(https://segmentfault.com/img/bVbplM3?w=953&h=465); 題目描述你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房...

crelaber 2019-08-23 15:39 評(píng)論0 收藏0
面試常遇的打家劫舍問題你學(xué)會(huì)了嗎~

摘要：打家劫舍打家劫舍問題描述問題描述你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，今晚能夠偷竊到的最高金額。和分別表示的左右孩子。打家劫舍I問題描述你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)...

不知名網(wǎng)友 2021-11-25 09:43 評(píng)論0 收藏0
leetcode 198 House Robber

摘要：但是任何臨近的兩個(gè)房子被偷就會(huì)觸發(fā)警報(bào)。要求我們求出在不觸發(fā)警報(bào)的情況下偷到的最多的錢。每個(gè)房子里的錢通過輸入的數(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 2019-08-16 11:06 評(píng)論0 收藏0
leetcode198,213 house robber

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

whidy 2019-08-16 11:01 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評(píng)論0 收藏0