Λύση Leetcode Pascal's Triangle II  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Microsoft
αλγόριθμοι Παράταξη κωδικοποίησης Δυναμικός προγραμματισμός συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions μαθηματικά

Δήλωση προβλήματος  

Σε αυτό το πρόβλημα μας δόθηκε Row index (i) του Pascal Triangle. Πρέπει να δημιουργήσουμε έναν γραμμικό πίνακα που περιέχει τις τιμές της σειράς ith και να τον επιστρέψουμε. Ο δείκτης σειράς ξεκινά από το 0.
Γνωρίζουμε ότι το τρίγωνο του Pascal είναι ένα τρίγωνο όπου κάθε αριθμός είναι το άθροισμα των δύο αριθμών ακριβώς πάνω από αυτό.

Λύση Leetcode Pascal's Triangle IIΚαρφώστε

Παράδειγμα

rowIndex = 3
[1,3,3,1]
rowIndex = 0
[1]

Όπως γνωρίζουμε ότι κάθε τιμή στο τρίγωνο του pascal είναι ένας διωνυμικός συντελεστής (nCr) όπου το n είναι η σειρά και το r είναι ο δείκτης στήλης αυτής της τιμής.

Έχουμε συζητήσει παρόμοιο πρόβλημα όπου πρέπει να επιστρέψουμε όλες τις σειρές από το ευρετήριο γραμμών 0 στο δεδομένο ευρετήριο σειρών του τριγώνου του pascal εδώ - Κωδικός πρόσβασης τριγώνου Pascal

Αλλά σε αυτό το πρόβλημα πρέπει να επιστρέψουμε μόνο μία γραμμή της οποίας δίνεται το ευρετήριο.
Εδώ θα συζητήσουμε τρεις προσεγγίσεις για την επίλυση αυτού του προβλήματος:

Βλέπε επίσης
Βρείτε τη λύση Leetcode Town Judge

Προσέγγιση 1 (Επανάληψη Brute Force)  

Γνωρίζουμε ότι κάθε αριθμός σε αυτό το τρίγωνο είναι το άθροισμα των δύο αριθμών ακριβώς πάνω από αυτόν. δηλ
Num (σειρά, στήλη) = Αριθ. (Σειρά-1, στήλη) + Αριθ. (Σειρά-1, στήλη-1).
Έτσι μπορούμε να καλέσουμε επανειλημμένα τη συνάρτηση Num (rowIndex, j) για κάθε ευρετήριο στηλών αυτής της σειράς και να επιστρέψουμε τη διαμορφωμένη λίστα.

Όπως μπορούμε να δούμε έχουμε διαμορφώσει αναδρομική προσέγγιση για την εύρεση του Num (i, j). Τώρα υπάρχουν μερικές βασικές περιπτώσεις για εκείνες που είναι:

  • Η τιμή στην πρώτη σειρά θα είναι 1. Έτσι για τη σειρά = 0, Αριθμός (σειρά,…) = 0.
  • Η τιμή στην πρώτη στήλη θα είναι 1. Έτσι για col = 0, Num (…, col) = 0.
  • Η τελευταία τιμή κάθε σειράς θα είναι ίση με 1. Έτσι για col = σειρά = k, Num (k, k) = 0.

Εφαρμογή για τη λύση Leetcode του Triangle II του Pascal

Πρόγραμμα C ++

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

