当前位置:网站首页>LeetCode 1020. Number of enclaves
LeetCode 1020. Number of enclaves
2022-07-06 16:43:00 【Daylight629】
1020. The number of enclaves
Give you a size of m x n
The binary matrix of grid
, among 0
Represents an ocean cell 、1
Represents a land cell .
once Move It refers to walking from one land cell to another ( On 、 Next 、 Left 、 Right ) Land cells or across grid
The boundary of the .
Return to grid unable The number of land cells that leave the grid boundary in any number of moves .
Example 1:
Input :grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output :3
explain : There are three 1 By 0 Surround . One 1 Not surrounded , Because it's on the border .
Example 2:
Input :grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output :0
explain : all 1 Are on the boundary or can reach the boundary .
Tips :
m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j]
The value of is0
or1
Two 、 Method 1
Depth-first search
class Solution {
int m;
int n;
boolean[][] visited;
public int numEnclaves(int[][] grid) {
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
int res = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
res++;
}
}
}
return res;
}
public void dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) {
return;
}
visited[x][y] = true;
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
}
}
Complexity analysis
Time complexity :O(mn), among m and n Grid grid The number of rows and columns . Depth first search accesses each cell at most once , need O(mn) Time for , Traversing the grid to count the number of enclaves also needs O(mn) Time for .
Spatial complexity :O(mn), among m and n Grid grid The number of rows and columns . The spatial complexity mainly depends on visited Array and recursive call stack space , The space complexity is O(mn).
3、 ... and 、 Method 2
Breadth first search
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
int[][] dirs = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
for (int i = 0; i < m; i++) {
if (grid[i][0] == 1) {
visited[i][0] = true;
queue.add(new int[]{
i, 0});
}
if (grid[i][n - 1] == 1) {
visited[i][n - 1] = true;
queue.add(new int[] {
i, n - 1});
}
}
for (int j = 1; j < n - 1; j++) {
if (grid[0][j] == 1) {
visited[0][j] = true;
queue.add(new int[]{
0, j});
}
if (grid[m - 1][j] == 1) {
visited[m - 1][j] = true;
queue.add(new int[]{
m - 1, j});
}
}
while(!queue.isEmpty()) {
int[] pos = queue.poll();
int x = pos[0];
int y = pos[1];
for (int[] dir : dirs) {
int row = x + dir[0];
int col = y + dir[1];
if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 1 && !visited[row][col]) {
visited[row][col] = true;
queue.add(new int[]{
row, col});
}
}
}
int res = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
res++;
}
}
}
return res;
}
}
Complexity analysis
Time complexity :O(mn), among m and n Grid grid The number of rows and columns . Breadth first search accesses each cell at most once , need O(mn) Time for , Traversing the grid to count the number of enclaves also needs O(mn) Time for .
Spatial complexity :O(mn), among m and n Grid \grid The number of rows and columns . The spatial complexity mainly depends on visited Array and queue space , The space complexity is O(mn).
Four 、 Method 3
Union checking set
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
UnionFind union = new UnionFind(grid);
for (int i = 0; i < m; i++) {
for (int j = 0; j< n; j++) {
if (grid[i][j] == 1) {
int index = i * n + j;
if (j + 1 < n && grid[i][j + 1] == 1) {
union.union(index, index + 1);
}
if (i + 1 < m && grid[i + 1][j] == 1) {
union.union(index, index + n);
}
}
}
}
int res = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !union.isEdge(i * n + j)) {
res++;
}
}
}
return res;
}
class UnionFind{
int[] p;
int[] r;
boolean[] edge;
public UnionFind(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
p = new int[m * n];
r = new int[m * n];
edge = new boolean[m * n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int index = i * n + j;
p[index] = index;
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
edge[index] = true;
}
}
}
}
}
public int find(int x) {
if (p[x] != x) {
return find(p[x]);
}
return p[x];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (r[rootx] > r[rooty]) {
p[rooty] = rootx;
edge[rootx] |= edge[rooty];
} else if (r[rooty] > r[rootx]) {
p[rootx] = rooty;
edge[rooty] |= edge[rootx];
} else {
p[rooty] = rootx;
edge[rootx] |= edge[rooty];
r[rootx]++;
}
}
public boolean isEdge(int i) {
return edge[find(i)];
}
}
}
Complexity analysis
Time complexity :O(mn×α(mn)), among m and n Grid grid The number of rows and columns ,α Is the inverse Ackerman function . The join search set here uses path compression and rank merging , The time complexity of a single operation is O(α(mn)), Therefore, the time complexity of the set merging operation of the whole grid is O(mn×α(mn)), After the set search operation, you need O(mn×α(mn)) Time to traverse the grid again and count the number of enclaves , So the total time complexity is O(mn×α(mn)).
Spatial complexity :O(mn), among m and n Grid grid The number of rows and columns . And search the set needs O(mn) Space .
边栏推荐
- LeetCode 1560. The sector with the most passes on the circular track
- Research Report on market supply and demand and strategy of double drum magnetic separator industry in China
- Raspberry pie 4b64 bit system installation miniconda (it took a few days to finally solve it)
- Mp4 format details
- China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
- It is forbidden to trigger onchange in antd upload beforeupload
- The concept of spark independent cluster worker and executor
- Hbuilder X格式化快捷键设置
- 业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事
- (lightoj - 1354) IP checking (Analog)
猜你喜欢
< li> dot style list style type
Mp4 format details
提交Spark应用的若干问题记录(sparklauncher with cluster deploy mode)
JS encapsulates the method of array inversion -- Feng Hao's blog
Problem - 922D、Robot Vacuum Cleaner - Codeforces
Chapter 2 shell operation of hfds
Install Jupiter notebook under Anaconda
Two weeks' experience of intermediate software designer in the crash soft exam
Gridhome, a static site generator that novices must know
QT realizes window topping, topping state switching, and multi window topping priority relationship
随机推荐
< li> dot style list style type
新手必会的静态站点生成器——Gridsome
(POJ - 1458) common subsequence (longest common subsequence)
Market trend report, technological innovation and market forecast of desktop electric tools in China
Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
It is forbidden to trigger onchange in antd upload beforeupload
<li>圆点样式 list-style-type
Problem - 922D、Robot Vacuum Cleaner - Codeforces
业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事
业务系统从Oracle迁移到openGauss数据库的简单记录
Input can only input numbers, limited input
LeetCode 1545. Find the k-th bit in the nth binary string
解决Intel12代酷睿CPU单线程调度问题(二)
Click QT button to switch qlineedit focus (including code)
Tree of life (tree DP)
OneForAll安装使用
Remove the border when input is focused
js时间函数大全 详细的讲解 -----阿浩博客
QT implementation fillet window
875. Leetcode, a banana lover