Adaların sayı II LeetCode Həll

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon alma Facebook google microsoft ÜberBaxılıb 78

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

Adaların sayı II LeetCode Həlli – Sizə boş 2D ikili şəbəkə verilir grid ölçüdə m x n. Şəbəkə harada bir xəritəni təmsil edir 0's su və təmsil edir 1torpaqlarını təmsil edir. Əvvəlcə bütün hüceyrələr  grid su hüceyrələridir (yəni bütün hüceyrələr 0s).

Yerdəki suyu quruya çevirən əlavə quru əməliyyatı həyata keçirə bilərik. Sizə massiv verilir positions hara positions[i] = [ri, ci] mövqedir (ri, ci) biz fəaliyyət göstərməliyik ith əməliyyat.

Qayıtmaq tam ədədlər massivi answer hara answer[i] hüceyrə çevrildikdən sonra adaların sayıdır (ri, ci) bir torpağa.

An ada su ilə əhatə olunub və ona bitişik torpaqları üfüqi və ya şaquli istiqamətdə birləşdirərək əmələ gəlir. Şəbəkənin bütün dörd kənarının su ilə əhatə olunduğunu güman edə bilərsiniz.

Adaların sayı II LeetCode HəllPin

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output: [1,1,2,3]
Explanation:
Initially, the 2d grid is filled with water.
- Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.

Izahat

Bu əsasdır union-find problem. Nöqtələrin əlavə olunduğu bir qrafiki nəzərə alsaq, heç olmasa həll edə bilərik:

  1. Ümumilikdə neçə ada?
  2. A nöqtəsi hansı adaya aiddir?
  3. tA nöqtəsi və B nöqtəsi bağlıdır?

Fikir sadədir. Adaların siyahısını təmsil etmək üçün istifadə edirik ağac. yəni köklərin siyahısı. Bu, adanın identifikatorunu daha tez tapmağa kömək edir. Əgər roots[c] = p c nodeunun valideyninin p olduğunu bildirir, biz adanın identifikatorunu, yəni bu nöqtənin hansı adaya aid olduğunu öyrənmək üçün ana zənciri yuxarı qalxa bilərik:

Do root[root[roots[c]]]... until root[c] == c;

İki ölçülü problemi klassik UF-ə çevirmək üçün xətti xəritələşdirmə aparın:

int id = n * x + y;

Əvvəlcə hər bir hüceyrənin qeyri-ada dəstində olduğunu fərz edin {-1}. A nöqtəsi əlavə edildikdə, yeni bir kök, yəni yeni bir ada yaradırıq. Sonra onun 4 qonşusundan hər hansı birinin eyni adaya aid olub olmadığını yoxlayın. Əgər olmasa, union kökün eyni olmasını təyin edərək qonşu. Qeyri-ada hüceyrələrini atlamağı unutmayın.

The UNION əməliyyat yalnız kök valideyni dəyişdirir, buna görə də işləmə müddəti O(1).

tapmaq əməliyyat ağacın dərinliyi ilə mütənasibdir. N əlavə edilmiş xalların sayıdırsa, orta iş vaxtıdır O(logN), və ardıcıllığı 4N əməliyyatlar aparır O(NlogN). Heç bir tarazlıq yoxdursa, daha pis vəziyyət ola bilər O(N^2).

Unutmayın ki, bir ada fərqli ola bilər roots[node] hər bir node üçün dəyər. Çünki roots[node] qovşağın anasıdır, adanın ən yüksək kökü deyil. Həqiqi kökü tapmaq üçün zəng edərək ağaca dırmaşmalıyıq tapmaq adası fəaliyyət göstərir.

Kodu

Adaların sayı üçün C++ kodu II

class Solution {
public:
    struct pair_hash {
        template <class T1, class T2>
        std::size_t operator () (const std::pair<T1,T2> &p) const {
            auto h1 = std::hash<T1>{}(p.first);
            auto h2 = std::hash<T2>{}(p.second);
            return h1 ^ h2;  
        }
    };
    
