د کور غلو II لیټکوډ حل


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه ebay لکه د ګوګل د Microsoft د وال مارټ لیبز
متحرک برنامې

د "هاؤس رابرټ II" ستونزه کې ، یو غل غواړي چې د مختلف کورونو څخه پیسې لوټ کړي. په کورونو کې د پیسو مقدار د صف له لارې ښودل کیږي. موږ اړتیا لرو پورتنۍ پیسې ومومئ چې د لاندې شرایطو مطابق په ورکړل شوي صف کې د عناصرو اضافه کولو سره رامینځته کیدی شي:

  1. غل هیڅ دوه پرله پسې کورونه نشي لوټولی دا ، موږ نشو کولی په خپل رقم کې دوه پرله پسې عناصر شامل کړو. که ith عنصر په پایله کې اضافه شوی ، بیا (i + 1)و او (i - 1)دا عنصر باید خارج شي.
  2. سري سرکلر ده. نو ، د لومړی او وروستی عنصر هم یو بل سره نږدې دي.

بېلګه

1 5 4 2
7
4 5 6 8 3
13

چلند (وحشي ځواک)

ستونزه موږ ته اړتیا لري ترڅو د اعظمي حد اندازه ومومئ چې په سر کې د غیر متقابل عناصرو په اضافه کولو سره تولید کیدی شي. موږ کولی شو یو بروټ ځواک پرمخ وړو ترڅو د ترتیب ناستې عنصر لرونکي هر ترتیب ترکیب چیک کړئ. مګر ، شاخصونه 1st او نهم په حقیقت کې سره نږدې دي. نو ، موږ باید ډاډ ترلاسه کړو چې دا دواړه زموږ په پایله کې نه شاملوي. په قصدي ډول ، موږ کولی شو د subarray څخه اعظمي اندازه ومومئ[1 ، N - 1] او subarray[2 ، N] په جلا توګه. اوس ، دواړه سبریریز خطي دي. پایله به د دوه سبارای - نیمونو څخه اعظمي وي.

اوس ، راځئ چې د هر عمومي خطي صف لپاره ستونزه حل کړو. لکه څنګه چې موږ فرض کوو چې دا سلسله په صف کې شتون نلري او دا د لومړي عنصر څخه پیل او په پای کې پای ته رسیږي ، موږ د نږدې او لومړني عنصر د نږدې په پام کې نیولو څخه خلاص شو.

دا اوس روښانه ده چې موږ یا هم کولی شو:

  1. شامل دي زموږ په مجموع کې کوم عنصر.
  2. ایستل هغه عنصر.

په داسې حالت کې ، موږ کولی شو هغه رقم ومومئ چې د ټولو احتمالي سلسلو درلودو سره تولید شوي نا ثابت عنصرونه. د ټولو احتمالي ترکیبونو موندلو لپاره ، موږ وکاروو تکرار او شاتړ. په هر تکراري کال کې ، موږ به یا زموږ عنصر په پایله کې عنصر شامل کړو یا یې خارج کړو. د دې پراساس ، که موږ په شاخص کې کوم عنصر غوره کړو I, بیا راتلونکي شاخص باید وي I + 2 ، I + 3.…. تر وروستي عنصر پورې په ورته ډول ، که موږ په شاخص کې عنصر خارج کړو I, موږ کولی شو په شاخص کې بل تکرار وغواړو زه + 1 ، ټول امکانات چې له دې څخه سرچینه اخلي چیک کړئ. پدې توګه ، موږ امکانات چیک کوو چې هر عنصر پکې شامل او خارج کړئ. همچنان ، ټول عناصر چې مجموعه تشکیلوي به وي نا منظم لکه څنګه چې موږ هر بدیل شاخص ته ځو.