int nCr(int n,int r)
{
    if(n==0 || r==0 || r==n)
        return 1;

    return nCr(n-1,r-1)+ nCr(n-1,r);
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Πρόγραμμα Java

import java.util.*;

class Rextester{
    
    static int nCr(int n,int r)
    {
        if(n==0 || r==0 || r==n)
            return 1;

        return nCr(n-1,r-1)+ nCr(n-1,r);
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Ανάλυση πολυπλοκότητας για τη λύση Triet II Leetcode του Pascal

Χρόνος πολυπλοκότητας

O (2 ^ k): όπου k είναι ο δεδομένος Row Index.
Ζητούμε την αναδρομή για το Num (i, j) ως Num (i-1, j) + Num (i-1, j-1). Ως εκ τούτου, ο χρόνος για την εύρεση Num (n, r) θα είναι nCr.
Καλούμε αυτήν την αναδρομική συνάρτηση για όλους τους δείκτες στηλών της δεδομένης σειράς (k) .ie
kC0 + kC1 + kC2 +…. + kCk = 2 ^ k.
Ως εκ τούτου, η συνολική πολυπλοκότητα του χρόνου θα είναι O (2 ^ k).

Βλέπε επίσης
Αριθμός Λύσης Leetcode Good Pairs

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

Εντάξει): Χρειαζόμαστε χώρο O (k) για να αποθηκεύσουμε όλες τις τιμές μιας δεδομένης σειράς σε μια λίστα. Επίσης στη χειρότερη περίπτωση η αναδρομή μας θα χρειαστεί χώρο στοίβας O (k) για αναδρομική κλήση. Ως εκ τούτου O (k) + O (k) = ~ O (k).

Προσέγγιση 2 (Δυναμικός προγραμματισμός 

Στην παραπάνω αναδρομή μπορούμε να δούμε ότι καλούμε τη συνάρτηση Num (i, j) για την ίδια (i, j) επανειλημμένα.

Αυτό που μπορούμε λοιπόν να κάνουμε είναι να μπορούμε να απομνημονεύσουμε το ans για κάθε (i, j) έτσι ώστε όποτε χρειάζεται να καλέσουμε ξανά αυτήν τη λειτουργία, επιστρέφουμε την προσωρινή μνήμη απ 'ευθείας από τη μνήμη χωρίς να υπολογίσουμε ξανά. Έτσι εξοικονομείτε πολύ χρόνο.
Για τη δυναμική αποθήκευση των απαντήσεων που μπορούμε να χρησιμοποιήσουμε χάρτης κατακερματισμού όπου το κλειδί θα είναι ο συνδυασμός ευρετηρίου γραμμών και ευρετηρίου στηλών.

Ένα ακόμη πράγμα που μπορούμε να δούμε εδώ είναι ότι χρειαζόμαστε μόνο τιμές προηγούμενων σειρών για την εύρεση των τιμών της τρέχουσας γραμμής. Επομένως, μπορούμε να αποθηκεύσουμε μόνο μία τιμή γραμμής τη φορά και να την χρησιμοποιήσουμε για να βρούμε τις τιμές της επόμενης σειράς. Ως εκ τούτου μπορούμε να μειώσουμε την πολυπλοκότητα του χώρου σε O (k) εδώ.

Αλγόριθμος βελτιστοποιημένος στο χώρο:
1. Δημιουργήστε δύο πίνακες για την προηγούμενη και την τρέχουσα σειρά αντίστοιχα.
2. Αρχικοποίηση prev σειρά ως {1}.
3. Εκτελέστε έναν βρόχο για ith σειρά από i = 1 έως i =rowIndex. Δημιουργήστε νέες τιμές γραμμής από την προηγούμενη σειρά και αποθηκεύστε τις curr πίνακας.
4. Τώρα ενημερώστε prev σειρά με εκχώρηση γάιδαρος σειρά προς prev σειρά και επαναλάβετε την ίδια διαδικασία σε αυτόν τον βρόχο.
5. Επιστρέψτε την τελευταία σειρά που είναι αποθηκευμένη στο prev πίνακας.

Εφαρμογή για τη λύση Leetcode του Triangle II του Pascal

Πρόγραμμα C ++ χρησιμοποιώντας απομνημόνευση

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

unordered_map<string,int> cache;

int nCr(int n,int r)
{
    string key= to_string(n)+to_string(r);
    if(cache.count(key)) return cache[key]; 

    if(n==0 || r==0 || r==n)
        return 1;

    return ( cache[key]= nCr(n-1,r-1)+ nCr(n-1,r) );
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}

Πρόγραμμα C ++ (DP βελτιστοποιημένο για το διάστημα)

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

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Πρόγραμμα Java χρησιμοποιώντας απομνημόνευση

import java.util.*;

class Rextester{
    
    static Map<String,Integer> cache=new HashMap<String,Integer>();
    
    static int nCr(int n,int r)
    {
        String key= "" + n + r;
        if(cache.containsKey(key)) return cache.get(key); 
        
        if(n==0 || r==0 || r==n)
            return 1;
        
        int ans= nCr(n-1,r-1)+ nCr(n-1,r);
        cache.put(key,ans);
        return ans;
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}

Πρόγραμμα Java (Space βελτιστοποιημένο DP)

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

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Ανάλυση πολυπλοκότητας για τη λύση Triet II Leetcode του Pascal

Χρόνος πολυπλοκότητας

O (k ^ 2):  Η απομνημόνευση θα διασφαλίσει ότι ένα συγκεκριμένο στοιχείο υπολογίζεται μόνο μία φορά. Και υποθέτοντας ότι χρειάζεται σταθερός χρόνος για να πάρει ans από hash map, χρειάζεται σταθερός χρόνος για τον υπολογισμό κάθε τιμής του τριγώνου του pascal.
Τώρα καταλήγουμε να υπολογίζουμε τις τιμές 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 που είναι = ~ O (k ^ 2).

Βλέπε επίσης
Συγχώνευση ταξινομημένης σειράς Leetcode Solution

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

1. Η απλή απομνημόνευση θα κρατούσε όλα τα στοιχεία 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 στη χειρότερη περίπτωση. Αυτό θα απαιτούσε O (k ^ 2) χώρος.
2. Σε χώρο βελτιστοποιημένο DP χρειαζόμαστε Εντάξει) χώρο μόνο για την αποθήκευση της τελευταίας γραμμής που δημιουργήθηκε.

Προσέγγιση 3 (Μαθηματικά)  

Όπως γνωρίζουμε ότι κάθε τιμή στο τρίγωνο του pascal είναι ένας διωνυμικός συντελεστής (nCr). Και μπορούμε να γράψουμε το nCr ως:
Λύση Leetcode Pascal's Triangle II

Τώρα αν παρατηρήσουμε, οι διαδοχικοί διωνυμικοί συντελεστές nC (r-1) και nCr διαφέρουν ανάλογα με τον παράγοντα:
Λύση Leetcode Pascal's Triangle II

Έτσι, μπορούμε να αντλήσουμε τον επόμενο όρο στη σειρά στο τρίγωνο του Pascal, από έναν προηγούμενο όρο.

Αλγόριθμος:

  1. Αρχικοποιήστε τον πρώτο όρο της σειράς ως 1.
  2. Εκτελέστε έναν βρόχο για στήλη με ευρετήριο και υπολογίστε τον επόμενο όρο (όρος (i)) ως, όρος (i) = όρος (i-1) * (n-i + 1) / i.
  3. Επιστρέψτε τις υπολογισμένες τιμές ως λίστα.

Εφαρμογή για τη λύση Leetcode του Triangle II του Pascal

Πρόγραμμα C ++

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

vector<int> getRow(int rowIndex) 
{
    int n=rowIndex;
   vector<int> res;
   res.push_back(1);

    for(int i=1;i<=n;i++)
    {
       int x= (int) ( ((long long)res.back()*(n-i+1) ) /i);
       res.push_back(x);
    }

    return res;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Πρόγραμμα Java

import java.util.*;

class Rextester{

    public static List<Integer> getRow(int rowIndex) 
    {
       int n=rowIndex;
       List<Integer> res=new ArrayList<Integer>();
       res.add(1);
        
        for(int i=1;i<=n;i++)
        {
           int x= (int) ( ((long)res.get(res.size()-1)*(n-i+1) ) /i);
           res.add(x);
        }
        
        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Ανάλυση πολυπλοκότητας για τη λύση Triet II Leetcode του Pascal

Χρόνος πολυπλοκότητας

Εντάξει): Κάθε τιμή της γραμμής υπολογίζεται σε σταθερό χρόνο.

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

Εντάξει): Δεν απαιτείται επιπλέον χώρος εκτός από το κράτημα της εξόδου.