Λύση Μοναδικής Διαδρομής Leetcode  


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg ByteDance Facebook Goldman Sachs Google Μαθηματικά Microsoft μαντείο Qualtrics Salesforce Snapchat Uber VMware Εργαστήρια Walmart
αλγόριθμοι Παράταξη κωδικοποίησης Δυναμικός προγραμματισμός συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions

Το πρόβλημα Unique Paths Leetcode Solution δηλώνει ότι σας δίδονται δύο ακέραιοι αριθμοί που αντιπροσωπεύουν το μέγεθος ενός πλέγματος. Χρησιμοποιώντας το μέγεθος του πλέγμα, το μήκος και το πλάτος του πλέγματος. Πρέπει να βρούμε τον αριθμό των μοναδικών διαδρομών από την επάνω αριστερή γωνία του πλέγματος έως την κάτω δεξιά γωνία. Υπάρχει ένας άλλος περιορισμός στην κατεύθυνση της κίνησης, σε οποιαδήποτε στιγμή, μπορεί κανείς να κινηθεί μόνο προς τα κάτω ή προς τη δεξιά κατεύθυνση.

Παράδειγμα  

row: 2, column: 2
2

Επεξήγηση: Υπάρχουν μόνο δύο τρόποι για να ολοκληρώσετε την εργασία. Πρώτα είτε μετακινείτε προς τα δεξιά ή προς τα κάτω. Εάν μετακινήσατε δεξιά μπορείτε να μετακινηθείτε μόνο προς τα κάτω. Εάν είχατε μετακινηθεί προς τα κάτω, τότε μπορείτε να μετακινηθείτε μόνο προς την κάτω κατεύθυνση. Έτσι, μόνο 2 τρόποι είναι δυνατοί.

Λύση Μοναδικής Διαδρομής LeetcodeΚαρφώστε

row: 2, column: 3
3

Επεξήγηση: Υπάρχουν 6 τρόποι για να φτάσετε στον προορισμό. Σκεφτείτε εάν μετακινήσατε προς τα δεξιά, τότε το πρόβλημα έχει μειωθεί στο παραπάνω παράδειγμα και έχετε 2 τρόπους για να φτάσετε στην κάτω δεξιά γωνία. Εάν θα έχετε κάτω, τότε έχετε μόνο έναν τρόπο να φτάσετε στην κάτω δεξιά γωνία. Έτσι, ο συνολικός αριθμός τρόπων για να φτάσετε στο τέλος είναι 3.

Βλέπε επίσης
Ελέγξτε τον σχηματισμό συστοιχίας μέσω της λύσης συνένωσης Leetcode

Προσέγγιση Brute Force για μοναδικές διαδρομές Leetcode Solution  

Το πρόβλημα Unique Paths Leetcode Solution μπορεί να λυθεί αναδρομικά. Όπως κάναμε και στο δεύτερο παράδειγμα, όπου μειώσαμε το δεδομένο πρόβλημα σε 2 υποπροβλήματα. Το ίδιο είναι αυτό που θα κάνουμε σε αυτήν τη λύση. Μόλις μετακινηθούμε προς τα δεξιά, τότε το πρόβλημα μειώνεται σε υποπρόβλημα (σειρά, στήλη-1). Εάν είχαμε κινηθεί προς τα κάτω, το πρόβλημα μειώνεται σε (σειρά-1, στήλη). Μπορούμε εύκολα να κωδικοποιήσουμε αυτήν την αναδρομική λύση. Αλλά αυτό θα υπερβεί το χρονικό όριο, επειδή η λύση είναι εξαιρετικά αναποτελεσματική.

Κωδικός για Brute Force Προσέγγιση

Κωδικός 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 ^ max (m, n)), λόγω της εκθετικής πολυπλοκότητας του χρόνου λόγω της αναδρομικής λειτουργίας.

Διαστημική πολυπλοκότητα

O (μέγιστο (m, n), ο χώρος που χρησιμοποιείται από τη στοίβα μεταγλωττιστή. Αυτό εξαρτάται από το ύψος του αναδρομικού δέντρου.

Προσέγγιση δυναμικού προγραμματισμού  

Η προσέγγιση που έχει εξηγηθεί παραπάνω στην αναδρομική λύση μπορεί εύκολα να απομνημονευθεί. Δεδομένου ότι η αναδρομική συνάρτηση εξαρτάται από δύο μεταβλητές που είναι σειρά και στήλη. Έτσι δημιουργούμε 2D DP παράταξη και αποθηκεύστε το αποτέλεσμα κάθε κατάστασης. Αυτό θα βελτιώσει δραματικά την πολυπλοκότητα του χρόνου, διότι δεν επιλύουμε τα ίδια προβλήματα.

Βλέπε επίσης
Ελάχιστος χρόνος επίσκεψης σε όλα τα σημεία Λύση κωδικού

Κωδικός Δυναμικού Προγραμματισμού για Unique Paths Leetcode Solution

Κωδικός 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), ο απαιτούμενος χώρος είναι για τη δημιουργία πίνακα 2D DP. Η πολυπλοκότητα του διαστήματος είναι πολυώνυμη για την προσέγγιση DP.