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

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

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

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

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

示例 1:

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

示例 2:

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 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云服務器云服務器刷應用刷VPS 刷cdn 刷alexa

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

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

相關(guān)文章

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

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

crelaber 2019-08-23 15:39 評論0 收藏0
面試常遇的打家劫舍問題你學會了嗎~

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

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

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

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

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

摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(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 評論0 收藏0