هائوس رابرٽ II ليٽ ڪوڊ جو حل


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب Amazon ايپل eBay گوگل Microsoft جي والارٽ ليبز
متحرڪ پروگرامنگ

“هائوس رابرٽ II” جي مسئلي ۾ ، هڪ robر مختلف گھرن کان پئسا وٺڻ چاهي ٿو. گهرين ۾ رقم جي مقدار هڪ صف جي ذريعي ڏيکاريل آهي. اسان کي وڌ کان وڌ رقم ڳولڻ جي ضرورت آهي جيڪا هيٺين شرطن مطابق ڏنل صف ۾ عناصر شامل ڪندي ٺاهي سگهجي ٿي.

  1. غالباً يڪدم ٻه ٻه گهر robري نٿو سگهي. اھو آھي ، اسان پنھنجي مجموعي ۾ ٻه مسلسل عنصر شامل نٿا ڪري سگھون. جيڪڏهن ith عنصر شامل ڪيو ويو نتيجو ، پوءِ (مان + 1)ٿ ۽ (مان - 1)عنصر لازمي طور خارج ڪيو ويو.
  2. صف سرڪشي آهي. .، پهريون ۽ آخري عنصر پڻ هڪٻئي جي ڀرسان آهن.

مثال

1 5 4 2
7
4 5 6 8 3
13

پهچ (زبردستي قوت)

مسئلو اسان کان گھربل رقم کي وڌيڪ مقدار ۾ شامل ڪرڻ جي وڌ کان وڌ مقدار ڳولڻ جي ضرورت آهي. اسان غير ترتيب وارن عنصرن تي مشتمل هر تسلسل جي ميلاپ کي جانچڻ لاءِ بروٽ فورس هلائي سگهون ٿا. پر ، انڊيڪس 1st ۽ اين اصل ۾ جڙيل آهن. تنهن ڪري ، اسان کي لازمي طور تي انهن ٻنهي کي شامل نه ڪرڻ جي نتيجي ۾ هجڻ گهرجي. بدقسمتي سان ، اسان سڀاڻي کان وڌ کان وڌ رقم ڳولي سگھون ٿا[1 ، اين - 1] ۽ ماتحت[2 ، اين] الڳ الڳ. ھاڻي ، ٻنهي صورتن جي لڪيرون آھن. نتيجو وڌ کان وڌ ٿيندو ، ٻه ذيلي ذخيرو.

هاڻي ، اچو ته ڪنهن به عام لڪير واري قطار جو مسئلو حل ڪريون. جيئن اسين سمجهون ٿا ته گردش صف ۾ غائب آهي ۽ اها پهرين عنصر کان شروع ٿيندي آهي ۽ آخري تي ختم ٿيندي آهي ، اسان انهي کي پهرين ۽ آخري عنصر کي ويجهي سمجهندا کان ڌار ڪيو آهي.

اهو واضح ٿي چڪو آهي ته اسان يا ته:

  1. شامل اسان جي رقم ۾ ڪوبه عنصر.
  2. شامل ڪريو اهو عنصر.

اهڙي صورت ۾ ، اسان سڀ ممڪن طريقي سان پيدا ڪيل رقم ڳولي سگهون ٿا نه متواتر عنصر. سڀ ممڪن ميلاپ ڳولڻ لاءِ ، اسان استعمال ڪري سگھون ٿا واپسي ۽ پٺتي پيل. هر ايراضي ڪال ۾ ، اسان يا ته عنصر پنهنجي نتيجي جي رقم ۾ شامل ڪنداسين يا ان کي ڌار ڪيو. ان بنياد تي ، جيڪڏھن اسان انڊيڪس تي ڪو عنصر چونڊون I, پوءِ ايندڙ انڊيڪس هئڻ گهرجي مان + 2 ، I + 3.…. آخري عنصر تائين. ساڳي طرح ، جيڪڏهن اسان انڊيڪس تي هڪ عنصر خارج ڪيو I, اسان انڊيڪس تي ايندڙ ريورس کي سڏ ڪري سگهون ٿا مان + 1 ، هن کان شروع ٿيڻ جا سڀ امڪان جانچڻ هن طريقي سان ، اسان هر عنصر کي شامل ۽ خارج ڪرڻ جا امڪان جانچيندا آهيون. انهي سان گڏ ، سڀئي عنصر جيڪي رقم قائم ڪندا هوندا غير متوقع جئين اسان هر متبادل انڊيڪس تي اچو ٿا.

الورورٿم

  1. جيڪڏهن صف خالي آهي ، واپسي 0;
  2. جيڪڏھن صف ھڪڙي ھڪ عنصر آھي
    • اسان صف کي ٻن حصن ۾ ورهائي نٿا سگهون. تنهن ڪري ، صف ۾ واحد عنصر واپس ڪريو
  3. هڪ متغير برقرار رکندي ، وڌ کان وڌ_ ممڪن_ ممڪن هجي ، جيڪا ممڪن مقدار ۾ وڌ ۾ وڌ ذخيرو ڪري ڇڏين
  4. ڪال جي ترغيب واري فنڪشن تي ڪال ڪريو ميلاپ () سبري ۾ ايندڙ هر چڪاس لاءِ چڪاس ڪرڻ [1، N - 1] ۽ [2، N]
    • ميلاپ ()  وٽس هر بحريه جي رقم کي ذخيرو ڪرڻ لاءِ پيٽرولر آهي cur_sum
    • جيڪڏھن اسان آخري عنصر کي پار ڪيو آھي جيڪڏھن صف ، موٽڻ
    • هاڻي ، اچو ته سڀني امکانات کي چڪاس ڪريون جيڪي اسان ٺاهي سگهون ٿا سميت موجوده انڊيڪس ويليو
      • موجوده انڊيڪس ويليو کي شامل ڪريو cur_sum
      • متبادل انڊيڪس کان شروع ٿيندڙ هڪ لوپ هليو ته جيئن اسان هن انڊيڪس مان هر غير متواتر عنصر کي ٽپو ڏئي سگهون
      • بوٽ ميلاپ () انهن اشارن تي
    • اچو ته چيڪ ڪريو امڪان جڏهن موجوده عنصر شامل نه آهي
      • cur_sum مان موجوده انڊيڪس ويليو کي گهٽايو ، هتي اسين پٺڀرائي اسان جو حل
      • بوٽ ميلاپ () ايندڙ انڊيڪس تي ، جيئن اسان موجوده انڊيڪس کي خارج ڪيو آهي
    • هر مرحلي تي ، اسان اهو پڙتال ڪريون ٿا kur_sum> max_sum_ ممڪن ۽ انهي کي تازه ڪاري
  5. نتيجو ڇاپيو

