ہاؤس ڈاکو II لیٹکوڈ حل


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل ای بے گوگل مائیکروسافٹ والمارٹ لیبز
متحرک پروگرامنگ

"ہاؤس ڈاکو II" کے مسئلے میں ، ایک ڈاکو مختلف گھروں سے رقم لوٹنا چاہتا ہے۔ گھروں میں رقم کی رقم کو ایک صف کے ذریعے پیش کیا جاتا ہے۔ ہمیں مندرجہ ذیل شرائط کے مطابق دیئے گئے صف میں عناصر کو شامل کرکے زیادہ سے زیادہ رقم تلاش کرنے کی ضرورت ہے:

  1. ڈاکو لگاتار دو مکانات نہیں لوٹ سکتا۔ یعنی ، ہم اپنی رقم میں لگاتار دو عناصر کو شامل نہیں کرسکتے ہیں۔ اگر پر ith پھر عنصر کو نتیجہ میں شامل کیا جاتا ہے (i + 1)ویں اور (i - 1)اس عنصر کو خارج کرنا ضروری ہے۔
  2. سرنی سرکلر ہے۔ تو ، سب سے پہلے اور آخری عنصر بھی ایک دوسرے سے ملحق ہیں۔

مثال کے طور پر

1 5 4 2
7
4 5 6 8 3
13

نقطہ نظر (جانور فورس)

مسئلہ کے ل requires ہم سے زیادہ سے زیادہ رقم تلاش کرنے کی ضرورت ہے جو صف میں غیر مستقل عناصر شامل کرکے پیدا کی جاسکے۔ ہم لگاتار عناصر پر مشتمل ہر ترتیب کے مجموعہ کی جانچ کے لئے ایک بروٹ فورس چلا سکتے ہیں۔ لیکن ، انڈیکس 1st اور Nth اصل میں ملحق ہیں۔ لہذا ، ہمیں یقینی بنانا ہوگا کہ ان دونوں کو اپنے نتیجے میں شامل نہ کریں۔ بدیہی طور پر ، ہم سبیارے سے زیادہ سے زیادہ رقم تلاش کرسکتے ہیں[1 ، N - 1] اور subarray[2 ، N] الگ الگ اب ، دونوں subarrays لکیری ہیں. نتیجہ دو سبری رمیوں میں سے زیادہ سے زیادہ ہوگا۔

اب ، کسی بھی عام لکیری صف کے لئے مسئلہ حل کریں۔ جیسا کہ ہم فرض کرتے ہیں کہ سرکولیٹی صف میں موجود نہیں ہے اور یہ پہلے عنصر سے شروع ہونے والی اور آخری حد تک اختتام پذیر ہے ، ہم نے پہلے اور آخری عنصر کو ملحقہ سمجھنے سے چھٹکارا حاصل کر لیا ہے۔

اب یہ واضح ہوچکا ہے کہ ہم یا تو:

  1. شامل کریں ہماری رقم میں کوئی عنصر۔
  2. کو خارج کر دیں وہ عنصر

ایسی صورت میں ، ہم موجود ہر ممکن ترتیب سے پیدا شدہ رقم تلاش کرسکتے ہیں غیر متوقع عناصر. ہر ممکن امتزاج کو تلاش کرنے کے ل we ، ہم استعمال کرسکتے ہیں تکرار اور بیک ٹریکنگ۔ ہر بار آنے والی کال میں ، ہم یا تو عنصر کو اپنے نتیجے میں شامل کریں گے یا اسے خارج کردیں گے۔ اس کی بنیاد پر ، اگر ہم انڈیکس میں کوئی عنصر منتخب کرتے ہیں I, پھر اگلا انڈیکس ہونا چاہئے I + 2، I + 3.…. آخری عنصر تک اسی طرح ، اگر ہم انڈیکس میں کسی عنصر کو خارج کردیں I, ہم انڈیکس پر اگلی تکرار کال کرسکتے ہیں I + 1، اس سے شروع ہونے والے تمام امکانات کی جانچ کرنا۔ اس طرح ، ہم ہر عنصر کو شامل کرنے اور خارج کرنے کے امکانات کی جانچ کرتے ہیں۔ نیز ، جو عنصر ہوگا اس کا مجموعہ ہوگا غیر مسلسل جیسا کہ ہم ہر متبادل انڈیکس پر جاتے ہیں۔

