01 Matrix LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook google microsoft ÜberBaxılıb 88

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

Bu 01 Matris LeetCode Həlli məsələsində verilmiş matrisin hər bir xanası üçün ən yaxın 0-ın məsafəsini tapmalıyıq. Matris yalnız 0 və 1-dən ibarətdir və hər hansı iki qonşu xananın məsafəsi 1-dir.

Nümunələr

Misal 1:

01 Matrix LeetCode HəlliPin

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Misal 2:

01 Matrix LeetCode HəlliPin

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Izahat

matris matını 0 indeksli hesab edin

  • məs.1: mat[1][1] istisna olmaqla, bütün xanalarda 0 var və buna görə də bu hüceyrələrdən ən yaxın məsafəyə qədər 0 0-dır. Mat[1][1]-dən 0-a qədər olan ən yaxın məsafə hər hansı qonşu xanadır, yəni 1 vahiddir.
  • məs. 2. 1 dəyəri və bitişik xana dəyəri 0 olan xanalar məsafə 1-ə malikdir, xana mat[2][1] ən yaxın 2-dan 0 vahiddir

Yanaşma

Bu problem kobud gücdən istifadə etməklə həll edilə bilər, lakin bu, TLE-yə səbəb olacaqdır.

Aşağıda müzakirə olunan yanaşma 1 vahid kimi kənar çəkilərə malik və ya dəyişdirilmiş Dijkstra alqoritmini istifadə edir. BFS. Məsafənin hesablandığı yerdən asılı olaraq BFS üçün 2 intuisiya var.

  1. Biz bütün xanaları keçə bilərik, əgər xana dəyəri 0 olarsa, 0-ı saxlayırıq, əks halda bu xanaya BFS tətbiq edirik. Bu yanaşma üçün BFS funksiyasını yuvalanmış döngələr daxilində çağırmalıyıq və buna görə də vaxt mürəkkəbliyi yüksək olacaqdır.
  2. Biz 0 dəyəri olan bütün xanaların koordinatlarını saxlamaq üçün növbədən istifadə edirik və ən yaxın 0-ı hesablamaq üçün Dijkstra salqoritmindən istifadə edirik. İlkin olaraq, 0 dəyəri olan hər bir xana üçün məsafə 0, sonsuzluq və ya INT_MAX-dır. Ön elementi açın və qonşularını keçin, əgər yeni hesablanmış məsafə daha kiçikdirsə, onun koordinatlarını növbəyə itələyirik və məsafəni yeniləyirik.

Aydındır ki, ikinci yanaşma bizi BFS-ni iç-içə döngələr içərisində işləməkdən xilas edəcək və biz ondan istifadə edərək daha sürətli alqoritmə nail ola bilərik.

Kodu

01 Matrix LeetCode Həlli üçün C++ Kodu

#define vvi vector<vector<int>>
#define iPair pair<int,int>
class Solution {
    int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    void bfs(queue<iPair> &q, vvi &res, int r, int c) {
         while(!q.empty()) {
            iPair curr = q.front();
            q.pop();
            int x = curr.first, y = curr.second;
            for(auto d:dir) {
                int newX = x+d[0], newY = y+d[1];
                
                if(newX >= 0 && newX < r && newY>=0 && newY < c) {
                    if(res[newX][newY] > res[x][y] + 1) {
                        res[newX][newY] = res[x][y] + 1;
                        q.push({newX,newY});
                    }
                }
            }
        }
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int r = mat.size(), c = mat[0].size();
        vvi res(r, vector<int> (c,INT_MAX));
        queue<iPair> q;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(!mat[i][j]) {
                    res[i][j] = 0;
                    q.push({i,j});
                }
            }
        }

        bfs(q, res, r, c);       
        return res;
    }
};

01 Matrix LeetCode Həlli üçün Java Kodu

class Solution {
    public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public void bfs(Queue<int[]> q, int[][] matrix, int r, int c) {
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            for (int[] d : dirs) {
                int x = cell[0] + d[0];
                int y = cell[1] + d[1];
                if (x < 0 || x >= r || y < 0 || y >= c || 
                    matrix[x][y] <= matrix[cell[0]][cell[1]] + 1) continue;
                q.add(new int[] {x, y});
                matrix[x][y] = matrix[cell[0]][cell[1]] + 1;
            }
        }
    }
    
    public int[][] updateMatrix(int[][] matrix) {
        int r = matrix.length;
        int c = matrix[0].length;
        
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == 0) {
                    q.offer(new int[] {i, j});
                }
                else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        bfs(q, matrix, r, c);
        
        
        
        return matrix;
    }
}

01 Matrix LeetCode Həlli üçün Mürəkkəblik Təhlili

  • Zamanın mürəkkəbliyi: O(r*c)Yeni xanalar növbəyə yalnız onların cari məsafəsi hesablanmış məsafədən böyük olduqda əlavə edildiyi üçün xanaların bir neçə dəfə əlavə olunma ehtimalı yoxdur.
  • Kosmik mürəkkəblik: O(r*c)Əlavə O(r*c) növbəni saxlamaq üçün yer tələb olunur.
Crack Sistemi Dizayn Müsahibələri
Translate »