ቤት ወንበዴ II Leetcode መፍትሔ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም eBay google የ Microsoft የዎልማርት ላብራቶሪዎች
ተለዋዋጭ ፕሮግራም

በ “ቤት ዘራፊ II” ችግር ውስጥ አንድ ዘራፊ ከተለያዩ ቤቶች ገንዘብ መዝረፍ ይፈልጋል ፡፡ በቤቶቹ ውስጥ ያለው የገንዘብ መጠን በድርድር በኩል ይወክላል። በሚከተሉት ሁኔታዎች መሠረት በአንድ በተወሰነ ድርድር ውስጥ ያሉትን ንጥረ ነገሮች በመጨመር ሊገኝ የሚችለውን ከፍተኛውን ገንዘብ መፈለግ አለብን

  1. ወንበዴው ማንኛውንም ሁለት ተከታታይ ቤቶችን መዝረፍ አይችልም ፡፡ ማለትም እኛ ሁለት ድምር ንጥረ ነገሮችን በድምራችን ማካተት አንችልም። ከሆነ እ.ኤ.አ. ith ንጥረ ነገር በውጤቱ ላይ ታክሏል ፣ ከዚያ (እኔ + 1)ኛ እና (እኔ - 1)ኛ አባል መወገድ አለበት።
  2. ድርድሩ ክብ ነው። ስለዚህ ፣ እ.ኤ.አ. አንደኛየመጨረሻ ንጥረ ነገሮች እርስ በእርሳቸው ተጓዳኝ ናቸው።

ለምሳሌ

1 5 4 2
7
4 5 6 8 3
13

አቀራረብ (የደስታ ኃይል)

ችግሩ በምድቡ ውስጥ ተከታታይ ያልሆኑ ንጥረ ነገሮችን በመጨመር የሚመረተውን ከፍተኛውን ድምር እንድናገኝ ያስገድደናል። ተከታታይ ያልሆኑ አባሎችን የያዘ እያንዳንዱን ቅደም ተከተል ጥምረት ለመፈተሽ የጭካኔ ኃይልን ማስኬድ እንችላለን። ግን ፣ ማውጫዎቹ 1stኛ በእውነቱ ተጎራባች ናቸው ፡፡ ስለዚህ በውጤታችን ውስጥ ሁለቱንም ላለማካተት ማረጋገጥ አለብን ፡፡ በአስተውሎት ፣ ከከፍተኛው ንዑስ ቡድን ከፍተኛውን ድምር ማግኘት እንችላለን[1 ፣ N - 1] እና ንዑስ መርከብ[2, N] በተናጠል. አሁን ሁለቱም subarrays መስመራዊ ናቸው ፡፡ ውጤቱ ከሁለቱ ንዑስ-ንዑስ-ድምር ከፍተኛው ይሆናል ፡፡

አሁን ለማንኛውም አጠቃላይ መስመራዊ ድርድር ችግሩን እንፍታ ፡፡ ክብ ክብነቱ በምድቡ ውስጥ እንደሌለ እና ከመጀመሪያው ንጥረ ነገር ጀምሮ እስከ መጨረሻው መስመራዊ ነው ብለን ስናስብ የመጀመሪያ እና የመጨረሻውን አካል እንደአጠገብ ከግምት ውስጥ አስገብተናል ፡፡

እኛ ወይ ማድረግ እንደምንችል አሁን ግልፅ ነው-

  1. አካት በእኛ ድምር ውስጥ ማንኛውም አካል
  2. አያካተት ያ አካል

