Mündəricat
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:
- 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:
- 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:
- Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Genişlik-İlk Axtarış.
- Matrisdə Genişlik-Birinci Axtarış aparın və bütün adaları tapın (1-in əlaqəli komponentləri).
- Necə tapmaq adaların sayı? İki və ya daha çox adanın olduğu halda necə davranmaq olar eyni forma?
- Adanı təşkil edən koordinatlar toplusunu nəzərdən keçirək.
- 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.
- Hamısını tapın yeni koordinatlar ilə bağlı cari ada üçün baza koordinatı.
- İki və ya daha çox ada var eyni forma varsa eyni koordinatlar dəsti onların əsas koordinatlarına görə.
- 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.
