运城可以做网站的公司,网络服务器可提供的常见服务有什么服务,推进门户网站建设,wordpress 一页一屏文章目录 一、1020、飞地的数量二、130、被围绕的区域三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、1020、飞地的数量 思路分析#xff1a;博主认为题目很抽象#xff0c;非常难理解。想了好久#xff0c;要理解… 文章目录 一、1020、飞地的数量二、130、被围绕的区域三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、1020、飞地的数量 思路分析博主认为题目很抽象非常难理解。想了好久要理解题目什么意思必须理解“移动”这个概念。“移动”是指陆地可以移动移动到连接的陆地单元或者跨过边界。例如示例1中的(1, 0)这块陆地可以移出边界示例2中(2, 2)这块陆地可以按照 ( 1 , 2 ) − ( 0 , 2 ) − ( 0 , 1 ) − 边界外 (1, 2)-(0, 2)-(0, 1)-边界外 (1,2)−(0,2)−(0,1)−边界外 的顺序离开网格边界。其他的陆地也类似连接的陆地都可以移出边界。另一方面从题目来理解更简单要求飞地的数量。所谓飞地就是不和边界挨着的陆地这也和任意次数“移动”出网格边界的定义一致。 飞地的数量我们一眼就能看出不和边界挨着的就是飞地。反过来想我们顺着边界找到所有连接的陆地讲这些陆地全部删除剩下的就都是飞地然后统计数量即可。程序当中删除的这一操作不必实际进行我们将其标记为已遍历只要坐标是陆地且没有被遍历过就是飞地。 程序如下
// 1020、飞地的数量-深度优先搜索
class Solution {
private:int Area 0;vectorvectorint delta_x_y { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; // 上下左右四个方向的偏移量void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) { // 1、递归输入参数// 2、终止条件 访问过或者遇到海水又或者越界if (x 0 || x grid.size() || y 0 || y grid[0].size() || visited[x][y] || grid[x][y] 0) return; // 越界了直接跳过visited[x][y] true;//grid[x][y] 0; // 可以省略// 3、单层递归逻辑for (int i 0; i 4; i) {int nextx x delta_x_y[i][0];int nexty y delta_x_y[i][1]; dfs(grid, visited, nextx, nexty);}}
public:int numEnclaves(vectorvectorint grid) {vectorvectorbool visited vectorvectorbool(grid.size(), vectorbool(grid[0].size(), false)); // 遍历过的坐标// 遍历最外面的一圈for (int i 0; i grid.size(); i) { // 遍历两列dfs(grid, visited, i, 0);dfs(grid, visited, i, grid[0].size() - 1);}for (int j 1; j grid[0].size() - 1; j) { // 遍历两行dfs(grid, visited, 0, j);dfs(grid, visited, grid.size() - 1, j);}for (int i 1; i grid.size() - 1; i) { // 遍历行for (int j 1; j grid[0].size() - 1; j) { // 遍历列if (grid[i][j] 1 !visited[i][j]) Area; // 深度优先搜索将连接的陆地都标记上true}}return Area;}
};复杂度分析
时间复杂度 O ( m × n ) O(m \times n) O(m×n)其中 m m m和 n n n分别是岛屿数组的行数和列数。空间复杂度 O ( m × n ) O(m \times n) O(m×n)主要是栈的调用最坏情况下网格全是陆地深度优先搜索的深度达到 m × n m \times n m×n。
二、130、被围绕的区域 思路分析 程序如下 复杂度分析
时间复杂度 O ( ) O() O()。空间复杂度 O ( ) O() O()。
三、完整代码 end
