Unikal Yollar II Leetcode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Unikal Yollar II LeetCode Həlli – “Unique Paths II” verildiyini bildirir mxn robotun şəbəkənin yuxarı sol küncündən başladığı tor. Cəmi tapmaq lazımdır yolların sayı şəbəkənin aşağı sağ küncünə çatmaq üçün.

Maneə olan hüceyrədə 1 while, pulsuz hüceyrə üçün 0 var.

Misal:

Input:  obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation:

• Şəbəkənin ortasında bir maneə var.
• Matrisin yuxarı sol küncündən aşağı sağ küncünə çatmaq üçün tam olaraq 2 unikal yol mövcuddur.
  • Sağ, Sağ, Aşağı, Aşağı.
  • Aşağı, Aşağı, Sağ, Sağ.

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1

Explanation:

• Tam olaraq 1 unikal yol var.
  • Aşağı, sağ.
• Beləliklə, 1 cavabımızdır.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir dinamik proqramlaşdırma.
2. dp[i][j] = bu xanada bitən unikal yolların sayı olsun.
3. Cari xanada maneə varsa, dp[i][j] = 0.
4. Cari xana sərbəst xanadırsa:
   1. Beləliklə, yuxarıdakı hüceyrədən cari hüceyrəyə çata bilərik dp[i][j] += dp[i-1][j], üst xananın mövcud olması şərti ilə.
   2. Beləliklə, sol xanadan cari xanaya çata bilərik dp[i][j] += dp[i][j-1], sol xananın mövcud olması şərti ilə.
5. Nəhayət, cavabımız dp[n-1][m-1]-dir.

Kodu

Unikal Yollar II Leetcode C++ Həlli:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(),m = obstacleGrid.back().size();
        vector<vector<int>> dp(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 and j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = 1;
                    }
                }
                else if(i==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i][j-1];
                    }
                }
                else if(j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                else{
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[n-1][m-1];
    }
};

Unikal Yollar II Leetcode Java Həlli:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 && j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = 1;
                    }
                }
                else if(i==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i][j-1];
                    }
                }
                else if(j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                else{
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[n-1][m-1];
    }
}

Unique Paths II Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N * M) burada N = sətirlərin sayı və M = sütunların sayı.

Bütün giriş matrisini ən azı bir dəfə keçdiyimiz üçün Zaman Mürəkkəbliyi O(N*M) təşkil edir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O(N*M). Birinə ehtiyacımız var dinamik proqramlaşdırma bütün aralıq dəyərləri saxlamaq üçün N*M ölçülü matrisa.

Referans: https://en.wikipedia.org/wiki/Dynamic_programming