当前位置：网站首页>【leetcode】1020. Number of enclaves
【leetcode】1020. Number of enclaves
2022-07-07 07:21:00 【Chinese fir sauce_】
subject ：
- 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 is 0 or 1
Method 1 ： Depth-first search
Ideas ：
Definition of enclave ： If a land cell starts, it cannot move to the grid boundary , Then this land cell is an enclave .
So we can divide all land cells into two categories ： The first type of land cells are connected to the network boundary , These land cells are not enclaves ; The second type of land cells are not connected to the grid , These land cells are enclaves .
We can start the depth first search from each land cell on the network boundary , After traversing the boundary , All land cells connected to the grid boundary are accessed . Then traverse the entire grid , If a land cell in the grid has not been accessed , Then the land cell is not connected to the boundary of the grid , It's an enclave .
And because the cells on the grid boundary must not be enclaves , So when traversing the grid and counting the number of enclaves , Just traverse the cells that are not on the grid boundary .
class Solution {
public static int[][] dirs = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
private int m, n;
private 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 enclaves = 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]) {
enclaves++;
}
}
}
return enclaves;
}
public void dfs(int[][] grid, int row, int col) {
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
return;
}
visited[row][col] = true;
for (int[] dir : dirs) {
dfs(grid, row + dir[0], col + dir[1]);
}
}
}
Complexity analysis ：
- Time complexity ：O(mn),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).
Method 2 ： Breadth first search
You can also judge whether each land cell is connected to the grid boundary by breadth first search .
First, start breadth first search from each land cell on the grid boundary , Access all land cells connected to the boundary , Then traverse the entire grid , Count the number of enclaves .
class Solution {
public static int[][] dirs = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new ArrayDeque<int[]>();
for (int i = 0; i < m; i++) {
if (grid[i][0] == 1) {
visited[i][0] = true;
queue.offer(new int[]{
i, 0});
}
if (grid[i][n - 1] == 1) {
visited[i][n - 1] = true;
queue.offer(new int[]{
i, n - 1});
}
}
for (int j = 1; j < n - 1; j++) {
if (grid[0][j] == 1) {
visited[0][j] = true;
queue.offer(new int[]{
0, j});
}
if (grid[m - 1][j] == 1) {
visited[m - 1][j] = true;
queue.offer(new int[]{
m - 1, j});
}
}
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int currRow = cell[0], currCol = cell[1];
for (int[] dir : dirs) {
int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
visited[nextRow][nextCol] = true;
queue.offer(new int[]{
nextRow, nextCol});
}
}
}
int enclaves = 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]) {
enclaves++;
}
}
}
return enclaves;
}
}
Complexity analysis ：
- Time complexity analysis ：O(mn), among m and n Namely 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).
Method 3 ： Union checking set
In addition to depth first search and breadth first search , You can also use and look up sets to determine whether each land cell is connected to the grid boundary .
The core idea of joint search is to calculate the connected component of each land cell in the grid . For each land cell on the grid boundary , All land cells in the connected component are not enclaves . If the connected component of a land cell is different from the connected component of a land cell on any grid boundary , Then the land cell is an enclave .
The way to search sets is , Traverse the entire grid , For each land cell in the grid , Merge it with all adjacent land cells . Because it is necessary to judge whether the connected component of each land cell is connected with the grid boundary , The information that each cell is connected to the grid boundary is also recorded in the one-time joint search , Update this information during the merge operation .
After traversing the grid and completing the merge operation of search set , Traverse the entire mesh again , Judge whether each land cell is connected with the grid boundary by checking the information in the set , Count the number of enclaves .
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
UnionFind uf = 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) {
uf.union(index, index + 1);
}
if (i + 1 < m && grid[i + 1][j] == 1) {
uf.union(index, index + n);
}
}
}
}
int enclaves = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
enclaves++;
}
}
}
return enclaves;
}
}
class UnionFind {
private int[] parent;
private boolean[] onEdge;
private int[] rank;
public UnionFind(int[][] grid) {
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
onEdge = new boolean[m * n];
rank = new int[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;
parent[index] = index;
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
onEdge[index] = true;
}
}
}
}
}
public int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
onEdge[rootx] |= onEdge[rooty];
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
onEdge[rooty] |= onEdge[rootx];
} else {
parent[rooty] = rootx;
onEdge[rootx] |= onEdge[rooty];
rank[rootx]++;
}
}
}
public boolean isOnEdge(int i) {
return onEdge[find(i)];
}
}
Complexity analysis ：
- Time complexity ：O(mn x α(mn)), among m and n Respectively, in the 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 x α(mn)), After the set search operation, you need O(mn x α(mn)) Time to traverse the grid again and count the number of enclaves , So the total time complexity is O(mn x α(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 .
边栏推荐
- Asynchronous components and suspend (in real development)
- How does an enterprise manage data? Share the experience summary of four aspects of data governance
- Config distributed configuration center
- Please answer the questions about database data transfer
- Composition API premise
- Big coffee gathering ｜ nextarch foundation cloud development meetup is coming
- 虚拟机的作用
- After the promotion, sales volume and flow are both. Is it really easy to relax?
- 抽丝剥茧C语言（高阶）指针的进阶
- Complete process of MySQL SQL
猜你喜欢
Kuboard can't send email and nail alarm problem is solved
Unity3d learning notes
Complete process of MySQL SQL
$parent (get parent component) and $root (get root component)
2018 Jiangsu Vocational College skills competition vocational group "information security management and evaluation" competition assignment
关于二进制无法精确表示小数
About binary cannot express decimals accurately
Abnova circulating tumor DNA whole blood isolation, genomic DNA extraction and analysis
Pass child component to parent component
Non empty verification of collection in SQL
随机推荐
計算機服務中缺失MySQL服務
Please tell me how to monitor multiple schemas and tables by listening to PgSQL
How can clothing stores make profits?
The currently released SKU (sales specification) information contains words that are suspected to have nothing to do with baby
How Oracle backs up indexes
How can gyms improve their competitiveness?
修改Jupyter Notebook文件路径
Test of transform parameters of impdp
Software acceptance test
sql中对集合进行非空校验
LC 面试题 02.07. 链表相交 ＆ LC142. 环形链表II
Several important steps to light up the display
选择商品属性弹框从底部弹出动画效果
A slow SQL drags the whole system down
Paranoid unqualified company
How DHCP router works
Initial experience of addresssanitizer Technology
How can brand e-commerce grow against the trend? See the future here!
云备份项目
From zero to one, I will teach you to build the "clip search by text" search service (2): 5 minutes to realize the prototype