פתרון Leetcode לנתיבים ייחודיים  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג Byte פייסבוק גולדמן זאקס Google עבודות מתמטיקה מיקרוסופט אורקל Qualtrics Salesforce Snapchat סופר VMware מעבדות וולמארט
אלגוריתמים מערך קידוד תכנות דינמי ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions

הבעיה Unique Paths Leetcode Solution קובעת שאתה מקבל שני מספרים שלמים המייצגים את גודל הרשת. באמצעות גודל ה - רשת, אורך ורוחב הרשת. עלינו למצוא את מספר הנתיבים הייחודיים מהפינה השמאלית העליונה של הרשת ועד הפינה הימנית התחתונה. יש מגבלה זו על כיוון התנועה, בכל נקודת זמן, אפשר לנוע רק בכיוון למטה או בכיוון הנכון.

דוגמה  

row: 2, column: 2
2

הסבר: יש רק שתי דרכים אפשריות לביצוע המשימה. ראשית או שתעבור ימינה או מטה. אם עברת ימינה תוכל לזוז רק למטה. אם היית זז למטה, אז אתה יכול לנוע רק בכיוון למטה. אז, רק שתי דרכים אפשריות.

פתרון Leetcode לנתיבים ייחודייםאורן

row: 2, column: 3
3

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

ראה גם
בדוק גיבוש מערך באמצעות פיתרון ליקוד לשרשור

גישת כוח הברוט לפתרון Leetcode לנתיבים ייחודיים  

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

קוד לגישת כוח הברוט

קוד C ++

#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {
    if(n==1 || m==1)return 1;
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

קוד Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

ניתוח מורכבות

מורכבות זמן

O (2 ^ מקסימום (m, n)), בגלל מורכבות הזמן האקספוננציאלית בגלל תפקוד רקורסיבי.

מורכבות בחלל

O (מקסימום (m, n), את החלל המשמש את ערימת המהדר. זה תלוי בגובה העץ הרקורסיבי.

גישת תכנות דינמית  

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

ראה גם
זמן מינימלי לביקור בכל הנקודות פתרון Leetcode

קוד תכנות דינמי לפתרונות ייחודיים של Leetcode

קוד C ++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
    if(m == 1 || n == 1) return 1;
    if(dp[m][n] != -1)
        return dp[m][n];
    return dp[m][n] = uniquePathsUtil(m-1, n) + uniquePathsUtil(m, n-1);
}

int uniquePaths(int m, int n) {
    dp.clear();
    dp.assign(m+1, vector<int>(n+1, -1));
    return uniquePathsUtil(m, n);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

קוד Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    private static int uniquePathsUtil(int m, int n, int[][] dp) {
        if(m == 1 || n == 1) return 1;
        if(dp[m][n] != 0)
            return dp[m][n];
        return dp[m][n] = uniquePathsUtil(m-1, n, dp) + uniquePathsUtil(m, n-1, dp);
    }

    private static int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        return uniquePathsUtil(m, n, dp);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

ניתוח מורכבות

מורכבות זמן

O (N * M), כאשר N, M משמשים לייצוג מספר השורות והעמודות ברשת. מכיוון שיש סך של מצבי N * M, מורכבות הזמן היא גם O (N * M).

מורכבות בחלל

O (N * M), השטח הנדרש הוא ליצירת טבלת DP דו-ממדית. מורכבות החלל היא פולינומית לגישת ה DP.