- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/number-of-islands/description/
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:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
有一片水域,四联通的算一个岛,求所有的岛的数目。
这个题在《挑战程序设计竞赛》书的前面就讲了,我觉得还是挺经典的题目。可以直接套模板解决。
做法是,我们对每个有“1"
的位置进行 DFS,把和它四联通的位置全部变成“0”
,这样就能把一个点推广到一个岛。
所以,我们总的进行了 DFS 的次数,就是总过有多少个岛的数目。
注意理解dfs函数的意义:已知当前是1,把它周围相邻的所有1全部转成0.
代码如下:
class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
res = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
self.dfs(grid, r, c)
res += 1
return res
def dfs(self, grid, i, j):
dirs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
grid[i][j] = "0"
for dir in dirs:
nr, nc = i + dir[0], j + dir[1]
if nr >= 0 and nc >= 0 and nr < len(grid) and nc < len(grid[0]):
if grid[nr][nc] == "1":
self.dfs(grid, nr, nc)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
C++版本的代码如下:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty())
return 0;
const int M = grid.size();
const int N = grid[0].size();
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1') {
res ++;
dfs(grid, i, j);
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, int x, int y) {
grid[x][y] = '0';
const int M = grid.size();
const int N = grid[0].size();
for (auto& dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx < 0 || nx >= M || ny < 0 || ny >= N || grid[nx][ny] == '0')
continue;
dfs(grid, nx, ny);
}
}
private:
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
这个题同样可以使用BFS解决。当遇到一个小岛的时候,做个BFS搜索,把它周围的小岛全部转成0即可。速度比DFS稍微慢了一点点。
Python 代码如下:
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid or not grid[0]: return 0
M, N = len(grid), len(grid[0])
que = collections.deque()
res = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(M):
for j in range(N):
if grid[i][j] == '1':
res += 1
grid[i][j] = '0'
que.append((i, j))
while que:
x, y = que.pop()
for d in directions:
nx, ny = x + d[0], y + d[1]
if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == '1':
grid[nx][ny] = '0'
que.append((nx, ny))
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
在写BFS 的时候可以把代码包装成一个函数,需要注意的是,由于BFS会把周围的1全部改成0,所以在出队列的时候,做一个判断,如果当前围着孩子已经被改了,那么就不用下面的搜索了。
C++代码如下:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) return 0;
const int M = grid.size(), N = grid[0].size();
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1') {
++res;
bfs(grid, i, j);
}
}
}
return res;
}
// gird[x][y] = 1, delete it and its around.
void bfs(vector<vector<char>>& grid, int x, int y) {
const int M = grid.size(), N = grid[0].size();
queue<pair<int, int>> q;
q.push({x, y});
while (!q.empty()) {
auto head = q.front(); q.pop();
int x = head.first;
int y = head.second;
if (grid[x][y] != '1') continue;
grid[x][y] = '0';
for (auto d : dirs) {
int i = x + d.first;
int j = y + d.second;
if (i < 0 || i >= M || j < 0 || j >= N || grid[i][j] != '1') {
continue;
}
q.push({i, j});
}
}
}
private:
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
从 angular 5.1 更新到 6.1 后,我开始从我的代码中收到一些错误,如下所示: Error: ngc compilation failed: components/forms/utils.
我正在学习 Typescript 并尝试了解类型和接口(interface)的最佳实践。我正在玩一个使用 GPS 坐标的示例,想知道一种方法是否比另一种更好。 let gps1 : number[];
type padding = [number, number, number, number] interface IPaddingProps { defaultValue?: padding
这两种格式在内存中保存结果的顺序上有什么区别吗? number = number + 10; number += 10; 我记得一种格式会立即保存结果,因此下一行代码可以使用新值,而对于另一种格式,
在 Python 匹配模式中,如何匹配像 1 这样的文字数字在按数字反向引用后 \1 ? 我尝试了 \g用于此目的的替换模式中可用的语法,但它在我的匹配模式中不起作用。 我有一个更大的问题,我想使用一
我的源文件here包含 HTML 代码,我想将电话号码更改为可在我的应用程序中单击。我正在寻找一个正则表达式来转换字符串 >numbernumber(\d+)$1numbernumber<",我们在S
我们有一个包含 2 个字段和一个按钮的表单。我们想要点击按钮来输出位于 int A 和 int B 之间的随机整数(比如 3、5 或 33)? (不需要使用 jQuery 或类似的东西) 最佳答案 你
我收到以下类型错误(TypeScript - 3.7.5)。 error TS2345: Argument of type '(priority1: number, priority2: number
只想创建简单的填充器以在其他功能中使用它: function fillLine(row, column, length, bgcolor) { var sheet = SpreadsheetApp
我有一个问题。当我保存程序输出的 *.txt 时,我得到以下信息:0.021111111111111112a118d0 以及更多的东西。 问题是: 这个数字中的“d0”和“a”是什么意思? 我不知道“
首先:抱歉标题太长了,但我发现很难用一句话来解释这个问题;)。是的,我也四处搜索(这里和谷歌),但找不到合适的答案。 所以,问题是这样的: 数字 1-15 将像这样放在金字塔中(由数组表示):
我想从字符串中提取血压。数据可能如下所示: text <- c("at 10.00 seated 132/69", "99/49", "176/109", "10.12 I 128/51, II 1
当尝试执行一个简单的 bash 脚本以将前面带有 0 的数字递增 1 时,原始数字被错误地解释。 #!/bin/bash number=0026 echo $number echo $((number
我有一个类型为 [number, number] 的字段,TypeScript 编译器(strict 设置为 true)出现问题,提示初始值值(value)。我尝试了以下方法: public shee
你能帮我表达数组吗:["232","2323","233"] 我试试这个:/^\[("\d{1,7}")|(,"\d{1,7}")\]$/ 但是这个表达式不能正常工作。 我使用 ruby(rail
这个问题在这里已经有了答案: meaning of (number) & (-number) (4 个回答) 关闭6年前. 例如: int get(int i) { int res = 0;
我正在考虑使用 Berkeley DB作为高度并发的移动应用程序后端的一部分。对于我的应用程序,使用 Queue对于他们的记录级别锁定将是理想的。但是,如标题中所述,我需要查询和更新概念建模的数据,如
我正在尝试解决涉及重复数字的特定 JavaScript 练习,为此我需要将重复数字处理到大量小数位。 目前我正在使用: function divide(numerator, denominator){
我有这个数组类型: interface Details { Name: string; URL: string; Year: number; } interface AppState {
我们正在使用 Spring 3.x.x 和 Quartz 2.x.x 实现 Web 应用程序。 Web 服务器是 Tomcat 7.x.x。我们有 3 台服务器。 Quartz 是集群式的,因此所有这
我是一名优秀的程序员,十分优秀!