الگورتھم

  1. اگر سرنی خالی ہے تو واپس لوٹ آئیں 0;
  2. اگر سرنی میں ایک عنصر ہے
    • ہم سرنی کو دو حصوں میں تقسیم نہیں کرسکتے ہیں۔ تو ، صف میں صرف عنصر کو واپس کریں
  3. ایک متغیر کو برقرار رکھیں ، زیادہ سے زیادہ_سوم_پوسیبل ، جو زیادہ سے زیادہ رقم کا ذخیرہ کرے
  4. کال recursive تقریب مجموعے () سببارے [1، N - 1] اور [2، N] میں ہر ایک کی پیروی کرنے کے ل to
    • مجموعے ()  کے طور پر ہر حصے کی رقم کو جمع کرنے کے لئے پیرامیٹر ہے cur_sum
    • اگر ہم آخری عنصر کو عبور کرچکے ہیں اگر صف ، واپسی
    • اب ، ہم ان تمام امکانات کو چیک کریں جو ہم کر سکتے ہیں سمیت موجودہ انڈیکس ویلیو
      • موجودہ انڈیکس ویلیو کو اس میں شامل کریں cur_sum
      • متبادل اشاریہ سے شروع ہونے والی لوپ کو چلائیں تاکہ ہم اس انڈیکس سے ہر غیر مستقل عنصر کی طرف جائیں
      • کال مجموعے () ان اشاریوں پر
    • آئیے موجودہ عنصر شامل نہ ہونے پر امکانات کی جانچ کریں
      • ہم یہاں ، cur_sum سے موجودہ انڈیکس ویلیو کو منہا کریں بیکٹیک ہمارا حل
      • کال مجموعے () اگلی انڈیکس پر ، جیسا کہ ہم نے موجودہ انڈیکس کو خارج کردیا ہے
    • ہر مرحلے پر ، ہم چیک کرتے ہیں کہ کیا cur_sum> زیادہ سے زیادہ_ممکن_نظام قابل ہے اور اسے اپ ڈیٹ کریں
  5. نتیجہ پرنٹ کریں

ہاؤس ڈاکو II کے حل کے ل al الگورتھم کا نفاذ

سی ++ پروگرام

#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) بار بار لگنے والے اسٹیک فریموں کی وجہ سے

نقطہ نظر (متحرک پروگرامنگ)

ہم نے گذشتہ نقطہ نظر میں گفتگو کی ہے کہ کسی خاص انڈیکس پر ، ہم کر سکتے ہیں

  • شامل کریں ہماری رقم میں عنصر.
  • کو خارج کر دیں عنصر.

ہاؤس ڈاکو II لیٹکوڈ حل

فرض کریں جوابات [i، N] یہ حد سے زیادہ رقم ہے جو ہم حاصل کرسکتے ہیں i کرنے کے لئے N. اس نتیجہ کا مزید انحصار جوابات [i + 2، N] اور جوابات [i + 1، N] پر ہوگا۔ ہم ہر رینج کو بطور ایک غور کرسکتے ہیں تھے اس طرح کہ ہر ریاست کا مزید انحصار ذیلی ریاستوں پر ہوتا ہے۔ یہ ممکن ہے کہ ہمیں والدین کی دیگر پریشانیوں کو حل کرنے کے لئے بار بار کسی خاص ریاست کے لئے بار بار حل کرنے کی ضرورت ہو۔ یہ ایک ہے زیادہ سے زیادہ ذیلی ساخت. ہم یہ بھی نتیجہ اخذ کرسکتے ہیں کہ سائز N کی ایک صف کے ل all ، زیادہ سے زیادہ رقم جو تمام 'n' عناصر سے حاصل کی جاسکتی ہے وہ ان دو نتائج میں سے زیادہ سے زیادہ ہے:

  • تک موزوں ترین نتیجہ (N - 1) عنصر اور Nth عنصر بھی شامل ہے
  • بہترین نتیجہ حاصل کیا (N - 1) اور Nth عنصر کو چھوڑ کر

ہم ایسی میز بنا سکتے ہیں ٹیبل [i] سب سے زیادہ رقم جمع کرتے ہیں جو subarray [0، i] کا استعمال کرتے ہوئے حاصل کیا جاسکتا ہے۔ لیکن ، ہر انڈیکس کے لئے دو انتخاب ہیں۔ لہذا ، ہمیں مقدمات کے ل two دو مختلف نتائج ذخیرہ کرنے کی ضرورت ہے: جب عنصر شامل ہوتا ہے اور جب عنصر کو خارج نہیں کیا جاتا ہے۔

الگورتھم

  1. اگر سرنی خالی ہے تو ، 0 واپس کریں
  2. اگر صف میں صرف ایک عنصر ہے تو وہ عنصر واپس کریں
  3. ایک فنکشن بنائیں روبوٹ لائنر () جو زیادہ سے زیادہ رقم واپس کرتا ہے جو لکیری صف میں حاصل کیا جاسکتا ہے
  4. روبوٹ لائنر () مندرجہ ذیل کام کرتا ہے:
    1. شامل کریں اور کے طور پر خارج کر دیا گیا دو متغیرات شروع کریں 0, جو بالترتیب موجودہ عنصر کو شامل کرکے اور چھوڑ کر حاصل کیے جانے والے زیادہ سے زیادہ نتائج کو محفوظ کرتا ہے
    2. ہر اگلی تکرار پر ، موجودہ عنصر + شامل ہوجاتا ہے خارج کر دیا گیا پچھلے عنصر کا نتیجہ
    3. خارج کر دیا گیا کی زیادہ سے زیادہ ہو جاتا ہے شامل اور خارج کر دیا گیا پچھلے عنصر کے نتائج
  5. زیادہ سے زیادہ روب لائنر لوٹائیں(1 ، این - 1) اور روبوٹ لائنر(2 ، این)

ہاؤس ڈاکو II کے حل کے ل al الگورتھم کا نفاذ

سی ++ پروگرام

#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) ، ہم 2 بار صف کو عبور کرتے ہیں۔ لہذا ، ہم او (2N) آپریشن کرتے ہیں ، جو لکیری ہوتا ہے۔

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

O (1) متغیر کے لئے صرف مستقل جگہ استعمال کی جاتی ہے۔