በእንደዚህ ዓይነት ሁኔታ ውስጥ ሊሆኑ በሚችሉ ቅደም ተከተሎች ሁሉ የተሰራውን ድምር ማግኘት እንችላለን ተከታታይ ያልሆኑ አካላት. ሁሉንም ሊሆኑ የሚችሉ ጥምረቶችን ለማግኘት ፣ እኛ ልንጠቀምባቸው እንችላለን መልሶ መሰብሰብ እና መልሶ መከታተል። በእያንዳንዱ ተደጋጋሚ ጥሪ ውስጥ ንጥረ ነገሮቻችንን በውጤታችን ድምር ውስጥ እናካትታለን ወይም አናገለለውም ፡፡ በዚያ ላይ በመመስረት ፣ በመረጃ ጠቋሚ ላይ ማንኛውንም ንጥረ ነገር ከመረጥን I, ከዚያ የሚቀጥለው ማውጫ መሆን አለበት እኔ + 2 ፣ እኔ + 3.…. እስከ መጨረሻው አካል። በተመሳሳይ እኛ በመረጃ ጠቋሚ ላይ አንድ አባል ካላስወገድን I, በሚቀጥለው ማውጫ ላይ በመረጃ ጠቋሚ ላይ መደወል እንችላለን እኔ + 1 ፣ ከእሱ የሚመጡትን ሁሉንም ዕድሎች ለማጣራት ፡፡ በዚህ መንገድ እያንዳንዱን ንጥረ ነገር ለማካተት እና ለማግለል እድሎችን እንፈትሻለን ፡፡ እንዲሁም ድምርን የሚያዋቅሩ ሁሉም አካላት ይሆናሉ ተከታታይ ያልሆነ ወደ እያንዳንዱ ተለዋጭ መረጃ ጠቋሚ ስንዘል ፡፡

አልጎሪዝም

  1. ድርድሩ ባዶ ከሆነ ይመለሱ 0;
  2. ድርድሩ አንድ አካል ካለው
    • አደረጃጀቱን በሁለት ክፍሎች መክፈል አንችልም። ስለዚህ ፣ በድርድሩ ውስጥ ያለውን ብቸኛ አካል ይመልሱ
  3. የሚቻለውን ከፍተኛውን ድምር የሚያከማች ተለዋጭ ፣ ከፍተኛ__ስም_ይቻላል
  4. እንደገና የማጠናቀር ተግባር ይደውሉ ጥምረት () በእያንዳንዱ ንዑስ ክፍል ውስጥ ያለውን ቀጣይ ቅደም ተከተል ለማጣራት [1 ፣ N - 1] እና [2, N]
    • ጥምረት ()  የእያንዲንደ ተከታይ ድምርን ሇማከማቸት ግቤት አሇው cur_sum
    • ከድርድሩ የመጨረሻውን አካል ከተሻገርን ፣ መመለስ.
    • አሁን እኛ ልንሠራባቸው የምንችላቸውን ሁሉንም አማራጮች እንመርምር ጭምር የአሁኑ የመረጃ ጠቋሚ እሴት
      • የአሁኑን የመረጃ ጠቋሚ እሴት ወደ ላይ ያክሉ cur_sum
      • ከዚህ መረጃ ጠቋሚ ወደ እያንዳንዱ ተከታታይ ያልሆነ አካል ለመዝለል እንድንችል ከአማራጭ መረጃ ጠቋሚ ጀምሮ ቀለበት ያሂዱ
      • ጥሪ ጥምረት () በእነዚህ ማውጫዎች ላይ
    • የአሁኑ ንጥረ ነገር ባልተካተተበት ጊዜ እድሉን እንፈትሽ
      • የአሁኑን የመረጃ ጠቋሚ እሴት ከ cur_sum ይቀንሱ ፣ እዚህ እኛ ነን ጀርባ መፍትሄያችን
      • ጥሪ ጥምረት () የአሁኑን ማውጫ እንዳገለልን በሚቀጥለው ኢንዴክስ ላይ
    • በእያንዳንዱ ደረጃ ፣ cur_sum> max_sum_ የማይቻል ከሆነ እናረጋግጣለን እናዘምንበታለን
  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 Leetcode መፍትሔ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

