這題是一題動態規劃問題,目標是擷取不連續的元素,全部相加起來選出最優解,因只用了一層迴圈,時間複雜度可估 O(n)
,這裡有 JAVA 和 Python 的寫法。
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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array
nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
你是一個專業的小偷,計畫了搶劫街道上的房子,每個房子藏有一定數量的錢,阻止你的唯一條件是房子之間有相連的安全系統,如果相連的房子同一晚被闖入,就會通知警方。
給定一個整數陣列
nums
代表每一間房子的金額,回傳擷取最高的金額且沒有驚動警察。
題目連結:https://leetcode.com/problems/house-robber/
1 <= nums.length <= 100
0 <= nums[i] <= 400
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
public int rob(int[] num) {
int rob = 0; // 搶當前的房子的最大金額
int notrob = 0; // 不搶當前的房子的最大金額
for(int i=0; i<nums.length; i++) {
int currob = notrob + nums[i]; // 0 + 當前房子 (如果搶了當前房子就不能搶前一個房子)
notrob = Math.max(notrob, rob); // 不搶當前的房子和搶當前的房子比較 (因為在不搶目前房屋的情況下,可以選擇搶或不搶上一個房屋,所以要取最大值)
rob = currob; // 搶當前的房子的最大金額
}
return Math.max(rob, notrob); // 最後選出最大的金額
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
class Solution:
def rob(self, nums: List[int]) -> int:
rob = 0
not_rob = 0
for num in nums:
cur_rob = not_rob + num
not_rob, rob = max(not_rob, rob), cur_rob
return max(rob, not_rob)
Language | Runtime | Memory |
---|---|---|
Java | 0ms | 40.62MB |
Python | 48ms | 16.33MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/11/14/LeetCode-198-House-Robber-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論