198. House Robber

LeetCode medium original: C# #array #bit-manipulation #csharp #dynamic-programming #leetcode #math #medium #recursion
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

Вы — профессиональный грабитель, планирующий ограбление домов вдоль улицы. В каждом доме спрятана определённая сумма денег, единственное ограничение, мешающее ограбить каждый из них, заключается в том, что соседние дома оснащены охранными системами, которые автоматически свяжутся с полицией, если в одну и ту же ночь будут взломаны два соседних дома.

given entier tableau nums, представляющий сумму денег в каждом доме, return максимальную сумму денег, которую вы можете ограбить этой ночью, не подняв тревогу.

Exemple:

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.

C# solution

correspondant/original 
class Solution {
    private int[] memo;
    public int Rob(int[] nums) {
        memo = new int[100];
        for (int i = 0; i < memo.Length; i++) {
            memo[i] = -1;
        }
        return RobFrom(0, nums);
    }
    private int RobFrom(int i, int[] nums) {
        if (i >= nums.Length) {
            return 0;
        }
        if (memo[i] > -1) {
            return memo[i];
        }
        int ans = Math.Max(RobFrom(i + 1, nums), RobFrom(i + 2, nums) + nums[i]);
        memo[i] = ans;
        return ans;
    }
}

C++ solution

brouillon automatique, à relire avant soumission 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
    private vector<int>& memo;
    public int Rob(vector<int>& nums) {
        memo = new int[100];
        for (int i = 0; i < memo.size(); i++) {
            memo[i] = -1;
        }
        return RobFrom(0, nums);
    }
    private int RobFrom(int i, vector<int>& nums) {
        if (i >= nums.size()) {
            return 0;
        }
        if (memo[i] > -1) {
            return memo[i];
        }
        int ans = max(RobFrom(i + 1, nums), RobFrom(i + 2, nums) + nums[i]);
        memo[i] = ans;
        return ans;
    }
}

Java solution

correspondant/original 
class Solution {
    private int[] memo;

    public int rob(int[] nums) {
        this.memo = new int[100];
        Arrays.fill(this.memo, -1);
        return this.robFrom(0, nums);
    }

    private int robFrom(int i, int[] nums) {
        if (i >= nums.length) {
            return 0;
        }
        if (this.memo[i] > -1) {
            return this.memo[i];
        }
        int ans = Math.max(
            this.robFrom(i + 1, nums),
            this.robFrom(i + 2, nums) + nums[i]
        );
        this.memo[i] = ans;
        return ans;
    }
}

JavaScript solution

correspondant/original 
class Solution {
    constructor() {
        this.memo = [];
    }

    rob(nums) {
        this.memo = Array(100).fill(-1);
        return this.robFrom(0, nums);
    }

    robFrom(i, nums) {
        if (i >= nums.length) {
            return 0;
        }
        if (this.memo[i] !== -1) {
            return this.memo[i];
        }
        const ans = Math.max(this.robFrom(i + 1, nums), this.robFrom(i + 2, nums) + nums[i]);
        this.memo[i] = ans;
        return ans;
    }
}

Python solution

correspondant/original 
class Solution:

    def __init__(self):
        self.memo = {}

    def rob(self, nums: List[int]) -> int:
        self.memo = {}
        return self.robFrom(0, nums)

    def robFrom(self, i, nums):
        if i >= len(nums):
            return 0
        if i in self.memo:
            return self.memo[i]
        ans = max(
            self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i]
        )
        self.memo[i] = ans
        return ans

Go solution

correspondant/original 
package main

import (
    "math"
)

type Solution struct {
    memo []int
}

func (s *Solution) Rob(nums []int) int {
    s.memo = make([]int, 100)
    for i := range s.memo {
        s.memo[i] = -1
    }
    return s.robFrom(0, nums)
}

func (s *Solution) robFrom(i int, nums []int) int {
    if i >= len(nums) {
        return 0
    }
    if s.memo[i] != -1 {
        return s.memo[i]
    }
    ans := int(math.Max(float64(s.robFrom(i + 1, nums)), float64(s.robFrom(i + 2, nums) + nums[i])))
    s.memo[i] = ans
    return ans
}

Algorithm

1️⃣

Определите функцию robFrom(), которая принимает индекс дома, который грабитель должен осмотреть, и tableau nums, необходимый для вычислений. На каждом шаге рекурсивного вызова у грабителя есть два варианта: ограбить текущий дом или нет.

2️⃣

Если грабитель выбирает ограбить текущий дом, он должен пропустить следующий, т.е. вызвать robFrom(i + 2, nums). Ответ будет равен значению robFrom(i + 2, nums) плюс сумма, которую грабитель получит, ограбив текущий дом, т.е. nums[i]. В противном случае он может перейти к следующему дому и вернуть прибыль, которую он получит в подзадаче, т.е. robFrom(i + 1, nums).

3️⃣

Нужно find, сохранить в кэше и вернуть максимум из этих двух вариантов на каждом шаге. robFrom(0, nums) даст ответ на всю задачу.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.