هائوس رابر II کي حل ڪرڻ لاءِ الگورتھم جو نفاذ

سي ++ پروگرام

#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(اين 2 ^ اين) جيئن اسين ناانصافي عنصرن تي مشتمل هر ممڪن ڪاميابي پيدا ڪريون ٿا.

خلائي پيچيدگي

اي (اين) recursive stack frames جي ڪري

پهچ (متحرڪ پروگرامنگ)

اسان پوئين طريقي تي بحث ڪيو ته ڪنھن خاص انڊيڪس تي ، اسين ڪري سگھون ٿا

  • شامل اسان جي رقم ۾ عنصر.
  • شامل ڪريو عنصر.

هائوس رابرٽ II ليٽ ڪوڊ جو حل

فرض ڪيو اين [i ، N] سڀ کان وڌيڪ رقم اسان حد تائين حاصل ڪري سگهون ٿا i جي طرف N. اهو نتيجو وڌيڪ انحصار ڪندو آهي اين ايس [i + 2 ، N] ۽ اين ايس [i + 1 ، N]. اسان هر رينج کي غور ڪري سگهون ٿا رياست اهڙي طرح هر رياست وڌيڪ منحصر هوندو آهي ذيلي رياستون. ممڪن آهي ته اسان کي ٻيهر ڪنهن خاص رياست جي لاءِ ٻيهر والدين جي رياست جي مسئلن کي حل ڪرڻ جي لاءِ بار بار جي ضرورت آهي. هي آهي وڌ کان وڌ بنيادي ادغام. اسان اهو به نتيجو ڪري سگهون ٿا ته اين اين جي سائيز جي وڌ لاءِ ، وڌ کان وڌ رقم جيڪا سڀني اين اين عناصر مان حاصل ڪري سگهجي ٿي انهن ٻن نتيجن جي وڌ ۾ وڌ آهي.

  • حاصل ٿيندڙ وڌ کان وڌ نتيجو (ن - 1) عنصر ۽ نيٿ عنصر سميت
  • بھترين نتيجو حاصل ڪيو (ن - 1) ۽ ناٿ عنصر کي ڪ excي ڇڏيو

اسان هڪ ٽيبل ٺاهي سگهون ٿا ائين ٽيبل [i] ذخيرو ڪندي حاصل ڪري سگھجي ٿو تمام گھڻي رقم جيڪا ماتحت حاصل ڪري سگھجي ٿي [0، i]. پر ، ٻه اشارا آهن ٻه چونڊون. تنهن ڪري ، اسان کي ڪيسن جي ٻن مختلف نتيجن کي اسٽور ڪرڻ جي ضرورت آهي: جڏهن عنصر شامل هجي ۽ جڏهن عنصر خارج ٿئي.

الورورٿم

  1. جيڪڏھن صف خالي آھي ، 0 واپس آڻيو
  2. جيڪڏھن صف ۾ صرف ھڪڙو عنصر آھي ، اھو عنصر واپس ڪريو
  3. ڪم ٺاهيو راب لائنر () اھو وڌ ۾ وڌ رقم واپس آڻيندو آھي جيڪي لڪير جي ترتيب ۾ حاصل ڪري سگھجن
  4. راب لائنر () هيٺيان ڪم ڪري ٿو:
    1. شروع ڪيل ٻه متغير شامل ۽ خارج ٿيڻ وانگر 0, جيڪو موجوده نتيجن کي ترتيب ڏيڻ ۽ خارج ڪرڻ سان حاصل ڪيل وڌايل نتيجا حاصل ڪري ٿو
    2. هر ايندڙ ورشن تي ، شامل موجوده عنصر + ٿي ويندو شامل ٿيل پوئين عنصر جو نتيجو
    3. خارج ٿي ويندو آهي وڌ کان وڌ شامل ۽ شامل ٿيل پوئين عنصر جا نتيجا
  5. روبينار جي وڌ کان وڌ موٽايو(1 ، اين - 1) ۽ روبينار(2 ، ن)

هائوس رابر II کي حل ڪرڻ لاءِ الگورتھم جو نفاذ

سي ++ پروگرام

#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 کي حل ڪرڻ جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (اين) ، اسان 2 وقت لاءِ صف جو سفر ڪيو. تنهن ڪري ، اسان O (2N) آپريشن ٺاهيون ٿا ، جيڪو لائين وارو آهي.

خلائي پيچيدگي

اي (1) صرف مستقل جڳهه متغيرن لاءِ استعمال ٿيندي آهي.