【LeetCode】200. Number of Islands (2 solutions)
LeetCode of number 200 Solutions
2023-09-11 14:20:27 时间
Number of Islands
Given a 2d grid map of '1'
s (land) and '0'
s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
对每次出现'1'的区域进行计数,同时深度或广度遍历,然后置为'0'。
解法一:非递归dfs
struct Node { int x; int y; Node(int newx, int newy): x(newx), y(newy) {} }; class Solution { public: int numIslands(vector<vector<char>> &grid) { int ret = 0; if(grid.empty() || grid[0].empty()) return ret; int m = grid.size(); int n = grid[0].size(); for(int i = 0; i < m; i ++) { for(int j = 0; j < n; j ++) { if(grid[i][j] == '1') { dfs(grid, i, j, m, n); ret ++; } } } return ret; } void dfs(vector<vector<char>> &grid, int i, int j, int m, int n) { stack<Node*> stk; Node* rootnode = new Node(i, j); grid[i][j] = '0'; stk.push(rootnode); while(!stk.empty()) { Node* top = stk.top(); if(top->x > 0 && grid[top->x-1][top->y] == '1') {//check up grid[top->x-1][top->y] = '0'; Node* upnode = new Node(top->x-1, top->y); stk.push(upnode); continue; } if(top->x < m-1 && grid[top->x+1][top->y] == '1') {//check down grid[top->x+1][top->y] = '0'; Node* downnode = new Node(top->x+1, top->y); stk.push(downnode); continue; } if(top->y > 0 && grid[top->x][top->y-1] == '1') {//check left grid[top->x][top->y-1] = '0'; Node* leftnode = new Node(top->x, top->y-1); stk.push(leftnode); continue; } if(top->y < n-1 && grid[top->x][top->y+1] == '1') {//check right grid[top->x][top->y+1] = '0'; Node* rightnode = new Node(top->x, top->y+1); stk.push(rightnode); continue; } stk.pop(); } } };
解法二:递归dfs
class Solution { public: int numIslands(vector<vector<char>> &grid) { int ret = 0; if(grid.empty() || grid[0].empty()) return ret; int m = grid.size(); int n = grid[0].size(); for(int i = 0; i < m; i ++) { for(int j = 0; j < n; j ++) { if(grid[i][j] == '1') { dfs(grid, i, j, m, n); ret ++; } } } return ret; } void dfs(vector<vector<char>> &grid, int i, int j, int m, int n) { grid[i][j] = '0'; if(i > 0 && grid[i-1][j] == '1') dfs(grid, i-1, j, m, n); if(i < m-1 && grid[i+1][j] == '1') dfs(grid, i+1, j, m, n); if(j > 0 && grid[i][j-1] == '1') dfs(grid, i, j-1, m, n); if(j < n-1 && grid[i][j+1] == '1') dfs(grid, i, j+1, m, n); } };
相关文章
- Leetcode: Number of Boomerangs
- Leetcode: Number of Digit One
- Leetcode: Length of Last Word
- LeetCode --- 58. Length of Last Word
- 【LeetCode】233. Number of Digit One
- 【LeetCode】17. Letter Combinations of a Phone Number
- [LeetCode] 1342. Number of Steps to Reduce a Number to Zero 将数字变成 0 的操作次数
- [LeetCode] 1326. Minimum Number of Taps to Open to Water a Garden 灌溉花园的最少水龙头数目
- [LeetCode] 1319. Number of Operations to Make Network Connected 连通网络的操作次数
- [LeetCode] 1269. Number of Ways to Stay in the Same Place After Some Steps 停在原地的方案数
- [LeetCode] 1254. Number of Closed Islands 统计封闭岛屿的数目
- [LeetCode] 891. Sum of Subsequence Widths 子序列宽度之和
- [LeetCode] 559. Maximum Depth of N-ary Tree N叉树的最大深度
- [LeetCode] 726. Number of Atoms 原子的个数
- [LeetCode] 711. Number of Distinct Islands II 不同岛屿的个数之二
- [LeetCode] 673. Number of Longest Increasing Subsequence 最长递增序列的个数
- [LeetCode] 200. Number of Islands 岛屿的数量
- Leetcode——17. Letter Combinations of a Phone Number
- leetcode 236. Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先(中等)
- leetcode 547. Number of Provinces 省份数量(中等)
- leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)