Μοναδικά μονοπάτια II  


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα VMware
Δυναμικός προγραμματισμός Μήτρα

Ας υποθέσουμε ότι ένας άντρας στέκεται στο πρώτο κελί ή στην επάνω αριστερή γωνία του «Α × β» μήτρα. Ένας άντρας μπορεί να κινηθεί μόνο πάνω ή κάτω. Αυτό το άτομο θέλει να φτάσει στον προορισμό του και αυτός ο προορισμός είναι το τελευταίο κελί του μήτρα ή κάτω δεξιά γωνία.

Και αν υπάρχουν κάποια εμπόδια σε αυτό, πόσα μοναδικά μονοπάτια μπορούν να προσδιοριστούν από το άτομο. Βοηθήστε τον να φτάσει στον προορισμό, γνωρίζοντας το No of Unique Paths.

Ένα εμπόδιο θεωρείται ως 1 και το διάστημα επισημαίνεται ως 0 στη μήτρα.

Παράδειγμα ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε

εισόδου:

[
[0,0,0],
[0,1,0],
[0,0,0]
]

Παραγωγή:

2

Επεξήγηση:

Επειδή υπάρχει μόνο ένα εμπόδιο στο μέσο ολόκληρου του πίνακα που επιτρέπει μόνο δύο μοναδικές διαδρομές:

  1. Κάτω → Κάτω → Δεξιά → Δεξιά
  2. Δεξιά → Δεξιά → Κάτω → Κάτω

Μοναδικά μονοπάτια IIΚαρφώστε

Στην παραπάνω εικόνα, το μπλε βέλος δείχνει τη διαδρομή 1 και το κόκκινο βέλος δείχνει τη διαδρομή 2.

Αλγόριθμος ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε

  1. Ελέγξτε εάν το πρώτο κελί που είναι πίνακας [0] [0] περιέχει 1 και, στη συνέχεια, επιστρέψτε τις μοναδικές διαδρομές ως 0, καθώς δεν μπορεί να προχωρήσει μπροστά από αυτό.
  2. Εάν ο πίνακας [0] [0] δεν περιέχει την τιμή 1, αρχικοποιήστε την τιμή του πίνακα [0] [0] = 1.
  3. Τώρα, επαναλάβετε την πρώτη σειρά του πίνακα και εάν αυτό το κελί περιέχει 1, αυτό σημαίνει ότι το τρέχον κελί έχει ένα εμπόδιο σε αυτό και ορίζει την τιμή ενός κελιού σε 0. Διαφορετικά ορίστε την τιμή αυτού του κελιού από το προηγούμενο κελί που είναι πίνακας [i] [j] = πίνακας [i] [j-1].
  4. Τώρα, επαναλάβετε την πρώτη στήλη του πίνακα και αν αυτό το κελί περιέχει 1, αυτό σημαίνει ότι το τρέχον κελί έχει ένα εμπόδιο σε αυτό και ορίζει την τιμή του κελιού στο 0. Διαφορετικά ορίστε την τιμή αυτού του κελιού από το προηγούμενο κελί που είναι πίνακας [i] [j] = πίνακας [i] [j-1].
  5. Τώρα, επαναλάβετε ολόκληρο τον πίνακα ξεκινώντας από τον πίνακα κελιών [1] [1].
  6. Ελέγξτε εάν το κελί δεν περιέχει κανένα εμπόδιο, τότε κάντε arrayi, j] = array [i-1, j] + array [i, j-1].
  7. Εάν ένα κελί περιέχει ένα εμπόδιο, ορίστε την τιμή του κελιού σε 0 για να βεβαιωθείτε ότι δεν επαναλαμβάνεται σε καμία άλλη διαδρομή.
Βλέπε επίσης
Αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

εξήγηση ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε

Επομένως, η κύρια ιδέα μας για την επίλυση αυτής της ερώτησης είναι εάν ένα κελί δεν έχει τις τιμές 0 σε αυτό σημαίνει ότι έχουμε τον αριθμό των τρόπων για να φτάσουμε στο κελί προορισμού μας είναι το άθροισμα πολλών τρόπων για να φτάσουμε στο κελί πάνω από αυτό κελί και άθροισμα του αριθμού των τρόπων επίτευξης του κελιού αριστερά αυτού του κελιού.

Έτσι, εφαρμόσαμε μερικές από τις λειτουργίες που θα μας βοηθήσουν στην επίλυση του προβλήματός μας. Δηλώσαμε μια συνάρτηση getVal, η getVal παίρνει κάποια ορίσματα εκτελεί ορισμένες λειτουργίες και επιστρέφει κάποια τιμή, που θα λύσει το ακόλουθο πρόβλημα:

  1. Εάν σε μια πρώτη σειρά, ένα κελί περιέχει ένα εμπόδιο θέτει την τιμή σε 0 αλλιώς θα ορίσει την τιμή αυτού του κελιού όπως εκείνη του προηγούμενου κελιού που είναι πίνακας [i] [j] = πίνακας [i] [j-1 ].
  2. Εάν σε μια πρώτη σειρά, ένα κελί περιέχει ένα εμπόδιο ορίζει την τιμή σε 0 αλλιώς θα ορίσει την τιμή αυτού του κελιού όπως εκείνη του προηγούμενου κελιού που είναι πίνακας [i] [j] = πίνακας [i-1] [j ].

