בית שודד פתרון Leetcode


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ eBay Google מיקרוסופט מעבדות וולמארט
תכנות דינמי

בבעיית "שודד הבית השני", שודד רוצה לשדוד כסף מבתים שונים. סכום הכסף בבתים מיוצג באמצעות מערך. עלינו למצוא את סכום הכסף המרבי שניתן לעשות על ידי הוספת האלמנטים במערך נתון בהתאם לתנאים הבאים:

  1. השודד אינו יכול לשדוד אף שני בתים רצופים. כלומר, איננו יכולים לכלול שני אלמנטים רצופים בסכום שלנו. אם ה ה- i אלמנט נוסף לתוצאה, ואז (i + 1)th ו (i - 1)יש לא לכלול את האלמנט.
  2. המערך מעגלי. אז ה א ו אחרון אלמנט צמוד גם זה לזה.

דוגמה

1 5 4 2
7
4 5 6 8 3
13

גִישָׁה(כוח פראי)

הבעיה מחייבת אותנו למצוא את הסכום המרבי שניתן לייצר על ידי הוספת אלמנטים שאינם עוקבים במערך. אנו יכולים להפעיל כוח ברוט כדי לבדוק כל שילוב רצפים המכיל אלמנטים שאינם עוקבים. אבל, המדדים 1st ו נ ' למעשה צמודים. לכן עלינו להבטיח שלא לכלול את שניהם בתוצאה שלנו. באופן אינטואיטיבי, אנו יכולים למצוא את הסכום המקסימלי ממערך משנה[1, N - 1] ומערך משנה[2, N] לְחוּד. כעת, שתי המערכות המשניות הן לינאריות. התוצאה תהיה המקסימום של שני סכומי המשנה תת-ערכיים.

עכשיו, בואו נפתור את הבעיה לכל מערך לינארי כללי. מכיוון שאנו מניחים שהמעגליות נעדרת במערך והיא ליניארית החל מהיסוד הראשון וכלה בסוף, נפטרנו מלהחשיב את היסוד הראשון והאחרון כצמוד.

כעת ברור שנוכל:

  1. לכלול כל אלמנט בסכום שלנו.
  2. תכלול האלמנט הזה.

במקרה כזה, אנו יכולים למצוא את הסכום המיוצר על ידי כל הרצפים האפשריים שיש אלמנטים שאינם עוקבים. כדי למצוא את כל השילובים האפשריים, נוכל להשתמש רקורסיה ומסלול חזרה. בכל שיחה רקורסיבית, נכלול את האלמנט בסכום התוצאות שלנו או נחריג אותו. בהתבסס על זה, אם אנו בוחרים אלמנט כלשהו באינדקס I, ואז האינדקס הבא צריך להיות אני + 2, אני + 3. .... עד האלמנט האחרון. באופן דומה, אם לא נכלול אלמנט באינדקס I, אנו יכולים לקרוא לרקורסיה הבאה באינדקס אני + 1, לבדוק את כל האפשרויות שמקורן בו. באופן זה, אנו בודקים את האפשרויות לכלול ולהחריג כל אלמנט. כמו כן, כל האלמנטים המהווים את הסכום יהיו לא רצוף כשאנחנו קופצים לכל אינדקס חלופי.

