House Robber II Leetcode Solution


Кыйынчылык деңгээли орто
Көп суралган Adobe Amazon алма Окшош Гугл Microsoft Walmart Labs
Динамикалык программалоо

"Үй тоноочу II" көйгөйүндө каракчы ар кайсы үйлөрдөн акча тоноп кеткиси келет. Үйлөрдөгү акчанын көлөмү массив аркылуу көрсөтүлөт. Төмөнкү шарттарга ылайык, берилген массивдеги элементтерди кошуу менен эң көп акча суммасын табышыбыз керек:

  1. Каракчы катары менен эки үйдү тоной албайт. Башкача айтканда, эки суммага катары менен эки элементти кошо албайбыз. Эгерде IMP натыйжага элемент кошулат, андан кийин (i + 1)th жана (i - 1)үчүнчү элемент алынып салынышы керек.
  2. Массив тегерек формада. Ошентип, биринчи жана акыркы элемент бири-бирине жанаша жайгашкан.

мисал

1 5 4 2
7
4 5 6 8 3
13

Мамиле (Кара күч)

Маселе, массивдеги ырааттуу эмес элементтерди кошуу менен өндүрүлө турган сумманын максималдуу көлөмүн табууну талап кылат. Катарсыз элементтер камтылган ар бир ырааттуулук айкалышын текшерүү үчүн биз Brute күчүн иштете алабыз. Бирок, индекстер 1st жана ынчы чындыгында чектеш. Демек, алардын экөөсүн тең биздин жыйынтыкка кошпошубуз керек. Ички туюм менен, биз subarrayден максималдуу сумманы таба алабыз[1, N - 1] жана subarray[2, N] өзүнчө. Эми, эки ич ара тилкелер тең сызыктуу. Натыйжада эки subarray-сумманын максимуму болот.

Эми, кандайдыр бир жалпы сызыктуу массив үчүн маселени чечели. Массивде циркуляр жок деп ойлойбуз жана ал биринчи элементтен баштап, акыркысына чейин созулат деп, биринчи жана акыркы элементтерди чектеш деп эсептөөдөн арылдык.

Эми биз:

  1. кошуу биздин суммабыздагы каалаган элемент.
  2. Четтетүү ошол элемент.

Мындай учурда, мүмкүн болгон ырааттуулуктар менен өндүрүлгөн сумманы таба алабыз ырааттуу эмес элементтер. Бардык мүмкүн болгон айкалыштарды табуу үчүн, биз колдоно алабыз Рекурсия жана Backtracking. Ар бир рекурсивдик чалууда биз элементти жыйынтыктоочу суммабызга кошобуз же алып салабыз. Ошонун негизинде индекс боюнча кандайдыр бир элементти тандап алсак I, анда кийинки индекс болушу керек I + 2, I + 3.…. акыркы элементке чейин. Ошо сыяктуу эле, индекстеги элементти алып салсак I, биз кийинки рекурсияны индекс боюнча атай алабыз I + 1, андан келип чыккан бардык мүмкүнчүлүктөрдү текшерүү. Ушундайча, биз ар бир элементти кошуу жана алып салуу мүмкүнчүлүктөрүн текшеребиз. Ошондой эле, сумманы түзгөн бардык элементтер болот ырааттуу эмес ар бир кошумча индекске секирген сайын.

