leetcode-827:最大人工岛

简介: leetcode-827:最大人工岛

题目

题目连接

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后,grid 中最大的岛屿面积是多少?

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1,最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1,岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1,面积依然为 4。

解题

方法一:dfs+map+枚举变化点

通过map记录每个岛屿对应的面积

通过不同值去标记不同的岛屿。

然后遍历矩阵,尝试让0变成1,然后查看最大面积

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{1,0},{0,-1},{0,1}};
    void dfs(unordered_map<int,int>& mp,vector<vector<int>>& grid,int id,int x,int y,int& area){
        grid[x][y]=id;
        area++;
        for(vector<int>& dir:dirs){
            int nx=x+dir[0];
            int ny=y+dir[1];
            if(nx<0||nx>=grid.size()||ny<0||ny>=grid.size()||grid[nx][ny]!=1) continue;
            dfs(mp,grid,id,nx,ny,area);
        }
    }
    int largestIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        int id=-1;
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=1) continue;
                int area=0;
                dfs(mp,grid,id,i,j,area);
                mp[id]=area;
                id--;
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    unordered_set<int> set;
                    int cur=1;
                    for(vector<int>& dir:dirs){
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        if(!set.count(grid[nx][ny])){
                            cur+=mp[grid[nx][ny]];
                            set.insert(grid[nx][ny]);
                        }
                    }
                    res=max(res,cur);
                }
            }
        }
        return res==0?n*n:res;//全1的情况下res不会进行更新。 只要有0, res至少为1
    }
};

方法二:并查集+枚举

查并集,可以查看每个集合中元素的数量

第一次遍历,将相邻的陆地加入到一个集合中

第二次遍历,如何相邻岛屿,那么就将它们岛屿的面积(集合的大小)加起来,注意去重。

class UnionFind{
public:
    vector<int> parent;
    vector<int> size;
    UnionFind(int n){
        parent.resize(n*n);
        size.resize(n*n,1);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){
        if(index==parent[index]) return index;
        return parent[index]=find(parent[index]);
    }
    void unite(int index1,int index2){
        int p1=find(index1),p2=find(index2);
        parent[p1]=p2;
        if(p1!=p2){//如果相等,会出现把size[p1]=size[p2]=0 都清空
            size[p2]+=size[p1];
            size[p1]=0;
        }
    }
    int getSize(int index){
        return size[find(index)];
    }
};
class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}};
    int largestIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        UnionFind uf(n);
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    for(int k=0;k<2;k++){
                        vector<int>& dir=dirs[k];
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        uf.unite(nx*n+ny,i*n+j);
                    }
                    res=max(res,uf.getSize(i*n+j));
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    int cur=1;
                    unordered_set<int> set;
                    for(vector<int>& dir:dirs){
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        int p=uf.find(nx*n+ny);
                        if(!set.count(p)){
                            cur+=uf.getSize(p);
                            set.insert(p);
                        }
                    }
                    res=max(cur,res);
                }
            }
        }
        return res;
    }
};
目录
打赏
0
0
0
0
7
分享
相关文章
一和零(LeetCode 474)
一和零(LeetCode 474)
105 0
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
111 0
leetcode第39题
leetcode第47题
基本上都是在上道题的基础上改出来了,一些技巧也是经常遇到,比如先排序,然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据,然后再想办法还原。
100 0
leetcode第47题
leetcode第49题
时间复杂度:两层 for 循环,再加上比较字符串,如果字符串最长为 K,总的时间复杂度就是 O(n²K)。 空间复杂度:O(NK),用来存储结果。 解法一算是比较通用的解法,不管字符串里边是大写字母,小写字母,数字,都可以用这个算法解决。这道题的话,题目告诉我们字符串中只有小写字母,针对这个限制,我们可以再用一些针对性强的算法。 下边的算法本质是,我们只要把一类的字符串用某一种方法唯一的映射到同一个位置就可以。
200 0
leetcode第49题
leetcode第42题
也就是红色区域中的水, 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2,temp ++,高度大于等于 2,ans = ans + temp,temp = 0。 temp 初始化为 0 ,ans 此时等于 2。 height [ 0 ] 等于 0 < 2,不更新。 height [ 1 ] 等于 1 < 2,不更新。 height [ 2 ] 等于 0 < 2, 不更新。 height [ 3 ] 等于 2 >= 2, 开始更新 height [ 4 ] 等于 1 < 2,temp = temp + 1 = 1。 h
118 0
leetcode第42题
leetcode第31题
我们想几个问题。 要想使得数字变大,只要任意一位变大就可以。 要想得到刚好大于原来的数字,要变个位。 这里变大数字,只能利用交换。 如果从个位开始,从右往左进行,找一个比个位大的,交换过来,个位的数字交换到了更高位,由于个位的数字较小,所以交换过去虽然个位变大了,但数字整体变小了。例如 1 3 2,把 2 和 3 交换,变成 1 2 3,个位变大了,但整体数字变小了。 个位不行,我们再看十位,如果从十位左边找一个更大的数字交换过来,和个位的情况是一样的,数字会变小。例如 4 1 2 3,把 2 和 4 交换,2 1 4 3,数字会变小。如果从
106 0
leetcode第31题
leetcode第29题
这道题看起来简单,却藏了不少坑。首先,我们用一次一次减造成了超时,然后我们用递归实现了加倍加倍的减,接着由于 int 表示的数的范围不是对称的,最小的负数并不能转换为对应的相反数,所以我们将之前的算法思路完全逆过来,正数边负数,大于变小于,还是蛮有意思的。
110 0
leetcode第29题
leetcode第32题
这几种算法,暴力破解和动态规划我觉得想的话,还是能分析出来的话,最后两种算法感觉是去挖掘题的本质得到的算法,普适性不是很强。但最后一种算法,从左到右,从右到左,是真的强。
117 0
leetcode第32题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等