אַלגוֹרִיתְם

  1. אם המערך ריק, חזור 0;
  2. אם למערך יש אלמנט אחד
    • איננו יכולים לחלק את המערך לשני חלקים. לכן, החזירו את האלמנט היחיד במערך
  3. שמור על משתנה, max_sum_possible, המאחסן את הסכום המרבי האפשרי
  4. פונקציית שיחה רקורסיבית שילובים () כדי לבדוק כל המשך במערך משנה [1, N - 1] ו- [2, N]
    • שילובים ()  יש פרמטר לאחסון סכום כל המשך כ cur_sum
    • אם חצינו את האלמנט האחרון אם המערך, לַחֲזוֹר.
    • עכשיו, בואו נבדוק את כל האפשרויות שאנחנו יכולים לעשות על ידי לְרַבּוֹת ערך המדד הנוכחי
      • הוסף ערך אינדקס נוכחי ל- cur_sum
      • הפעל לולאה החל מהאינדקס החלופי כדי שנוכל לקפוץ לכל אלמנט שאינו רציף מהאינדקס הזה
      • שִׂיחָה שילובים () על המדדים הללו
    • בואו נבדוק את האפשרות כאשר האלמנט הנוכחי אינו כלול
      • גרע את ערך האינדקס הנוכחי מ- cur_sum, הנה אנחנו לַחֲזוֹר עַל עִקבוֹתָיו הפיתרון שלנו
      • שִׂיחָה שילובים () במדד הבא, מכיוון שאיננו כוללים את המדד הנוכחי
    • בכל שלב, אנו בודקים אם cur_sum> max_sum_possible ומעדכנים אותו
  5. הדפיס את התוצאה

יישום אלגוריתם לפתרון House Robber 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';
}

תוכנית Java

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) כאשר אנו מייצרים כל המשך אפשרי המכיל אלמנטים שאינם עוקבים.

מורכבות חלל

עַל) בגלל מסגרות מחסנית רקורסיביות

גִישָׁה(תכנות דינמי)

דנו בגישה הקודמת שבכל אינדקס מסוים אנו יכולים

  • לכלול היסוד בסכום שלנו.
  • תכלול האלמנט.

בית שודד פתרון Leetcode

נניח ans [i, N] הוא הסכום המרבי שנוכל להשיג בטווח i ל N. תוצאה זו תהיה תלויה עוד יותר ב- ans [i + 2, N] ו- ans [i + 1, N]. אנו יכולים להתייחס לכל טווח כ- היו כאלה שכל מדינה תלויה עוד במדינות משנה. יתכן שעלינו לפתור רקורסיבית עבור כל מדינה מסוימת שוב ושוב כדי לפתור בעיות אחרות של מדינת האם. זה מבנה אופטימלי. אנו יכולים גם להסיק כי עבור מערך בגודל N, הסכום המרבי שניתן להשיג מכל האלמנטים 'n' הוא המקסימום של שתי התוצאות הללו:

  • תוצאה אופטימלית שהושגה עד (N - 1) אלמנטים וכולל את האלמנט ה- N
  • התוצאה הטובה ביותר שהושגה עד (N - 1) ולמעט אלמנט ה- N

אנחנו יכולים ליצור טבלה כזו שולחן [i] מאחסן את הסכום המרבי שניתן להשיג באמצעות מערך המשנה [0, i]. אבל יש שתי אפשרויות לכל אינדקס. לכן, עלינו לאחסן שתי תוצאות שונות למקרים: כאשר האלמנט נכלל וכאשר האלמנט אינו נכלל.

אַלגוֹרִיתְם

  1. אם המערך ריק, החזר 0
  2. אם למערך יש רק אלמנט אחד, החזיר את האלמנט הזה
  3. צור פונקציה robLinear () המחזיר את הסכום המרבי שניתן להשיג במערך ליניארי
  4. robLinear () עובד כדלקמן:
    1. יזם שני משתנים הכלולים וכללו 0, המאחסן את התוצאות המקסימליות המתקבלות על ידי הכללה והכללה של האלמנט הנוכחי בהתאמה
    2. בכל איטרציה הבאה, הכלול הופך להיות האלמנט הנוכחי + נשלל תוצאה של אלמנט קודם
    3. לא נכלל הופך למקסימום של כלול ו נשלל תוצאות האלמנט הקודם
  5. החזר את המקסימום של robLinear(1, N - 1) ולשדוד לינארית(2, N)

יישום אלגוריתם לפתרון House Robber 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';
}

תוכנית Java

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) אנו חוצים את המערך פעמיים. אז אנו מבצעים פעולות O (2N), שהיא ליניארית.

מורכבות חלל

O (1) רק שטח קבוע משמש למשתנים.