FB面经 Prepare: Count Unique Island

时间:2021-08-23 04:42:59
数unique island, 比如

110000

110001

001101

101100

100000

总共两个unique岛,不是四个

方法可以是记录每次新的岛屿搜索的路径,left,right,up,down, 作为标志是否相同的key,存hashset

 package fbOnsite;
import java.util.*;
public class UniqueIsland {
public int countIsland(int[][] grid) {
HashSet<String> set = new HashSet<String>(); for (int i=0; i<grid.length; i++) {
for (int j=0; j<grid[0].length; j++) {
if (grid[i][j] != 1) continue;
StringBuilder path = new StringBuilder();
dfs(grid, i, j, path.append('s')); //start
set.add(path.toString());
}
} for(String str : set) {
System.out.println(str);
} return set.size();
} public void dfs(int[][] grid, int i, int j, StringBuilder sb) {
grid[i][j] = 2;
//up
if (i>=1 && grid[i-1][j]==1) dfs(grid, i-1, j, sb.append('u'));
//right
if (j<grid[0].length-1 && grid[i][j+1]==1) dfs(grid, i, j+1, sb.append('r'));
//down
if (i<grid.length-1 && grid[i+1][j]==1) dfs(grid, i+1, j, sb.append('d'));
//left
if (j>=1 && grid[i][j-1]==1) dfs(grid, i, j-1, sb.append('l'));
} /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
UniqueIsland sol = new UniqueIsland();
int[][] grid = new int[][]{{1,1,0,0,0,0},{1,1,0,0,0,1},{0,0,1,1,0,0},{1,0,1,1,0,0,},{1,0,0,0,0,0}};
int res = sol.countIsland(grid);
System.out.println(res);
} }