Qapalı Adaların sayı Leetcode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Kupanq Facebook google microsoft Kahin ÜberBaxılıb 32

Problem bəyanat :

Qapalı Adalar Leetcode Həllinin sayı – 2-lardan (torpaq) və 0-lərdən (su) ibarət 1D şəbəkə verilmişdir. An ada 4 və a-dan ibarət maksimal 0 istiqamətli bağlı qrupdur qapalı ada bir adadır tamamilə (hamısı sol, yuxarı, sağ, aşağı) 1-lərlə əhatə olunmuşdur.

nömrəsini qaytarın qapalı adalar.

Misal:

Məsələn 1 

Qapalı Adaların sayı Leetcode HəllPin

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are surrounded by water (group of 1s).

 

Məsələn 2

 

Qapalı Adaların sayı Leetcode HəllPin

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

Məhdudiyyətlər:

Qapalı Adaların sayı Leetcode Həll

Yanaşma:

Fikir

  • Bu problemin uzantısıdır Adaların sayı LeetCode Həll.
  • Beləliklə, necə tapacağımızı bilirik  adaların sayı , lakin bu problem üçün tapmaq lazımdır qapalı adaların sayıqapalı ada vasitə su ilə əhatə olunmuş (1) .
  • İndi diqqət yetirin kənarları, baxsaq görərik ki, kənarlardakı torpaq (0-lar) ola bilər heç vaxt qapalı bir adanın parçası olmayın, qapalı ada tərifinə görə, torpaq ( 0 ) hər dörd istiqamətdə su ( 1 ) ilə bağlanmalıdır.
  • Şəbəkənin kənarları var birinci sətir (r = 0), Son sətir (r = n-1), Birinci Sütun (c = 0), Son sütun (c = m-1).

Alqoritm:

  • Şəbəkəni keçin və olub olmadığını yoxlayın şəbəkənin kənarları sıfırdır.
  • Əgər şəbəkə[i][j] kənarlarda sıfırdır, sonra DFS keçidi edin və onları kimi qeyd edin su, kənarlarında quru kimi adalar bağlana bilməz.
  • Kenarlarda DFS keçidi vasitəsilə, bütün komponentləri o kənara yapışdırıldıqda suya çevriləcək.
  • Şəbəkənin hərəkətindən sonra a yenidən keçid və DFS-ə zəng edin qalan torpaq (0).
  • İkinci keçid ilə eyni işləyəcək adaların sayıetibarlı qapalı adaları qaytarır.

Qapalı Adaların Sayı üçün kod Leetcode Həlli

Java Kodu

class Solution {
    int DIR[][]={{0,1},{1,0},{-1,0},{0,-1}};
    public int closedIsland(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 || j==0 ||i ==n-1 || j==m-1){
                    dfs(grid,i,j);
                }
            }
        }
            int ans=0;
             for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
               if(grid[i][j]==0){
                    dfs(grid,i,j);
                   ans++;
               }
            }
        }
            return ans;
    }
    
    public void dfs(int[][]grid,int r,int c){
        
         if(r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]==1)return ;
        grid[r][c]=1;
        
        for(int[]d:DIR){
            int nr= r+d[0];
            int nc=c+d[1];
           
            dfs(grid,nr,nc);
        }
    }
}

C++ kodu

class Solution {
public:
    int DIR[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
    int closedIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 || j==0 ||i ==n-1 || j==m-1){
                    dfs(grid,i,j);
                }
            }
        }
            int ans=0;
             for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
               if(grid[i][j]==0){
                    dfs(grid,i,j);
                   ans++;
               }
            }
        }
            return ans;
    }
    
    void dfs(vector<vector<int>>& grid,int r,int c){
        
         if(r<0||c<0||r>=grid.size()||c>=grid[0].size()||grid[r][c]==1)return ;
        grid[r][c]=1;
        for(auto & d:DIR){
            int nr= r+d[0];
            int nc=c+d[1];
            dfs(grid,nr,nc);
        }
    }
};

Qapalı Adaların Sayı üçün Mürəkkəblik Təhlili Leetcode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n * m), çünki biz şəbəkənin hər bir elementini həmişə iki dəfə keçirik. Burada n və m-dir sətirlərin sayı və sütunların sayı müvafiq.

Kosmik Mürəkkəblik 

O (1), biz heç bir əlavə yerdən istifadə etməmişik.

Translate »