House Robber II Leetcode шешімі  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма еВау Google Microsoft Walmart зертханалары
алгоритмдер кодтау Динамикалық бағдарламалау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions

«Үйді тонаушы II» мәселесінде қарақшы әртүрлі үйлерден ақша тонағысы келеді. Үйлердегі ақша сомасы массив арқылы ұсынылған. Берілген жиымға элементтерді келесі шарттарға сәйкес қосу арқылы жасауға болатын ең көп ақша сомасын табуымыз керек:

  1. Қарақшы кез-келген екі үйді тонай алмайды. Яғни, біз қосындыға қатарынан екі элементті қоса алмаймыз. Егер ит нәтижеге элемент қосылады, содан кейін (мен + 1)ші және (i - 1)үшінші элемент алынып тасталуы керек.
  2. Жиым дөңгелек. Сонымен, бірінші және соңғы элемент бір-біріне жақын орналасқан.

мысал  

1 5 4 2
7
4 5 6 8 3
13

Тәсіл (Брут күші 

Мәселе бізден жиымға бірізді емес элементтер қосу арқылы алынатын максималды соманы табуды талап етеді. Біз кез-келген элементтерден тұратын кез-келген комбинацияны тексеру үшін Brute күшін қолдана аламыз. Бірақ, индекстер 1st және Тоғызыншы жақын орналасқан. Сонымен, біз олардың екеуін де нәтижемізге қоспауды қамтамасыз етуіміз керек. Интуитивті түрде біз қосындыдан максималды қосынды таба аламыз[1, N - 1] және субаррай[2, N] бөлек. Енді ішкі аралықтардың екеуі де сызықтық болып табылады. Нәтиже екі қосындының максимумы болады.

Сондай-ақ, қараңыз
Leetcode шешімінің 1d массивінің қосындысы

Енді кез-келген жалпы сызықтық массив үшін есеп шығарайық. Массивте дөңгелек жоқ және ол бірінші элементтен бастап, соңғымен аяқталады деп болжай отырып, біз бірінші және соңғы элементтерді іргелес деп қарастырудан құтылдық.

Енді біз:

  1. Қосыңыз біздің қосындымыздағы кез-келген элемент.
  2. шығару сол элемент.

Мұндай жағдайда біз барлық ықтимал тізбектермен шығарылған соманы таба аламыз бірізді емес элементтер. Барлық ықтимал комбинацияларды табу үшін біз пайдалана аламыз Рекурсия және кері трекинг. Әр рекурсивті қоңырау кезінде біз элементті нәтиже қосындысына қосамыз немесе оны алып тастаймыз. Соның негізінде индекстегі кез-келген элементті таңдасақ I, онда келесі индекс болуы керек I + 2, I + 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. Нәтижені басып шығарыңыз
Сондай-ақ, қараңыз
Массивтің шешім кодында жолдарды сәйкестендіру

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 шешімінің күрделілігін талдау

Уақыттың күрделілігі

O(N.2 ^ N) кез-келген элементтерден тұратын кез-келген ықтимал тізбекті жасай отырып.

Ғарыштың күрделілігі

O (N) рекурсивті стек жақтауларының арқасында

Тәсіл (Динамикалық бағдарламалау 

Алдыңғы тәсілде біз кез-келген нақты индекс кезінде мүмкін болатындығын талқыладық

  • Қосыңыз біздің қосындымыздағы элемент.
  • шығару элемент.
Сондай-ақ, қараңыз
Стектің ортаңғы элементін жою

House Robber II Leetcode шешімітүйреуіш

Болыңыз ans [i, N] - бұл диапазонда алуға болатын максималды сома i дейін N. Бұл нәтиже 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. Әрбір келесі қайталану кезінде + элементі болады алынып тасталды алдыңғы элементтің нәтижесі
    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

Үйді тонаушы II шешудің күрделілігін талдау

Уақыттың күрделілігі

O (N), біз массивті 2 рет айналып өтеміз. Сонымен, O (2N) амалын жасаймыз, ол сызықтық.

Ғарыштың күрделілігі

O (1) Айнымалылар үшін тек тұрақты кеңістік қолданылады.