الګوریتم

  1. که صف خالي وي ، بیرته راشئ 0;
  2. که صف یو عنصر ولري
    • موږ نشو کولی په سر کې په دوه برخو وویشو. نو ، په صف کې یوازینی عنصر بیرته راستانه کړئ
  3. یو متغیر لرونکی ، max_sum_possable وساتئ ، کوم چې د امکان تر حد پورې زیرمه کوي
  4. کال تکرار فعالیت ترکیبونه () په فرعي [1 ، N - 1] او [2 ، N] کې د هرې راتلونکې لپاره چک کول
    • ترکیبونه ()  د هر ضمني برخو مجموعه کولو لپاره پیرامیټر لري cur_sum
    • که موږ وروستي عنصر تیر شو که صف ، راستنیدنه.
    • اوس ، راځئ ټول امکانات وګورو چې موږ یې کولی شو په شمول د اوسني شاخص ارزښت
      • د اوسني لړيزو ارزښت اضافه کړئ cur_sum
      • د بدیل شاخص څخه پیل کولو لپاره لوپ پرمخ وړئ ترڅو موږ وکولی شو له دې شاخص څخه هر غیر ثابت عنصر ته لاړ شو
      • غوښتنه ترکیبونه () په دې شاخصونو کې
    • راځئ چې احتمال وګورو کله چې اوسنی عنصر پکې شامل نه وي
      • د cur_sum څخه د اوسني شاخص ارزښت تخفیف ، دلته موږ شاتړ زموږ حل
      • غوښتنه ترکیبونه () په راتلونکي شاخص کې ، لکه څنګه چې موږ اوسنی شاخص لرې کړی دی
    • په هر ګام کې ، موږ ګورو چې ایا cur_sum> max_sum_possable او دا تازه کړئ
  5. پایله چاپ کړئ

د هاؤس روبر 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';
}

جاوا پروګرام

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

د هاؤس روبر II لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O(N.2. N) لکه څنګه چې موږ هره ممکنه ضمني تولید ولرو چې غیر منظم عنصر پکې شامل وي.

د ځای پیچلتیا

O (N) د تکراري ب stو چوکاټونو له امله

چلند (متحرک برنامې)

موږ په تیرو چلند کې بحث کړی چې په کوم ځانګړي شاخص کې ، موږ کولی شو

  • شامل دي زموږ په مجموع کې عنصر.
  • ایستل عنصر.

د کور غلو II لیټکوډ حل

غاړه اخلي ځواب [i ، N] دا اعظمي اندازه ده چې موږ یې په لړ کې ترلاسه کولی شو i ته N. دا پایله به نور په ځوابونو [i + 2 ، N] او ځوابونو [i + 1 ، N] پورې اړه ولري. موږ کولی شو هره لړۍ د a په توګه په پام کې ونیسو دولت داسې چې هر ایالت بیا په فرعي ایالتونو تکیه کوي. دا ممکنه ده چې موږ اړتیا ولرو چې د هر ځانګړي دولت لپاره په مکرر ډول حل کړئ او د والدین ریاست نورې ستونزې حل کړئ. دا یو مطلوب فرعي جوړښت. موږ دا نتیجه هم اخیستلی شو چې د N کچه اندازه لپاره ، اعظمي اندازه چې د ټولو 'n' عناصرو څخه ترلاسه کیدی شي د دې دوو پایلو اعظمي ده:

  • ترټولو غوره پایلهN - 1) عناصر او د Nth عنصر په شمول
  • تر دې غوره پایله ترلاسه شوې (N - 1) او د Nth عنصر څخه علاوه

موږ کولی شو داسې میز چمتو کړو جدول [i] هغه اعظمي اندازه ذخیره کوي چې د subarray [0 ، i] په کارولو سره ترلاسه کیدی شي. مګر ، د هرې شاخص لپاره دوه انتخابونه دي. نو ، موږ اړتیا لرو د قضیو لپاره دوه مختلف پایلې ذخیره کړو: کله چې عنصر پکې شامل وي او کله چې عنصر خارج شوی وي.

الګوریتم

  1. که صف خالي وي ، 0 بیرته راستانه کړئ
  2. که صف یوازې یو عنصر ولري ، نو هغه عنصر بیرته راشئ
  3. یو فنکشن جوړ کړئ روب لاینار () دا اعظمي اندازه بیرته ورکوي چې په خطي صف کې ترلاسه کیدی شي
  4. روب لاینار () لاندې کار کوي:
    1. دوه متغیرات پیل کړئ شامل دي او لکه څنګه چې خارج شوي 0, کوم چې اعظمي پایلې ذخیره کوي چې په ترتیب سره د اوسني عنصر په شمول او لرې کولو سره ترلاسه کیږي
    2. په هر بل تکرار کې ، شامل اوسني عنصر کیږي + خارج شوی د تیر عنصر پایله
    3. ایستل شوی د اعظمي حد کیږي شامل دي او خارج شوی د تیر عنصر پایلې
  5. د لوټ لاینار اعظمي حد ته راستون کړئ(1 ، ن - 1) او لوټلینار(2 ، N)

د هاؤس روبر 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';
}

جاوا پروګرام

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) ، موږ دوه ځله صف ته ځو. نو ، موږ د O (2N) عملیات کوو ، کوم چې خطي وي.

د ځای پیچلتیا

O (1) یوازې متغیر ځای د تغیر لپاره کارول کیږي.