[LeetCode]|[LeetCode] 200. Number of Islands (Medium)
原题
0代表水，1代表陆地，边界土地的上下左右不相连其他土地，则称为一块陆地。
计算有几块陆地。
思路：
DFS，从起点开始，每碰到一个‘1’，就作为DFS起点，将其相近的‘1’全部变为‘0’。直到无‘1’。
【[LeetCode]|[LeetCode] 200. Number of Islands (Medium)】一开始dfs没有传参数组长度，而是每一次都调用size()，速度很慢
Runtime: 12 ms, faster than 47.97%
修改以后
Runtime: 8 ms, faster than 98.94%
class Solution
{
public:
int numIslands(vector> &grid)
{
int res = 0;
if (grid.empty())
return res;
int rowSize = grid.size();
int colSize = grid[0].size();
for (int i = 0;
i < rowSize;
i++)
{
for (int j = 0;
j < colSize;
j++)
{
if (grid[i][j] == '1')
{
dfs(grid, i, j, rowSize, colSize);
res++;
}
}
}
return res;
}
void dfs(vector> &grid, int row, int col, int rs, int cs)
{
if (grid[row][col] == '1')
{
grid[row][col] = '0';
if (row > 0 && grid[row - 1][col] == '1')
dfs(grid, row - 1, col, rs, cs);
if (row < grid.size() - 1 && grid[row + 1][col] == '1')
dfs(grid, row + 1, col, rs, cs);
if (col > 0 && grid[row][col - 1] == '1')
dfs(grid, row, col - 1, rs, cs);
if (col < grid[0].size() - 1 && grid[row][col + 1] == '1')
dfs(grid, row, col + 1, rs, cs);
}
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- LintCode|LintCode 545 [Top k Largest Number II]
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- 136.|136. Single Number
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式