213. House Robber II

leetcode medium

#array#backtracking#bit-manipulation#csharp#leetcode#math#medium

Task

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

Дан массив целых чисел 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# solution

matched/original

public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        int max1 = RobSimple(nums, 0, nums.Length - 2);
        int max2 = RobSimple(nums, 1, nums.Length - 1);
        return Math.Max(max1, max2);
    }
    private int RobSimple(int[] nums, int start, int end) {
        int t1 = 0;
        int t2 = 0;
        for (int i = start; i <= end; i++) {
            int temp = t1;
            int current = nums[i];
            t1 = Math.Max(current + t2, t1);
            t2 = temp;
        }
        return t1;
    }
}

C++ solution

auto-draft, review before submit

#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 {
public:
    public int Rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int max1 = RobSimple(nums, 0, nums.size() - 2);
        int max2 = RobSimple(nums, 1, nums.size() - 1);
        return max(max1, max2);
    }
    private int RobSimple(vector<int>& nums, int start, int end) {
        int t1 = 0;
        int t2 = 0;
        for (int i = start; i <= end; i++) {
            int temp = t1;
            int current = nums[i];
            t1 = max(current + t2, t1);
            t2 = temp;
        }
        return t1;
    }
}

Java solution

matched/original

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int max1 = rob_simple(nums, 0, nums.length - 2);
        int max2 = rob_simple(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }

    public int rob_simple(int[] nums, int start, int end) {
        int t1 = 0;
        int t2 = 0;

        for (int i = start; i <= end; i++) {
            int temp = t1;
            int current = nums[i];
            t1 = Math.max(current + t2, t1);
            t2 = temp;
        }

        return t1;
    }
}

JavaScript solution

matched/original

class Solution {
    rob(nums) {
        if (nums.length === 0) return 0;
        if (nums.length === 1) return nums[0];

        let max1 = this.robSimple(nums, 0, nums.length - 2);
        let max2 = this.robSimple(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }

    robSimple(nums, start, end) {
        let t1 = 0;
        let t2 = 0;

        for (let i = start; i <= end; i++) {
            let temp = t1;
            let current = nums[i];
            t1 = Math.max(current + t2, t1);
            t2 = temp;
        }

        return t1;
    }
}

Python solution

matched/original

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        max1 = self.rob_simple(nums, 0, len(nums) - 2)
        max2 = self.rob_simple(nums, 1, len(nums) - 1)

        return max(max1, max2)

    def rob_simple(self, nums, start, end):
        t1, t2 = 0, 0

        for i in range(start, end + 1):
            temp = t1
            current = nums[i]
            t1 = max(current + t2, t1)
            t2 = temp

        return t1

Go solution

matched/original

package main

import (
    "fmt"
    "math"
)

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }

    max1 := robSimple(nums, 0, len(nums)-2)
    max2 := robSimple(nums, 1, len(nums)-1)

    return int(math.Max(float64(max1), float64(max2)))
}

func robSimple(nums []int, start, end int) int {
    t1, t2 := 0, 0

    for i := start; i <= end; i++ {
        temp := t1
        current := nums[i]
        t1 = int(math.Max(float64(current+t2), float64(t1)))
        t2 = temp
    }

    return t1
}

Explanation

Algorithm

1️⃣

Обработка базовых случаев:

Если массив nums пуст, возвращаем 0.

Если в массиве nums только один дом, возвращаем значение этого дома.

2️⃣

Разделение задачи на две подзадачи:

Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию RobSimple с параметрами 0 и nums.Length - 2.

Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию RobSimple с параметрами 1 и nums.Length - 1.

3️⃣

Сравнение результатов и возврат максимального значения:

Вернуть максимальное значение из двух полученных результатов.

😎