घर डाकू द्वितीय लीटकोड समाधान


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन एप्पल eBay गुगल माइक्रोसफ्ट वालमार्ट ल्याबहरू
डायनामिक प्रोग्रामिंग

"हाउस डकैर II" समस्यामा एक लुटेरा विभिन्न घरहरूबाट पैसा लुट्न चाहन्छ। घरहरूमा पैसाको रकम एरे मार्फत प्रतिनिधित्व हुन्छ। हामीले तलको सर्तहरू बमोजिम दिइएको एर्रेमा एलिमेन्टहरू थपेर बनाउन सकिने अधिकतम रकम खोज्नु पर्छ:

  1. लुटेरा कुनै दुई लगातार घर लुट्न सक्दैन। त्यो हो, हामी हाम्रो योगमा दुई लगातार तत्वहरू समावेश गर्न सक्दैनौं। यदि ith तत्त्व परिणाममा थपिन्छ, त्यसपछि (i + १)th र (i - २)element तत्वलाई हटाउनु पर्छ।
  2. एरे गोलाकार छ। त्यसो भए पहिलोअन्तिम एलिमेन्ट पनि एक अर्कासँग नजिक छ।

उदाहरणका

1 5 4 2
7
4 5 6 8 3
13

दृष्टिकोण (ब्रुट फोर्स)

समस्याले हामीलाई अधिकतम योगफल फेला पार्नु पर्छ जुन एर्रेमा लगातार नरहेको तत्वहरू थपेर उत्पादन गर्न सकिन्छ। गैर क्रमिक तत्वहरू समावेश गर्ने प्रत्येक अनुक्रम संयोजन जाँच गर्न हामी ब्रुट फोर्स चलाउन सक्छौं। तर, सूचकांक 1stNth वास्तवमा सटेको छ। त्यसोभए, हामीले ती दुबैलाई हाम्रो नतिजामा समावेश नगर्न निश्चित गर्नु पर्छ सहज रूपमा, हामी सबार्रेबाट अधिकतम योग फेला पार्न सक्दछौं[१, N - १] र subarray[२, N] छुट्टै अब दुबै subarrays रेखीय हो। परिणाम दुई subarray- योग को अधिकतम हुनेछ।

अब, कुनै पनि सामान्य रैखिक एर्रे को लागी समस्या समाधान गरौं। जस्तो कि मानौं कि सर्कुलाइट एरेमा अनुपस्थित छ र यो रैखिक हो पहिलो एलिमेन्टबाट सुरू गरेर अन्तमा अन्त्य हुन्छ, हामीले पहिलो र अन्तिम एलिमेन्टलाई नजिकैको रूपमा लिने बाट छुटकारा पाएका छौं।

यो स्पष्ट छ कि हामी कि त:

  1. समावेश हाम्रो योगमा कुनै पनि तत्व।
  2. बहिष्कार त्यो तत्व।

यस्तो अवस्थामा, हामी भएको सबै सम्भावित अनुक्रमहरू द्वारा निर्मित योग पाउन सक्छौं गैर-लगातार तत्वहरू। सबै सम्भावित संयोजनहरू फेला पार्न हामी प्रयोग गर्न सक्दछौं पुनरावृत्ति र ब्याकट्र्याकिंग। प्रत्येक रिकर्सिभ कलमा, हामी या त तत्व समावेश गर्दछ हाम्रो परिणाम योगमा वा यसलाई समावेश गर्दैन। यसको आधारमा, यदि हामी सूचकांकमा कुनै पनि तत्व चयन गर्दछौं I, त्यसो भए अर्को सूचकांक हुनुपर्दछ I + २, I +…।…। अन्तिम तत्व सम्म। त्यस्तै गरी, यदि हामी सूचकांकमा एक तत्व बहिष्कार गर्छौं I, हामी अनुक्रमणिका मा अर्को रिकर्सन कल गर्न सक्छौं I + १, यसबाट सुरु भएका सबै सम्भावनाहरू जाँच गर्न। यस तरिकाले, हामी सबै तत्वहरू समावेश र समावेश गर्न सम्भाव्यता जाँच गर्छौं। साथै, जोड को गठन गर्ने सबै तत्वहरू हुनेछन् लगातार हामी हरेक वैकल्पिक सूचकांकमा जान्छौं।

अल्गोरिदम

  1. यदि एर्रे खाली छ भने, फर्कनुहोस् 0;
  2. यदि एर्रेमा एक तत्व छ
    • हामी एर्रेलाई दुई भागमा विभाजन गर्न सक्दैनौं। त्यसैले एरेमा एलिमेन्ट एलिमेन्ट फिर्ता गर्नुहोस्
  3. भ्यारीएबल, अधिकतम_सुन_मग्न सम्बन्धी प्रबन्ध गर्नुहोस्, जसले अधिकतम योगफल भण्डार गर्दछ
  4. रिकर्सिव प्रकार्य कल गर्नुहोस् संयोजन () सबर्रे [१, N - १] र [२, N] मा हरेक अनुक्रम जाँच गर्न।
    • संयोजन ()  को रूपमा हरेक subcence को योग भण्डार गर्न प्यारामिटर छ cur_sum
    • यदि हामीले अन्तिम एलिमेन्ट पार गर्यौं यदि एर्रे, फर्किनु।
    • अब, हामी द्वारा गर्न सक्ने सबै संभावनाहरू जाँच गर्नुहोस् लगायत हालको अनुक्रमणिका मान
      • हालको अनुक्रमणिका मान थप गर्नुहोस् cur_sum
      • वैकल्पिक अनुक्रमणिकाबाट सुरू गरेर एउटा लूप चलाउनुहोस् जसले गर्दा हामी यस अनुक्रमणिकाबाट हरेक गैर-लगातार तत्वमा जान सक्दछौं
      • कल संयोजन () यी सूचकहरुमा
    • जब सम्भावित तत्व समावेश गरिएको छैन जाँच गरौं
      • हालको अनुक्रमणिका मान cur_sum बाट घटाउनुहोस्, हामी यहाँ छौं ब्याकट्र्याक हाम्रो समाधान
      • कल संयोजन () अर्को सूचकांकमा, किनकि हामीले हालको अनुक्रमणिका बहिष्कार गरेका छौं
    • प्रत्येक चरणमा, हामी जाँच गर्छौं यदि cur_sum> max_sum_possible र यसलाई अपडेट गर्नुहोस्
  5. परिणाम प्रिन्ट गर्नुहोस्

