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

whinc 發布于2019-08-23 14:08 / 410人閱讀

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

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

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

示例 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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100150.html

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

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

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

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

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

摘要：但是任何臨近的兩個房子被偷就會觸發警報。要求我們求出在不觸發警報的情況下偷到的最多的錢。每個房子里的錢通過輸入的數組表示。題目詳情 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

摘要：你不能連著偷兩家因為這樣會觸發警報系統。現在有一個數組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗了動態編程的思想。動態編程要求我們將問題一般化，然后再找到初始情況開始這個由一般到特殊的計算過程。 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 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 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