हाऊस रॉबर II लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद हा कोड eBay Google मायक्रोसॉफ्ट वॉलमार्ट लॅब
डायनॅमिक प्रोग्रामिंग

“हाऊस रॉबर II” च्या समस्येमध्ये दरोडेखोरांना वेगवेगळ्या घरांकडून पैसे लुटण्याची इच्छा असते. घरामधील पैशांची रक्कम अ‍ॅरेद्वारे दर्शविली जाते. आम्हाला खालील अटींनुसार दिलेल्या अ‍ॅरेमध्ये घटक जोडून तयार केले जास्तीत जास्त पैसे शोधण्याची आवश्यकता आहे:

  1. दरोडेखोर सलग दोन घरे लुटू शकत नाही. म्हणजेच, आम्ही आपल्या बेरीजमध्ये सलग दोन घटक समाविष्ट करू शकत नाही. जर आयथ नंतर निकालामध्ये घटक जोडला जातो (i + 1)व्या आणि (i - 1)व्या घटक वगळणे आवश्यक आहे.
  2. अ‍ॅरे गोलाकार आहे. तर, द प्रथम आणि शेवटचा घटक देखील एकमेकांना जवळ आहेत.

उदाहरण

1 5 4 2
7
4 5 6 8 3
13

दृष्टीकोन (ब्रुट फोर्स)

अ‍ॅरेमध्ये सलग नसलेले घटक जोडून तयार करता येणारी जास्तीत जास्त रक्कम शोधण्यासाठी समस्येची आवश्यकता असते. सलग घटक नसलेले प्रत्येक अनुक्रम संयोजन तपासण्यासाठी आम्ही ब्रूट फोर्स चालवू शकतो. परंतु, निर्देशांक 1st आणि नववी प्रत्यक्षात समीप आहेत. तर, या दोघांना आमच्या निकालात समाविष्ट न करण्याची खात्री आपण केली पाहिजे. अंतर्ज्ञानाने, आम्ही सबॅरेमधून जास्तीत जास्त बेरीज शोधू शकतो[1, एन - 1] आणि subarray[२, एन] स्वतंत्रपणे. आता दोन्ही सबरी रेषात्मक आहेत. दोन सबब्रे-बेरीजपैकी जास्तीत जास्त निकाल मिळेल.

आता कोणत्याही सामान्य रेषीय अ‍ॅरेसाठी समस्या सोडवू. जसे आपण असे गृहीत धरतो की वर्तुळाकार अ‍ॅरेमध्ये अनुपस्थित आहे आणि ते पहिल्या घटकापासून सुरू होते आणि शेवटपर्यंत समाप्त होते, तेव्हा आपल्याला प्रथम आणि शेवटचे घटक जवळचे समजण्यापासून मुक्त केले आहे.

हे स्पष्ट झाले आहे की आम्ही एकतर करू शकतोः

  1. समावेश आमच्या बेरीज कोणत्याही घटक.
  2. वगळा तो घटक.

अशा परिस्थितीत, आम्ही सर्व संभाव्य अनुक्रमांद्वारे तयार केलेली बेरीज शोधू शकतो अविरत घटक. सर्व शक्य जोड्या शोधण्यासाठी, आम्ही वापरू शकतो रिकर्सियन आणि बॅकट्रॅकिंग. प्रत्येक रिकर्सीव्ह कॉलमध्ये आम्ही आमच्या परिणामामध्ये एक घटक समाविष्ट करू किंवा त्यास वगळू. त्या आधारे, जर आपण अनुक्रमणिकेत कोणतेही घटक निवडले तर I, तर पुढील अनुक्रमणिका असावी I + 2, I + 3.…. शेवटच्या घटकापर्यंत त्याचप्रमाणे जर आपण अनुक्रमणिकेतील एखादे घटक वगळले तर I, आम्ही अनुक्रमणिकेवर पुढील पुनरावृत्ती कॉल करू शकतो I + 1, त्यातून उद्भवणार्‍या सर्व शक्यता तपासण्यासाठी. अशाप्रकारे, आम्ही प्रत्येक घटक समाविष्ट आणि वगळण्याची शक्यता तपासतो. तसेच, बेरीज तयार करणारे सर्व घटक असतील सलग जसे आपण प्रत्येक पर्यायी निर्देशांकावर जाऊ.