Παράδειγμα

Ας πάρουμε λοιπόν ένα παράδειγμα ως Array = {{0,0,0}, {0,1,0}, {0,0,0}};

Ένας πίνακας μεταφέρεται στο findUniquePath

Σειρά = {{0,0,0}, {0,1,0}, {0,0,0}};

Επομένως, το πρώτο κελί του που είναι πίνακας [0] [0] δεν είναι ίσο με 1.

Ορίστε λοιπόν, πίνακα [0] [0] = 1;

Επανάληψη στήλης,

I = 1

αν ο πίνακας [1] [0] == 0 και ο πίνακας [0] [0] = 1 είναι αληθής

έτσι πίνακας [1] [0] = 1;

i = 2;

αν ο πίνακας [2] [0] == 0 και ο πίνακας [1] [0] = 1 είναι αληθής

έτσι πίνακας [2] [0] = 1;

Τώρα επαναλαμβάνεται σε σειρά,

I = 1

αν ο πίνακας [0] [1] == 0 και ο πίνακας [0] [0] = 1 είναι αληθής

έτσι πίνακας [0] [1] = 1;

i = 2;

αν ο πίνακας [0] [2] == 0 και ο πίνακας [0] [1] = 1 είναι αληθής

έτσι πίνακας [0] [2] = 1;

Τώρα ξεκινά από τον πίνακα [1] [1]

Βλέπε επίσης
K-th Μικρότερο Στοιχείο σε Ταξινόμηση Πίνακας

i = 1, j = 1

αν ο πίνακας [1] [1] == 0 είναι ψευδής

έτσι πίνακας [1] [1] = 0

i = 1, j = 2

αν ο πίνακας [1] [2] == 0 είναι αληθής

πίνακας [i] [j] = πίνακας [i - 1] [j] + πίνακας [i] [j - 1];

so array[1][2]=array[0][2]+array[0][1];

array[1][2]=1+1=2;

i = 2, j = 1

αν ο πίνακας [2] [1] == 0 είναι αληθής

έτσι πίνακας [2] [1] = 0

i = 2, j = 2

αν ο πίνακας [2] [2] == 0 είναι αληθής

πίνακας [i] [j] = πίνακας [i - 1] [j] + πίνακας [i] [j - 1];

so array[2][2]=array[1][2]+array[2][1];

πίνακας [2] [2] = 2 + 0;

πίνακας [2] [2] = 2

Δηλαδή πρόκειται να επιστρέψουμε τον πίνακα τιμών [2] [2] που σημαίνει 2 είναι η απαιτούμενη έξοδος μας.

Εκτέλεση ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε

Πρόγραμμα C ++ για Unique Paths II

#include<iostream>
using namespace std;
int getVal(int x, int y)
{
    if(x==0 && y==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int findUniquePath(int arr[3][3])
{
    if (arr[0][0] == 1)
    {
        return 0;
    }
    arr[0][0] = 1;
    for (int i = 1; i < 3; i++)
    {
        arr[i][0] = getVal(arr[i][0],arr[i-1][0]);
    }
    for (int i = 1; i < 3; i++)
    {
        arr[0][i] = getVal(arr[0][i],arr[0][i-1]);
    }
    for (int i = 1; i < 3; i++)
    {
        for (int j = 1; j < 3; j++)
        {
            if (arr[i][j] == 0)
            {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
            else
            {
                arr[i][j] = 0;
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputValue[3][3]= {{0,0,0},
                           {0,1,0},
                           {0,0,0}};
                           
    findUniquePath(inputValue);
    cout<<findUniquePath(inputValue);;
    return 0;
}
2

Πρόγραμμα Java για Unique Paths II

class uniquePath2 {
  public static int getVal(int x, int y) {
    if (x == 0 && y == 1) {
      return 1;
    } else {
      return 0;
    }
  }
  public static int findUniquePath(int array[][]) {
    if (array[0][0] == 1) {
      return 0;
    }
    array[0][0] = 1;
    for (int i = 1; i<array.length; i++) {
      array[i][0] = getVal(array[i][0], array[i - 1][0]);
    }
    for (int i = 1; i<array[0].length; i++) {
      array[0][i] = getVal(array[0][i], array[0][i - 1]);
    }
    for (int i = 1; i<array.length; i++) {
      for (int j = 1; j<array[i].length; j++) {
        if (array[i][j] == 0) {
          array[i][j] = array[i - 1][j] + array[i][j - 1];
        } else {
          array[i][j] = 0;
        }
      }
    }

    int row = array.length;
    int col = array[0].length;
    return array[row - 1][col - 1];
  }
  public static void main(String[] args) {
    int inputValue[][] = {
      {
        0, 0, 0
      }, {
        0, 1, 0
      }, {
        0, 0, 0
      }
    };
    System.out.println(findUniquePath(inputValue));
  }
}
2

Ανάλυση πολυπλοκότητας για μοναδικές διαδρομές II ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε ΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστεΚαρφώστε

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

O (a × b) όπου a και b είναι ο αριθμός των γραμμών και στηλών στη μήτρα που μας έχει δοθεί καθώς κάθε κελί υποβάλλεται σε επεξεργασία μόνο μία φορά.

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

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

Ο (1) καθώς δεν χρησιμοποιείται επιπλέον χώρος αφού χρησιμοποιούμε δυναμικό προγραμματισμό.

Αναφορά