हाउस डाकू दोस्रो समाधान गर्न एल्गोरिथ्मको कार्यान्वयन

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

घर डाकू दोस्रो लीटकोड समाधानको जटिलता विश्लेषण

समय जटिलता

O(N.2। N) जस्तो कि हामी गैर-लगातार तत्वहरू समावेश गर्ने हरेक सम्भावित अनुक्रम उत्पन्न गर्दछौं।

ठाउँ जटिलता

O (N) रिकर्सिव स्ट्याक फ्रेमहरूको कारण

दृष्टिकोण (डायनामिक प्रोग्रामिंग)

अघिल्लो दृष्टिकोणमा हामीले छलफल गरेका थियौं कि कुनै विशेष सूचकांकमा हामी गर्न सक्दछौं

  • समावेश हाम्रो योगमा तत्व।
  • बहिष्कार तत्व।

घर डाकू द्वितीय लीटकोड समाधान

मान्नुहोस् उत्तर [i, N] हामी दायरामा प्राप्त गर्न सक्ने अधिकतम योग हो i लाई N. यो नतीजा उत्तरहरू [i + 2, N] र उत्तरहरू [i + 1, N] मा निर्भर गर्दछ। हामी हरेक दायरा a को रूपमा विचार गर्न सक्छौं राज्य जस्तो कि प्रत्येक राज्य उप-राज्यहरूमा निर्भर गर्दछ। यो सम्भव छ कि हामीले कुनै विशेष राज्यको लागि बारम्बार समाधान गर्न आवश्यक छ र अन्य प्यारेन्ट राज्य समस्याहरू समाधान गर्न। यो एक हो इष्टतम उपस्ट्रक्चर। हामी पनि निष्कर्षमा पुग्न सक्छौं कि आकार N को एक एर्रेका लागि, सबै 'n' तत्त्वहरूबाट प्राप्त गर्न सकिने अधिकतम योग यी दुई परिणामहरूको अधिकतम हो:

  • इष्टतम परिणाम सम्म प्राप्त (N - १) तत्वहरू र Nth तत्व सहित
  • उत्तम परिणाम सम्म प्राप्त (एन - १) र Nth तत्व बाहेक

हामी यस्तो टेबल सिर्जना गर्न सक्छौं तालिका [i] सबभर्रे [०, i] प्रयोग गरेर प्राप्त गर्न सकिने अधिकतम योगफल भण्डार गर्दछ। तर, त्यहाँ हरेक अनुक्रमणिकाको लागि दुई विकल्पहरू छन्। त्यसोभए, हामीले केसहरूको लागि दुई बिभिन्न नतिजाहरू भण्डार गर्न आवश्यक हुन्छ: जब तत्व समावेश हुन्छ र जब तत्व समावेश हुँदैन।

अल्गोरिदम

  1. यदि एर्रे खाली छ भने, ० फिर्ता गर्नुहोस्
  2. यदि एर्रेमा केवल एक तत्व छ भने त्यो तत्व फिर्ता गर्नुहोस्
  3. प्रकार्य सिर्जना गर्नुहोस् robLinear () यसले अधिकतम योग फिर्ता गर्दछ जुन एक रैखिक एर्रेमा प्राप्त गर्न सकिन्छ
  4. robLinear () निम्न कार्य गर्दछ:
    1. दुई भेरिएबलहरू सुरूवात गर्नुहोस् जसलाई समावेश गरिएको थियो र बाहेक 0, जसले अधिकतम परिणामहरू भण्डार गर्दछ जुन हालको तत्त्वलाई क्रमशः समावेश गरेर र बाहेक प्राप्त गरिन्छ
    2. प्रत्येक अर्को पुनरावृत्तिमा, समावेश गरीन्छ छोडिएको अघिल्लो तत्वको परिणाम
    3. बहिष्कारको अधिकतम हुन्छ समावेशछोडिएको अघिल्लो तत्वको परिणामहरू
  5. RobLinear को अधिकतम फिर्ता(१, एन - १) र robLinear(२, N)

हाउस डाकू दोस्रो समाधान गर्न एल्गोरिथ्मको कार्यान्वयन

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

घर डाकू द्वितीयको समाधानको जटिलता विश्लेषण

समय जटिलता

O (N), हामी २ पटक एर्रे पार गर्दछौं। त्यसो भए, हामी हे (2N) अपरेसनहरू गर्छौं, जुन रैखिक हो।

ठाउँ जटिलता

O (१) केवल स्थिर स्थान भ्यारीएबलका लागि प्रयोग गरिन्छ।