House Robber II Leetcode解决方案  


难度级别 中等
经常问 土砖 亚马逊 Apple 易趣 谷歌 微软 沃尔玛实验室
算法 编码 动态编程 访谈 面试准备 力码 力码解决方案

在“ House Robber II”问题中,强盗想从不同的房屋中抢钱。 房屋中的金额通过数组表示。 我们需要根据以下条件找到通过将给定数组中的元素相加可以赚到的最大金额:

  1. 强盗不能连续抢劫任何两栋房屋。 也就是说,我们不能在总和中包含两个连续的元素。 如果 第i个 元素添加到结果中,然后 (i + 1)(i – 1)th元素必须排除在外。
  2. 该数组是圆形的。 所以 第一 以及 最后 元素也彼此相邻。

使用案列  

1 5 4 2
7
4 5 6 8 3
13

方法(蛮力 

这个问题要求我们找到通过在数组中添加非连续元素可以产生的总和的最大数量。 我们可以使用蛮力检查包含非连续元素的每个序列组合。 但是,索引 1 以及 第N个 实际上是相邻的。 因此,我们必须确保在我们的结果中不要同时包含这两者。 直观地,我们可以从子数组中找到最大和[1,N – 1] 和子数组[2,N] 分别地。 现在,两个子阵列都是线性的。 结果将是两个子数组和的最大值。

参见
一维阵列Leetcode解决方案的运行总和

现在,让我们解决所有常规线性阵列的问题。 由于我们假设数组中不存在圆度,并且从第一个元素开始到最后一个元素都是线性的,因此我们不再考虑将第一个和最后一个元素视为相邻元素。

现在很明显,我们可以:

  1. 包括 我们总和中的任何元素。
  2. 排除 该元素。

在这种情况下,我们可以找到由所有可能的序列产生的和 非连续元素。 为了找到所有可能的组合,我们可以使用 递归和回溯。 在每个递归调用中,我们要么将元素包含在结果和中,要么将其排除。 基于此,如果我们选择索引中的任何元素 I, 那么下一个索引应该是 我+ 2,我+ 3。 直到最后一个元素。 同样,如果我们排除索引中的元素 I, 我们可以在索引上调用下一个递归 我+ 1 检查由此产生的所有可能性。 这样,我们检查了包含和排除每个元素的可能性。 同样,构成总和的所有元素都将是 非连续的 当我们跳到每个其他索引时。

算法

  1. 如果数组为空,则返回 ;
  2. 如果数组只有一个元素
    • 我们不能将数组分为两部分。 因此,返回数组中的唯一元素
  3. 维护一个变量max_sum_possible,该变量存储可能的最大和
  4. 调用递归函数 组合() 检查子数组[1,N – 1]和[2,N]中的每个子序列
    • 组合()  具有将每个子序列之和存储为的参数 cur_sum
    • 如果我们越过了数组的最后一个元素, 返回。
    • 现在,让我们检查一下所有可以实现的可能性 包括 当前索引值
      • 将当前索引值添加到 cur_sum
      • 从备用索引开始运行循环,以便我们可以从该索引跳转到每个非连续元素
      • 电话联系 组合() 在这些指数上
    • 让我们检查一下不包含当前元素的可能性
      • 从cur_sum中减去当前索引值,在这里我们 原路返回 我们的方案
      • 电话联系 组合() 在下一个索引上,因为我们已经排除了当前索引
    • 在每一步,我们都会检查cur_sum> max_sum_possible并进行更新
  5. 打印结果
参见
数组Leetcode解决方案中的字符串匹配

解决强盗II的算法的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

void combinations(vector <int> &a , int &cur_sum , int idx , int &end , int &max_sum_possible)
{
    if(idx > end)
        return;


    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;

    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);

    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}


int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
    combinations(a , cur_sum , 0 , end , max_sum_possible);
    end++;
    combinations(a , cur_sum , 1 , end , max_sum_possible);

    return max_sum_possible;
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

Java程序

import java.lang.Math;


class MutableInt
{
    public int val;
    MutableInt(int x)
    {
        this.val = x;
    }
}


class House_Robber_II
{
    static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
    {
        if(idx > end)
            return;

        cur_sum += a[idx];
        if(cur_sum > max_sum_possible.val)
            max_sum_possible.val = cur_sum;

        for(int i = idx + 2 ; i <= end ; i++)
            combinations(a , cur_sum , i , end , max_sum_possible);

        cur_sum -= a[idx];
        combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
        return;
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        int cur_sum = 0 , end = n - 2;
        MutableInt max_sum_possible = new MutableInt(0);
        combinations(a , cur_sum , 0 , end , max_sum_possible);
        end++;
        combinations(a , cur_sum , 1 , end , max_sum_possible);

        return max_sum_possible.val;
    }
    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

House Robber II Leetcode解决方案的复杂性分析

时间复杂度

O(N.2 ^ N),因为我们会生成每个包含非连续元素的可能子序列。

空间复杂度

上) 由于递归堆栈框架

方法(动态编程 

我们在前面的方法中讨论过,在任何特定索引下,我们都可以

  • 包括 我们总和中的元素。
  • 排除 元素。
参见
删除堆栈的中间元素

House Robber II Leetcode解决方案Pin

假设 ans [i,N] 是我们可以在范围内获得的最大和 iN. 此结果将进一步取决于ans [i + 2,N]和ans [i + 1,N]。 我们可以将每个范围视为 这样每个状态都进一步取决于子状态。 我们可能需要一次又一次地递归求解任何特定状态,以解决其他父状态问题。 这是一 最佳子结构。 我们还可以得出结论,对于大小为N的数组,可以从所有'n'个元素获得的最大和为以下两个结果的最大值:

  • 直至获得最佳结果N – 1)元素,包括第N个元素
  • 直到获得最佳结果 (N – 1) 并排除第N个元素

我们可以创建一个表 桌子[i] 存储可以使用子数组[0,i]获得的最大和。 但是,每个索引都有两个选择。 因此,对于情况,我们需要存储两个不同的结果:何时包含元素和何时排除元素。

算法

  1. 如果数组为空,则返回0
  2. 如果数组只有一个元素,则返回该元素
  3. 创建一个功能 robLinear() 返回可以在线性数组中获得的最大和
  4. robLinear() 的工作方式如下:
    1. 启动包含和排除的两个变量,分别为 0, 它分别存储通过包含和排除当前元素而获得的最大结果
    2. 每次下一次迭代时,included都会成为当前元素+ 排除 前一个元素的结果
    3. 排除成为最大 包括 以及 排除 前一个元素的结果
  5. 返回robLinear的最大值(1,N – 1) 和robLinear(2,N)
参见
Lemonade Change Leetcode解决方案

解决强盗II的算法的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

int robLinear(int l , int r , vector <int> &a)
{
    int inc = 0 , exc = 0 , temp;

    for(int i = l ; i <= r ; i++)
    {
        temp = max(inc , exc);
        inc = exc + a[i];
        exc = temp;
    }
    return max(inc , exc);
}

int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

Java程序

import java.lang.Math;

class House_Robber_II
{
    static int robLinear(int l , int r , int[] a)
    {
        int inc = 0 , exc = 0 , temp;

        for(int i = l ; i <= r ; i++)
        {
            temp = Math.max(inc , exc);
            inc = exc + a[i];
            exc = temp;
        }
        return Math.max(inc , exc);
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
    }

    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

解决House Robber II的复杂性分析

时间复杂度

上), 我们遍历数组2次。 因此,我们进行O(2N)运算,这是线性的。

空间复杂度

O(1) 仅恒定空间用于变量。