House Robber II Leetcode шийдэл  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Ebay Google-ийн Microsoft- Walmart лабораторууд
алгоритмууд кодлох Динамик програмчлал ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions

"Байшин дээрэмчин II" асуудалд дээрэмчин янз бүрийн байшингаас мөнгө дээрэмдэхийг хүсдэг. Байшин дахь мөнгөний хэмжээг массиваар илэрхийлдэг. Дараах нөхцлүүдийн дагуу өгөгдсөн массив дахь элементүүдийг нэмж олох хамгийн их мөнгөний нийлбэрийг олох хэрэгтэй.

  1. Дээрэмчин хоёр дараалсан байшинг дээрэмдэж чадахгүй. Энэ нь бид нийлбэрдээ дараалсан хоёр элементийг оруулж чадахгүй гэсэн үг юм. Хэрэв ith элементийг үр дүнд нэмнэ, дараа нь (би + 1)th ба (i - 1)элементийг хасах ёстой.
  2. Массив нь дугуй хэлбэртэй байна. Тэгэхээр эхний болон өнгөрсөн элемент нь хоорондоо зэрэгцэн оршдог.

Жишээ нь  

1 5 4 2
7
4 5 6 8 3
13

Хандалт (Харгис хүчин 

Асуудал нь массив дахь дараалалгүй элементүүдийг нэмж гаргаж болох нийлбэрийн дээд хэмжээг олохыг биднээс шаардаж байна. Дараалалгүй элемент агуулсан дарааллын хослол бүрийг шалгахын тулд бид Brute хүчийг ажиллуулж болно. Гэхдээ индексүүд 1st болон үнэндээ зэргэлдээ байдаг. Тиймээс бид хоёуланг нь хоёуланг нь үр дүндээ багтаахгүй байх ёстой. Бид дэд массиваас хамгийн их нийлбэрийг олох боломжтой[1, N - 1] ба дэд хэсэг[2, N] тус тусад нь. Одоо дэд зурвасууд хоёулаа шугаман байна. Үр дүн нь хоёр дэд нийлбэрээс хамгийн их байх болно.

мөн үзнэ үү
1d массивын Leetcode шийдлийн нийлбэрийг ажиллуулж байна

Одоо ямар ч ерөнхий шугаман массивын асуудлыг шийдье. Дугуй хэлбэр нь массивт байхгүй бөгөөд эхний элементээс эхлээд сүүлд нь шугаман байна гэж таамаглаж байгаа тул эхний ба сүүлийн элементийг зэргэлдээ гэж үзэхээс ангижирсан.

Бид дараахь зүйлийг хийж чадах нь тодорхой боллоо.

  1. оруулах бидний нийлбэр дэх аливаа элемент.
  2. Орхих тэр элемент.

Ийм тохиолдолд бид боломжит бүх дарааллын дагуу үйлдвэрлэсэн нийлбэрийг олох боломжтой дараалсан бус элементүүд. Бүх боломжит хослолуудыг олохын тулд бид ашиглаж болно Рекурс ба Backtracking. Рекурсив дуудлага бүрт бид элементийг үр дүнгийн нийлбэрт оруулах эсвэл хасах болно. Үүний үндсэн дээр, хэрэв бид индекс дээр ямар нэгэн элемент сонговол 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. Үр дүнг хэвлэ
мөн үзнэ үү
Array Leetcode шийдэлд мөр тохирох

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 шийдэл

гэж үздэг ans [i, N] Энэ нь бидний олж авах хамгийн дээд нийлбэр юм i to N. Энэ үр дүн нь ans [i + 2, N] ба ans [i + 1, N] -ээс хамаарна. Бид муж бүрийг а гэж авч үзэж болно төлөв муж бүр цаашлаад дэд мужуудаас хамаарна. Эцэг эхийн бусад асуудлуудыг шийдвэрлэхийн тулд бид аль нэг муж улсын хувьд дахин дахин давтан шийдвэрлэх шаардлагатай болж магадгүй юм. Энэ бол Оновчтой дэд бүтэц. N хэмжээтэй массивын хувьд бүх 'n' элементүүдээс авах хамгийн дээд нийлбэр нь эдгээр хоёр үр дүнгийн хамгийн дээд хэмжээ гэж бид дүгнэж болно.

  • Хүртэл авсан оновчтой үр дүн (N - 1) элементүүд ба үүнд N элементийг оруулна
  • Хүртэл авсан хамгийн сайн үр дүн (N - 1) N элементийг оруулаагүй болно

Бид ийм хүснэгт үүсгэж болно хүснэгт [би] дэд массив ашиглан олж болох хамгийн дээд нийлбэрийг хадгалдаг [0, i]. Гэхдээ индекс бүрт хоёр сонголт байдаг. Тиймээс бид тохиолдлын хувьд хоёр өөр үр дүнг хадгалах хэрэгтэй: элемент орсон үед, элемент хасагдах үед.

Алгоритм

  1. Хэрэв массив хоосон байвал 0-г буцаана уу
  2. Хэрэв массив нь зөвхөн нэг элементтэй бол тухайн элементийг буцаана
  3. Функц үүсгэх robLinear () Энэ нь шугаман массиваас олж болох хамгийн дээд нийлбэрийг буцаана
  4. robLinear () дараах байдлаар ажиллана:
    1. Гэж оруулсан ба хассан хоёр хувьсагчийг эхлүүлнэ 0, одоогийн элементийг оруулах, хасах замаар олж авсан хамгийн их үр дүнг хадгалдаг
    2. Дараагийн давталт бүрт одоогийн элемент + болдог хасагдсан өмнөх элементийн үр дүн
    3. Хасагдсан нь хамгийн дээд хэмжээ болно оруулах болон хасагдсан өмнөх элементийн үр дүн
  5. RobLinear-ийн дээд хэмжээг буцаана уу(1, N - 1) ба robin Шулуун(2, N)
мөн үзнэ үү
Lemonade Change Leetcode шийдэл

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) Зөвхөн тогтмол орон зайг хувьсагчдын хувьд ашигладаг.