Algorithm

  1. Эгерде массив бош болсо, анда кайтып келиңиз 0;
  2. Эгерде массивде бир элемент болсо
    • Массивди эки бөлүккө бөлө албайбыз. Ошентип, массивдеги жалгыз элементти кайтарыңыз
  3. Максималдуу сумманы сактай турган max_sum_possible өзгөрмөчөсүн колдонуңуз
  4. Чакыруу рекурсивдик функциясы айкалыштары () subarray [1, N - 1] жана [2, N] ар бир кийинки ырааттуулугун текшерүү
    • айкалыштары ()  катары ар бир кийинки санынын суммасын сактоочу параметрге ээ cur_sum
    • Эгерде биз массивдин акыркы элементин кесип өткөн болсок, кайра.
    • Эми, жасай турган бардык мүмкүнчүлүктөрүбүздү текшерип көрөлү кошуу менен учурдагы индекстин мааниси
      • Учурдагы индекстин маанисин кошуңуз cur_sum
      • Бул индекстен кийинки ар бир ырааттуу эмес элементтерге секирүү үчүн, альтернативдик индекстен баштап цикл иштетүү керек
      • чакыруу айкалыштары () ушул индекстер боюнча
    • Учурдагы элемент камтылбай калганда мүмкүнчүлүктү текшерип көрөлү
      • Учурдагы индекстин маанисин cur_sumден алып салыңыз, биз бул жерде backtrack биздин чечим
      • чакыруу айкалыштары () кийинки индекс боюнча, анткени учурдагы индекстен чыгардык
    • Ар бир кадам сайын cur_sum> max_sum_possible экендигин текшерип, аны жаңыртабыз
  5. Жыйынтыгын басып чыгарыңыз

House Robber 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 Solution комплекстүүлүгүн талдоо

Убакыт татаалдыгы

O(N.2 ^ N) катары менен, биз ырааттуу эмес элементтерди камтыган бардык мүмкүн болгон кийинки катмарларды жаратабыз.

Космостун татаалдыгы

O (N) рекурсивдүү стек алкактарынын эсебинен

Мамиле (Динамикалык программалоо)

Мурунку мамиледе биз ар кандай конкреттүү индексте болот деп талкууладык

  • кошуу биздин суммабыздагы элемент.
  • Четтетүү элемент.

House Robber II Leetcode Solution

өзүнө ans [i, N] бул биз ала турган максималдуу сумма i үчүн N. Бул жыйынтык мындан ары ans [i + 2, N] жана ans [i + 1, N] көз каранды болот. Ар бир диапазонду а деп эсептесек болот мамлекет ар бир штат андан ары суб-мамлекеттерден көз каранды. Башка ата-энелердин көйгөйлөрүн чечүү үчүн биз кайсыл бир конкреттүү мамлекет үчүн рекурсивдүү түрдө чечишибиз керек болушу мүмкүн. Бул Optimal Substructure. Ошондой эле N көлөмүндөгү массив үчүн бардык 'n' элементтеринен алынуучу максималдуу сумма ушул эки натыйжанын максимуму болот деген тыянак чыгарсак болот:

  • Чейин оптималдуу натыйжа алынган (N - 1) элементтери жана N элементин кошкондо
  • Чейин алынган мыкты натыйжа (N - 1) жана N элементти эске албаганда

Биз ушундай таблица түзө алабыз таблица [i] [0, i] подразделениеси аркылуу алынуучу максималдуу сумманы сактайт. Бирок, ар бир индекс үчүн эки тандоо бар. Ошентип, учурлар үчүн эки башка жыйынтыкты сакташыбыз керек: качан элемент киргизилет жана качан элемент алынып салынат.

Algorithm

  1. Эгерде массив бош болсо, 0 кайтарыңыз
  2. Эгерде массивде бир эле элемент болсо, анда ошол элементти кайтарыңыз
  3. Функцияны түзүү robLinear () бул сызыктуу массивден алууга боло турган сумманын суммасын кайтарат
  4. robLinear () төмөнкүдөй иштейт:
    1. Катары киргизилген жана алынып салынган эки өзгөрмөнү баштаңыз 0, учурдагы элементти тиешелүүлүгүнө жараша жана кошпогондо алынган эң жогорку натыйжаларды сактайт
    2. Кийинки ар бир кайталоодо, учурдагы элемент + болуп калат алынып салынат мурунку элементтин натыйжасы
    3. Четтетилген максималдуу болуп калат киргизилген жана алынып салынат мурунку элементтин натыйжалары
  5. RobLinear максимумун кайтарыңыз(1, N - 1) жана robLinear(2, N)

House Robber 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 чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (N), биз массивди 2 жолу айланып өтөбүз. Ошентип, биз O (2N) амалдарын жасайбыз, бул сызыктуу.

Космостун татаалдыгы

O (1) Өзгөрүлмө үчүн туруктуу мейкиндик гана колдонулат.