一刷 05/2022
Version #1 BFS
参考LC649
重点是把一个island normalize
这里可以hash成一个string
StringBuilder append 加String.format很慢，要避免，最好一个一个append
Runtime: 281 ms, faster than 12.12% of Java online submissions for Number of Distinct Islands II.
Memory Usage: 73.3 MB, less than 16.67% of Java online submissions for Number of Distinct Islands II.
class Solution {
public int numDistinctIslands2(int[][] grid) {
// find all grids of an island
// enumerate all transformations of that island
// Normalize those transformations by calculating the relative position of the left & top point
// Sort all the transformations and use the minimum representative to represent the island
// Use a hash set to deduplicate
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int rows = grid.length, cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Set<String> islands = new HashSet<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (!visited[y][x] && grid[y][x] == 1) {
String island = normalize(findIsland(grid, y, x, visited));
islands.add(island);
}
}
}
return islands.size();
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private List<List<Integer>> findIsland(int[][] grid, int y, int x, boolean[][] visited) {
List<List<Integer>> island = new ArrayList<>();
Queue<List<Integer>> que = new ArrayDeque<>();
que.offer(Arrays.asList(y, x));
visited[y][x] = true;
while (!que.isEmpty()) {
List<Integer> curr = que.poll();
island.add(curr);
// go to 4 directions
for (int i = 0; i < 4; i++) {
int ny = curr.get(0) + dy[i];
int nx = curr.get(1) + dx[i];
// out of boundary
if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {
continue;
}
if (!visited[ny][nx] && grid[ny][nx] == 1) {
visited[ny][nx] = true;
que.offer(Arrays.asList(ny, nx));
}
}
}
return island;
}
private String normalize(List<List<Integer>> island) {
List<List<List<Integer>>> transformations = new ArrayList<>();
List<String> strs = new ArrayList<>();
for (int i = 0; i < 8; i++) {
transformations.add(new ArrayList<>());
}
for (List<Integer> curr : island) {
int y = curr.get(0);
int x = curr.get(1);
transformations.get(0).add(Arrays.asList(x, y));
transformations.get(1).add(Arrays.asList(-x, y));
transformations.get(2).add(Arrays.asList(x, -y));
transformations.get(3).add(Arrays.asList(-x, -y));
transformations.get(4).add(Arrays.asList(y, x));
transformations.get(5).add(Arrays.asList(-y, x));
transformations.get(6).add(Arrays.asList(y, -x));
transformations.get(7).add(Arrays.asList(-y, -x));
}
StringBuilder sb = new StringBuilder();
for (List<List<Integer>> transformation : transformations) {
Collections.sort(transformation, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> a, List<Integer> b) {
if (a.get(0) != b.get(0)) {
return a.get(0) - b.get(0);
}
return a.get(1) - b.get(1);
}
});
Integer y0 = transformation.get(0).get(0);
Integer x0 = transformation.get(0).get(1);
for (int i = 0; i < transformation.size(); i++) {
List<Integer> yx = transformation.get(i);
// y = yx.get(0) - y0
// x = yx.get(1) - x0
sb.append("(" + (yx.get(0) - y0) + "," + (yx.get(1) - x0) + ")");
}
strs.add(sb.toString());
sb.setLength(0);
}
Collections.sort(strs);
return strs.get(0);
}
}
Version #2 DFS
Runtime: 115 ms, faster than 45.45% of Java online submissions for Number of Distinct Islands II.
Memory Usage: 67.6 MB, less than 71.21% of Java online submissions for Number of Distinct Islands II.
class Solution {
class Point implements Comparable<Point> {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point p) {
if (this.y != p.y) {
return this.y - p.y;
}
return this.x - p.x;
}
@Override
public String toString() {
return String.format("(%s,%s)", x, y);
}
}
public int numDistinctIslands2(int[][] grid) {
// find all grids of an island
// enumerate all transformations of that island
// Normalize those transformations by calculating the relative position of the left & top point
// Sort all the transformations and use the minimum representative to represent the island
// Use a hash set to deduplicate
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int rows = grid.length, cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Set<String> islands = new HashSet<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (!visited[y][x] && grid[y][x] == 1) {
List<Point> island = new ArrayList<>();
visited[y][x] = true;
findIsland(grid, y, x, visited, island);
String str = normalize(island);
islands.add(str);
}
}
}
return islands.size();
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void findIsland(int[][] grid, int y, int x, boolean[][] visited, List<Point> island) {
island.add(new Point(x, y));
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {
continue;
}
if (!visited[ny][nx] && grid[ny][nx] == 1) {
visited[ny][nx] = true;
findIsland(grid, ny, nx, visited, island);
}
}
}
private String normalize(List<Point> island) {
List<Point>[] transformations = new List[8];
String[] strs = new String[8];
for (int i = 0; i < 8; i++) {
transformations[i] = new ArrayList<>();
}
for (Point p : island) {
int y = p.y;
int x = p.x;
transformations[0].add(new Point(x, y));
transformations[1].add(new Point(-x, y));
transformations[2].add(new Point(x, -y));
transformations[3].add(new Point(-x, -y));
transformations[4].add(new Point(y, x));
transformations[5].add(new Point(-y, x));
transformations[6].add(new Point(y, -x));
transformations[7].add(new Point(-y, -x));
}
for (int i = 0; i < 8; i++) {
StringBuilder sb = new StringBuilder();
Collections.sort(transformations[i]);
int x0 = transformations[i].get(0).x;
int y0 = transformations[i].get(0).y;
for (Point p : transformations[i]) {
sb.append(String.format("(%s,%s)", p.x - x0, p.y - y0));
}
strs[i] = sb.toString();
}
Arrays.sort(strs);
return strs[0];
}
}
