694. Number of Distinct Islands
2021/4/8 10:13:18
本文主要是介绍694. Number of Distinct Islands,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given a non-empty 2D array grid
of 0's and 1's, 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.
Count the number of distinct islands. 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.
Example 1:
11000 11000 00011 00011
Given the above grid map, return 1
.
Example 2:
11011 10000 00001 11011
Given the above grid map, return 3
.
Notice that:
11 1
and
1 11
are considered different island shapes, because we do not consider reflection / rotation.
1 class Solution { 2 int[][] dirs = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; 3 public int numDistinctIslands(int[][] grid) { 4 Set<String> set = new HashSet<>(); 5 int res = 0; 6 7 for (int i = 0; i < grid.length; i++) { 8 for (int j = 0; j < grid[0].length; j++) { 9 if (grid[i][j] == 1) { 10 StringBuilder sb = new StringBuilder(); 11 helper(grid, i, j, 0, 0, sb); 12 String s = sb.toString(); 13 if (!set.contains(s)) { 14 res++; 15 set.add(s); 16 } 17 } 18 } 19 } 20 return res; 21 } 22 23 public void helper(int[][] grid, int i, int j, int xpos, int ypos, StringBuilder sb) { 24 grid[i][j] = 0; 25 sb.append(xpos + "" + ypos); 26 for (int[] dir : dirs) { 27 int x = i + dir[0]; 28 int y = j + dir[1]; 29 if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) 30 continue; 31 helper(grid, x, y, xpos + dir[0], ypos + dir[1], sb); 32 } 33 } 34 }
这篇关于694. Number of Distinct Islands的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验