[leetcode]問題解答と解説。198. House Robber [JavaScript]
皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます
私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。
では今日のleetCode。
【198. House Robber】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。
※下にある自分のコードは自分で設けた制限時間内に書けたところまです。
これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。
[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 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.
あなたはプロの強盗で、ある通り沿いの家々を襲う計画を立てています。各家には一定額のお金が隠されています。あなたが各家を襲うのを阻む唯一の制約は、隣接する家にはセキュリティシステムが接続されており、同じ夜に隣接する2つの家が侵入された場合、自動的に警察に連絡されることです。
各家の金額を表す整数配列 nums が与えられたとき， 今夜，警察に通報せずに強奪できる最大金額を返せ．
Example 1:
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.
Example 2:
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.
- 連続するインデックスの値は足せない。
- 連続しない積算の最大値を求める
- 最初は0からでも1からでも良い
exampleは実際の問題ページを見てください
[leetcode] 198. House Robber 問題ページ
[leetcode] 198. House Robber
my code is not good(time out)
var rob = function(nums) {
if(nums.length === 0) return 0
if(nums.length === 1) return nums[0]
if(nums.length === 2) return Math.max(nums[0], nums[1])
let dp = Array.from({length: nums.length}).map(_ => 0)
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
for(let i = 2; i < dp.length; i++){
dp[i] = Math.max((dp[i-2] + nums[i]), dp[i-1])
}
return dp[nums.length-1]
};時間切れ。
でも調べながらやった。
[leetcode] 198. House Robber。discussの中の一つの解答例
数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない
JavaScriptでfilterされている、discussはこちらから
var rob = function (nums) {
let dp = new Array(nums.length + 1).fill(0);
dp[0] = 0;
dp[1] = nums[0];
for (let i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2])
}
return dp[nums.length];
};[leetcode] 198. House Robber をやってみて感想
- my first dp!!
- 理解するのに苦労した。