198. House Robber

LeetCode medium оригинал: C# #array #bit-manipulation #csharp #dynamic-programming #leetcode #math #medium #recursion

LeetCode Static

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

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

Пример:

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# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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(), которая принимает индекс дома, который грабитель должен осмотреть, и массив nums, необходимый для вычислений. На каждом шаге рекурсивного вызова у грабителя есть два варианта: ограбить текущий дом или нет.

2️⃣

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

3️⃣

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.