अल्गोरिदम

  1. जर अ‍ॅरे रिक्त असेल तर परत या 0;
  2. जर अ‍ॅरेमध्ये एक घटक असेल
    • आम्ही अ‍ॅरेचे दोन भागात विभाजन करू शकत नाही. Arरेमधील एकमेव घटक परत करा
  3. जास्तीत जास्त बेरीज ठेवणारे व्हेरिएबल मॅक्स_सम_पॉसिबल ठेवा
  4. कॉल रिकर्सीव्ह फंक्शन जोड्या () सबर्रे [1, एन - 1] आणि [2, एन] मधील प्रत्येक अनुक्रम तपासण्यासाठी
    • जोड्या ()  प्रत्येक अनुक्रमांची बेरीज म्हणून संचयित करण्यासाठी पॅरामीटर आहे cur_sum
    • जर अ‍ॅरेचा शेवटचा घटक आपण पार केला असेल तर परत.
    • आता आपण करू शकू अशा सर्व शक्यता तपासू यासह वर्तमान निर्देशांक मूल्य
      • मध्ये वर्तमान निर्देशांक मूल्य जोडा cur_sum
      • वैकल्पिक निर्देशांकापासून सुरू होणारे लूप चालवा जेणेकरुन आम्ही या निर्देशांकातील प्रत्येक नॉन-सलग घटकावर जाऊ शकतो
      • कॉल जोड्या () या निर्देशांकांवर
    • चालू घटक समाविष्ट नसताना शक्यता तपासू या
      • येथे आम्ही cur_sum वरून सद्य निर्देशांक मूल्य वजा करा बॅकट्रॅक आमचे समाधान
      • कॉल जोड्या () पुढील अनुक्रमणिकेवर जसे आपण वर्तमान अनुक्रमणिका वगळली आहे
    • प्रत्येक चरणात, आम्ही cur_sum> max_sum_possable आणि ते अद्ययावत करतो का ते तपासतो
  5. निकाल प्रिंट करा

हाऊस रॉबर II सोडविण्यासाठी अल्गोरिदमची अंमलबजावणी 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(एन .२. एन) जसे की आम्ही अविरत घटक असलेले प्रत्येक संभाव्य अनुक्रम तयार करतो.

जागेची जटिलता

ओ (एन) रिकर्सिव स्टॅक फ्रेम्समुळे

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

आम्ही मागील दृष्टिकोनातून चर्चा केली की कोणत्याही विशिष्ट निर्देशांकात आम्ही ते करू शकतो

  • समावेश आमच्या बेरीजमधील घटक.
  • वगळा घटक.

हाऊस रॉबर II लीटकोड सोल्यूशन

समजा उत्तर [मी, एन] आम्ही श्रेणीमध्ये मिळवू शकणारी जास्तीत जास्त रक्कम आहे i ते N. हा परिणाम पुढील उत्तरांवर [i + 2, N] आणि उत्तर [i + 1, N] वर अवलंबून असेल. आम्ही प्रत्येक श्रेणीचा ए म्हणून विचार करू शकतो राज्य असे की प्रत्येक राज्य यापुढे उप-राज्यांवर अवलंबून आहे. हे शक्य आहे की पालकांच्या इतर समस्यांचे निराकरण करण्यासाठी आम्हाला वारंवार कोणत्याही विशिष्ट राज्यासाठी वारंवार सोडवणे आवश्यक आहे. हे एक आहे इष्टतम उपस्ट्रक्चर. आम्ही असा निष्कर्ष देखील काढू शकतो की आकार N च्या अ‍ॅरेसाठी, सर्व 'एन' घटकांकडून मिळवलेली जास्तीत जास्त बेरीज या दोन परिणामांमधील कमाल आहे:

  • पर्यंत इष्टतम निकाल प्राप्त (एन - 1) घटक आणि Nth घटकासह
  • पर्यंत सर्वोत्कृष्ट निकाल (एन - 1) आणि Nth घटक वगळता

आपण असे टेबल तयार करू शकतो सारणी [मी] सबर्रे [0, i] वापरून मिळवता येणारी जास्तीत जास्त रक्कम संग्रहित करते. परंतु, प्रत्येक निर्देशांकासाठी दोन पर्याय असतात. तर, प्रकरणांसाठी आम्हाला दोन भिन्न परिणाम संग्रहित करण्याची आवश्यकता आहे: जेव्हा घटक समाविष्ट असतो आणि जेव्हा घटक वगळला जातो.

अल्गोरिदम

  1. अ‍ॅरे रिक्त असल्यास 0 परत करा
  2. जर अ‍ॅरेमध्ये फक्त एक घटक असेल तर तो घटक परत करा
  3. एक फंक्शन तयार करा रोबलाइनर () जे एका रेषीय अ‍ॅरेमध्ये मिळवता येऊ शकते कमाल रक्कम मिळवते
  4. रोबलाइनर () खालीलप्रमाणे कार्य करते:
    1. समाविष्ट केलेले आणि वगळलेले दोन चल सुरू करा 0, जे सध्याच्या घटकास अनुक्रमे समाविष्ट करून आणि वगळून प्राप्त होणारे कमाल परिणाम संचयित करते
    2. प्रत्येक पुढील पुनरावृत्तीच्या वेळी समाविष्ट केलेला वर्तमान घटक + बनतो वगळले मागील घटकाचा परिणाम
    3. वगळले जास्तीत जास्त होते समाविष्ट आणि वगळले मागील घटकाचा परिणाम
  5. जास्तीत जास्त रोबलाइनर परत करा(1, एन - 1) आणि robLinear(2, एन)

हाऊस रॉबर II सोडविण्यासाठी अल्गोरिदमची अंमलबजावणी 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 वेळा मागे टाकतो. तर, आम्ही ओ (2 एन) ऑपरेशन्स करतो, जे रेषीय असतात.

जागेची जटिलता

ओ (1) व्हेरिएबल्ससाठी फक्त स्थिर जागा वापरली जाते.