O(N.2 ^ ኤንተከታታይ ያልሆኑ አባሎችን የያዘ እያንዳንዱን ቀጣይ ውጤት እንደምናመነጭ።

የቦታ ውስብስብነት

ኦ (ኤን) ምክንያት recursive ቁልል ፍሬሞች

አቀራረብ (ተለዋዋጭ ፕሮግራም)

በቀደመው አካሄድ በየትኛውም ልዩ መረጃ ጠቋሚ ላይ እንደምንችል ተወያይተናል

  • አካት በእኛ ድምር ውስጥ ያለው ንጥረ ነገር
  • አያካተት ንጥረ ነገሩ።

ቤት ወንበዴ II Leetcode መፍትሔ

መገመት ans [i, N] በክልሉ ውስጥ ማግኘት የምንችለው ከፍተኛው ድምር ነው i ወደ N. ይህ ውጤት በእንስሶች [i + 2 ፣ N] እና በ ans [i + 1, N] ላይ የበለጠ የሚመረኮዝ ይሆናል። እያንዳንዱን ክልል እንደ አንድ ልንቆጥረው እንችላለን ግዛት እያንዳንዱ ክልል በይበልጥ በክፍለ-ግዛቶች ላይ የተመሠረተ ነው ፡፡ ሌሎች የወላጅ ሁኔታ ችግሮችን ለመፍታት እንደገና ለማንኛውም ክልል እንደገና መፍታት ያስፈልገናል ፡፡ ይህ አንድ ነው የተመቻቸ ንዑስ መዋቅር. እንዲሁም ለ ‹N› ብዛት ፣ ከሁሉም ‹n› አካላት ሊገኝ የሚችለው ከፍተኛው ድምር የእነዚህ ሁለት ውጤቶች ከፍተኛ ነው ብለን መደምደም እንችላለን-

  • የተገኘው ውጤት እስከ (N - 1) አባሎች እና የ Nth ን አካልን ጨምሮ
  • እስከዚህ ድረስ የተገኘ ምርጥ ውጤት (N - 1) የኒን ንጥረ ነገርን ሳይጨምር

እንደዚህ ያለ ጠረጴዛ መፍጠር እንችላለን ጠረጴዛ [i] ንዑስ ክፍልን በመጠቀም ሊገኝ የሚችለውን ከፍተኛ ድምር ያከማቻል [0, i] ግን ፣ ለእያንዳንዱ መረጃ ጠቋሚ ሁለት ምርጫዎች አሉ ፡፡ ስለዚህ ለጉዳዮች ሁለት የተለያዩ ውጤቶችን ማከማቸት አለብን-ኤለመንቱ ሲካተት እና ንጥረ ነገሩ ሲገለል ፡፡

አልጎሪዝም

  1. ድርድሩ ባዶ ከሆነ 0 ን ይመልሱ
  2. ድርድሩ አንድ አካል ብቻ ካለው ያንን ንጥረ ነገር ይመልሱ
  3. ተግባር ይፍጠሩ robLinear () በመስመራዊ ድርድር ውስጥ ሊገኝ የሚችለውን ከፍተኛውን ድምር ይመልሳል
  4. robLinear () እንደሚከተለው ይሠራል
    1. እንደ ሁለት የተካተቱ እና የተገለሉ ሁለት ተለዋዋጮችን ያስጀምሩ 0, የአሁኑን ንጥረ ነገር በቅደም ተከተል በማካተት እና በማግለል የሚገኘውን ከፍተኛ ውጤት ያከማቻል
    2. በእያንዳንዱ ቀጣይ ድግግሞሽ ላይ የተካተተው የአሁኑ ንጥረ ነገር + ይሆናል አልተካተተም የቀድሞው ንጥረ ነገር ውጤት
    3. የተገለለ ከፍተኛው ይሆናል ተካቷልአልተካተተም የቀድሞው ንጥረ ነገር ውጤቶች
  5. ከፍተኛውን የ robLinear ይመልሱ(1 ፣ N - 1) እና robLinear(2 ፣ ኤን)

የቤት ዘራፊ 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 ን የመፍታት ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ድርድርን ለ 2 ጊዜ እናቋርጣለን። ስለዚህ ፣ እኛ (2N) ኦፕሬሽኖችን እናደርጋለን ፣ እሱም መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (1) ለተለዋጮች ብቻ ቋሚ ቦታ ብቻ ጥቅም ላይ ይውላል።