LC: 694. Number of Distinct Islands
https://leetcode.com/problems/number-of-distinct-islands/
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Return the number of distinct islands.
Example 1:
Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1Example 2:
Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
The Essence:
Wenn man ein zweidimensionales Array durchläuft, kann man annehmen, dass man zuerst die obere linke Ecke einer Insel begegnet, die der Wurzel des entsprechenden gerichteten Baums ist. Die Insel kann also durch die Eigenschaften wie Richtung und Abstand von anderen Knoten in Bezug auf diesen Wurzel beschrieben werden.
Details:
Die intuitivste Lösung ist einfach die Koordinaten anderer Knoten der Insel in Bezug auf den Wurzel in einer Liste hinzufügen und dann diese Liste in einer Menge-Datenstruktur wie die Hashset in Java speichern. Die Anzahl der Inseln ist einfach die Anzahl der Elemente der Liste. Man kann auch “Insel-Strings” bilden, indem man die Richtungen Traversierung aus dem Wurzel als Zeichen zu einem String zufügt.
Solutions and Further Explanations:
Last updated