Fərqli adaların sayı Leetcode həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg ByteDance eBay Facebook google microsoft Kahin Snapchat Über
Genişlik İlk Axtarış Dərinlik İlk Axtarış Sükut HashMap tiktok Birlik tapınBaxılıb 14

Problem bəyanat

The Fərqli Adaların sayı LeetCode Həll - “Fərqli adaların sayı” a verilmişdir nxm ikili matris. Ada bir qrupdur 1's (torpağı təmsil edən) bağlıdır 4-istiqamətli (üfüqi və ya şaquli).

Bir ada digəri ilə eyni hesab olunur, o zaman və yalnız bir ada digərinə bərabər tutula bilərsə (və fırlanmazsa və ya əks olunmazsa).

Biz ümumi sayını qaytarmalıyıq fərqli adalar.

Misal:

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

Explanation:

Fərqli adaların sayı Leetcode həlliPin

  • Daha yaxşı başa düşmək üçün yuxarıdakı diaqramı yoxlayın.
  • Nəzərə alın ki, biz adanın istiqamətini döndərə və ya əks etdirə bilmərik.
  • Yuxarıdakı şəkildə, hər iki ada eynidir, buna görə də fərqli adaların sayı 1-dir.
Input:  grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3

Explanation:

Fərqli adaların sayı Leetcode həlliPin

  • Daha yaxşı başa düşmək üçün yuxarıdakı diaqramı yoxlayın.
  • Qeyd edək ki, yuxarı sağ küncdə və aşağı sol küncdəki adalar eyni, yuxarı sol künc və aşağı sağ küncdəki adalar fərqlidir.
  • Beləliklə, fərqli adaların ümumi sayı 3-dür.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Genişlik-İlk Axtarış.
  2. Matrisdə Genişlik-Birinci Axtarış aparın və bütün adaları tapın (1-in əlaqəli komponentləri).
  3. Necə tapmaq adaların sayı? İki və ya daha çox adanın olduğu halda necə davranmaq olar eyni forma?
    1. Adanı təşkil edən koordinatlar toplusunu nəzərdən keçirək.
    2. Tapmaq minimum x koordinatı və minimum y koordinatı koordinatlar dəsti arasında bu koordinat olacaq baza koordinatı adanı təşkil edən bütün koordinat dəstləri üçün.
    3. Hamısını tapın yeni koordinatlar ilə bağlı cari ada üçün baza koordinatı.
    4. İki və ya daha çox ada var eyni forma varsa eyni koordinatlar dəsti onların əsas koordinatlarına görə.
  4. Bütün belə koordinat massivlərini a-da saxlayın Set, nəhayət təyin edilmiş ölçü bizim cavabımızdır, çünki dəst bütün fərqli adaların dəsti olan bütün fərqli koordinat dəstlərini saxlayacaq.

Kodu

Fərqli Adaların sayı Leetcode C++ Həlli:

class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int n = grid.size(),m = grid.back().size();
        vector<vector<bool>> vis(n,vector<bool>(m));
        set<vector<pair<int,int>>> distinct;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!grid[i][j]){
                    continue;
                }
                vector<pair<int,int>> coord;
                int mn_x = INT_MAX,mn_y = INT_MAX;
                queue<array<int,2>> q;
                q.push({i,j});
                grid[i][j] = 0;                
                while(!q.empty()){
                    int x = q.front()[0],y = q.front()[1];
                    q.pop();
                    mn_x = min(mn_x,x);
                    mn_y = min(mn_y,y);
                    coord.push_back({x,y});
                    for(int dx=-1;dx<=1;dx++){
                        for(int dy=-1;dy<=1;dy++){
                            int xx = x + dx,yy = y + dy;
                            if(xx<n and xx>=0 and yy<m and yy>=0 and abs(xx-x)+abs(yy-y)==1 and grid[xx][yy]==1){
                                q.push({xx,yy});
                                grid[xx][yy] = 0;
                            }
                        }
                    }
                }                
                for(auto& p:coord){
                    p.first-=mn_x;
                    p.second-=mn_y;
                }                
                sort(coord.begin(),coord.end());
                distinct.insert(coord);
            }
        }
        return distinct.size();
    }
};

Fərqli Adaların sayı Leetcode Java Həll:

class Solution {
    private int R[] = {0, 0, 1, -1};
    private int C[] = {1, -1, 0, 0};
    private int D[] = {1, 2, 3, 4};
    public int numDistinctIslands(int[][] grid) {
        Set<String> distinct = new HashSet<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    distinct.add(layout(i, j, grid));
                }
            }
        }
        return distinct.size();
    }
    private String layout(int i, int j, int grid[][]) {
        StringBuilder sb = new StringBuilder();
        Queue<int[]> queue = new LinkedList<>();
        int size, current[], nR, nC;
        queue.add(new int[] {i, j});
        while (!queue.isEmpty()) {
            size = queue.size();
            while (size != 0) {
                size--;
                current = queue.poll();
                for (int k = 0; k < R.length; k++) {
                    nR = current[0] + R[k];
                    nC = current[1] + C[k];
                    if (nR < 0 || nR == grid.length || nC < 0 || nC == grid[0].length || grid[nR][nC] != 1) {
                        sb.append(0);
                        continue;
                    }                    
                    if (grid[nR][nC] == 1) {
                        queue.add(new int[]{nR,nC});
                        grid[nR][nC] = 2;
                        sb.append(D[k]);
                    }
                }
            }
        }        
        return sb.toString();
    }
}

Fərqli 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*Mlog(N*M)) çünki matrisin hüceyrələrini nəzərdən keçiririk və hüceyrələrin çeşidlənməsi loqarifmik vaxt aparır.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N * M) koordinatlar dəstini saxlamaq üçün çoxluğa ehtiyacımız olduğundan və ən pis halda O(N*M) Boşluq tutur.

Translate »