    typedef pair<int,int> _pos;
    typedef unordered_map< pair<int,int>, pair<int,int>, pair_hash> _parent_map;
    typedef unordered_map< pair<int,int>, int, pair_hash> _size_map;
    typedef vector<vector<char>> _grid; 
    int set_cnts = 0; 
    
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        int rows = m, cols = n;
        _grid grid(rows, vector<char>(cols,'0'));
        _parent_map ps;
        _size_map sz;
        vector<int> result;
        for(auto& pos :positions) {
            int row = pos[0];
            int col = pos[1];
            if(grid[row][col]=='1') {
                result.push_back(set_cnts);
                continue;
            }
            grid[row][col]='1';
            ps[{row, col}] = {row, col};
            sz[{row, col}] = 1;
            set_cnts+=1;
            if(row+1 < rows && grid[row+1][col] == '1') {
                UF_union(sz, ps, {row,col}, {row+1,col});
            }
            if(col+1 < cols && grid[row][col+1] == '1') {
                UF_union(sz, ps, {row,col}, {row,col+1});
            }
            if(col-1 >=0 && grid[row][col-1] == '1') {
                UF_union(sz, ps, {row,col}, {row,col-1});
            }                    
            if(row-1 >= 0 && grid[row-1][col] == '1') {
                UF_union(sz, ps, {row,col}, {row-1,col});
            }
            result.push_back(set_cnts);
        }
        return result;    
    }
    
    _pos UF_find_root(_parent_map& ps,  _pos node ) {
        _pos root = node;
        while(ps[root] != root) {
            root = ps[root];    
        }
        return root;
    }
    
    bool UF_is_connected(_parent_map& ps, _pos node1, _pos node2) {
        return UF_find_root(ps, node1) == UF_find_root(ps, node2);
    }
    
    void UF_union(_size_map& sz, _parent_map& ps, _pos node1, _pos node2) {
        _pos root1 = UF_find_root(ps, node1);
        _pos root2 = UF_find_root(ps, node2);
        if(root1 == root2) return;
        if(sz[root1] <sz[root2]) {
            ps[root1] = root2;
            sz[root2] += sz[root1];
        } else {
            ps[root2] = root1;
            sz[root1] += sz[root2];
        }
        set_cnts--;
    }  
};

 

Adaların sayı üçün Java kodu II

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<>();
        if (positions == null || positions.length == 0) {
            return result;
        }
        int[] root = new int[m * n];
        Arrays.fill(root, -1);
        int count = 0;
        int[] xDelta = {1, -1, 0, 0};
        int[] yDelta = {0, 0, 1, -1};
        for (int[] position : positions) {
            
            int x = position[0];
            int y = position[1];
            int index = x * n + y;
            if (root[index] != -1) {    // duplicate position
                result.add(count);
                continue;
            }
            count++;
            root[index] = index;
            for (int i = 0; i < 4; i++) {
                int r = x + xDelta[i];
                int c = y + yDelta[i];
                if (isValid(m, n, r, c, root)) {
                    int neighborIndex = r * n + c;
                    int neighborRoot = findRoot(root, neighborIndex);
                    if (neighborRoot != index) {
                        root[neighborRoot] = index;
                        count--;
                    }
                }
            }
            result.add(count);
        }
        return result;
    }
    
    private boolean isValid(int m, int n, int r, int c, int[] root) {
        if (r < 0 || c < 0 || r >= m || c >= n || root[r * n + c] == -1) {
            return false;
        }
        return true;
    }
    
    private int findRoot(int[] root, int index) {
        while (index != root[index]) {
            root[index] = root[root[index]];
            index = root[index];
        }
        return index;
    }
}

Adaların sayı üçün Python kodu II

class UF:
    
    def __init__(self, n):        
        self.parent = {i: i for i in range(n)}
        self.size = {i: 1 for i in range(n)}
    
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX == rootY:
            return
        
        if rootX <= rootY:
            self.parent[rootX] = rootY
            self.size[rootY] += self.size[rootX]
        
        else:
            self.parent[rootY] = rootX
            self.size[rootX] += self.size[rootY]
            
        
class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        
        uf = UF(m * n)
        
        res = []
        
        count = 0
        
        visited = set()
        
        for x, y in positions:
            
            if (x, y) in visited:
                res.append(count)
                continue
            
            count += 1
            visited.add((x, y))
            
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                
                xx, yy = x + dx, y + dy
                
                if xx < 0 or xx == m or yy < 0 or yy == n:
                    continue
                
                # skip water
                if (xx, yy) not in visited:
                    continue
                
                component1 = uf.find(x * n + y)
                component2 = uf.find(xx * n + yy)
                
                if component1 != component2:
                    uf.union(component1, component2)
                    count -= 1
            
            res.append(count)
        
        return res

Adaların sayı üçün mürəkkəblik təhlili II LeetCode Həlli

Zamanın mürəkkəbliyi

O( len(vəzifələr) * log mn )

Kosmik Mürəkkəblik

O (mn)

Crack Sistemi Dizayn Müsahibələri
Translate »