2023-05-07：給你一個(gè)大小為 n x n 二進(jìn)制矩陣 grid 。最多 只能將一格 0 變成 1 。

返回執(zhí)行此操作后，grid 中最大的島嶼面積是多少？

島嶼 由一組上、下、左、右四個(gè)方向相連的 1 形成。

輸入: grid = [[1, 0], [0, 1]]。

輸出: 3。

來自亞馬遜、谷歌、微軟、Facebook、Bloomberg。

答案2023-05-07：

算法步驟：

1.遍歷輸入矩陣?grid，對(duì)于每個(gè)島嶼進(jìn)行標(biāo)記，并用數(shù)組?sizes?統(tǒng)計(jì)每個(gè)島嶼的大小。

2.遍歷矩陣?grid，對(duì)于每個(gè)位置上的值，如果當(dāng)前位置上的值為非零正整數(shù)，則更新答案為當(dāng)前島嶼的大小。

3.遍歷矩陣?grid，當(dāng)當(dāng)前位置上的值為 0 時(shí)，分別查看該位置上、下、左、右四個(gè)方向是否有與其相鄰且已經(jīng)被訪問過的島嶼，并將它們的大小累加起來。如果這些島嶼的大小之和加上當(dāng)前位置上自身的大小可以更新最大島嶼面積，則更新答案。

4.返回答案。

時(shí)間復(fù)雜度：$O(n^2)$ ，遍歷了三次矩陣，每次遍歷的時(shí)間復(fù)雜度均為 $O(n^2)$。

空間復(fù)雜度：$O(n^2)$，使用了兩個(gè)二維數(shù)組，每個(gè)數(shù)組都是 $n \times n$ 的大小。

go完整代碼如下：

package?main

import?"fmt"

func?main()?{
????grid?:=?[][]int{{1,?0},?{0,?1}}
????ans?:=?largestIsland(grid)
????fmt.Println(ans)
}

func?largestIsland(grid?[][]int)?int?{
????n?:=?len(grid)
????m?:=?len(grid[0])
????id?:=?2
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?grid[i][j]?==?1?{
????????????????infect(grid,?i,?j,?id,?n,?m)
????????????????id++
????????????}
????????}
????}
????sizes?:=?make([]int,?id)
????ans?:=?0
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?grid[i][j]?>?1?{
????????????????sizes[grid[i][j]]++
????????????????ans?=?max(ans,?sizes[grid[i][j]])
????????????}
????????}
????}
????visited?:=?make([]bool,?id)
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?grid[i][j]?==?0?{
????????????????up?:=?0
????????????????if?i-1?>=?0?{
????????????????????up?=?grid[i-1][j]
????????????????}
????????????????down?:=?0
????????????????if?i+1?<?n?{
????????????????????down?=?grid[i+1][j]
????????????????}
????????????????left?:=?0
????????????????if?j-1?>=?0?{
????????????????????left?=?grid[i][j-1]
????????????????}
????????????????right?:=?0
????????????????if?j+1?<?m?{
????????????????????right?=?grid[i][j+1]
????????????????}
????????????????merge?:=?1?+?sizes[up]
????????????????visited[up]?=?true
????????????????if?!visited[down]?{
????????????????????merge?+=?sizes[down]
????????????????????visited[down]?=?true
????????????????}
????????????????if?!visited[left]?{
????????????????????merge?+=?sizes[left]
????????????????????visited[left]?=?true
????????????????}
????????????????if?!visited[right]?{
????????????????????merge?+=?sizes[right]
????????????????????visited[right]?=?true
????????????????}
????????????????ans?=?max(ans,?merge)
????????????????visited[up]?=?false
????????????????visited[down]?=?false
????????????????visited[left]?=?false
????????????????visited[right]?=?false
????????????}
????????}
????}
????return?ans
}

func?infect(grid?[][]int,?i,?j,?v,?n,?m?int)?{
????if?i?<?0?||?i?==?n?||?j?<?0?||?j?==?m?||?grid[i][j]?!=?1?{
????????return
????}
????grid[i][j]?=?v
????infect(grid,?i-1,?j,?v,?n,?m)
????infect(grid,?i+1,?j,?v,?n,?m)
????infect(grid,?i,?j-1,?v,?n,?m)
????infect(grid,?i,?j+1,?v,?n,?m)
}

func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}


rust完整代碼如下：

fn?main()?{
????let?grid?=?vec![vec![1,?0],?vec![0,?1]];
????let?ans?=?largest_island(grid);
????println!("{}",?ans);
}

fn?largest_island(grid:?Vec<Vec<i32>>)?->?i32?{
????let?n?=?grid.len();
????let?m?=?grid[0].len();
????let?mut?id?=?2;
????let?mut?new_grid?=?grid.clone();
????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????if?new_grid[i][j]?==?1?{
????????????????infect(&mut?new_grid,?i?as?i32,?j?as?i32,?id,?n?as?i32,?m?as?i32);
????????????????id?+=?1;
????????????}
????????}
????}
????let?mut?sizes?=?vec![0;?id?as?usize];
????let?mut?ans?=?0;
????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????if?new_grid[i][j]?>?1?{
????????????????sizes[new_grid[i][j]?as?usize]?+=?1;
????????????????ans?=?ans.max(sizes[new_grid[i][j]?as?usize]);
????????????}
????????}
????}
????let?mut?visited?=?vec![false;?id?as?usize];
????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????if?new_grid[i][j]?==?0?{
????????????????let?up?=?if?i?>?0?{?new_grid[i?-?1][j]?}?else?{?0?};
????????????????let?down?=?if?i?<?n?-?1?{?new_grid[i?+?1][j]?}?else?{?0?};
????????????????let?left?=?if?j?>?0?{?new_grid[i][j?-?1]?}?else?{?0?};
????????????????let?right?=?if?j?<?m?-?1?{?new_grid[i][j?+?1]?}?else?{?0?};
????????????????let?mut?merge?=?1;
????????????????if?up?>?0?&&?!visited[up?as?usize]?{
????????????????????visited[up?as?usize]?=?true;
????????????????????merge?+=?sizes[up?as?usize];
????????????????}
????????????????if?down?>?0?&&?!visited[down?as?usize]?{
????????????????????visited[down?as?usize]?=?true;
????????????????????merge?+=?sizes[down?as?usize];
????????????????}
????????????????if?left?>?0?&&?!visited[left?as?usize]?{
????????????????????visited[left?as?usize]?=?true;
????????????????????merge?+=?sizes[left?as?usize];
????????????????}
????????????????if?right?>?0?&&?!visited[right?as?usize]?{
????????????????????visited[right?as?usize]?=?true;
????????????????????merge?+=?sizes[right?as?usize];
????????????????}
????????????????ans?=?ans.max(merge);
????????????????visited[up?as?usize]?=?false;
????????????????visited[down?as?usize]?=?false;
????????????????visited[left?as?usize]?=?false;
????????????????visited[right?as?usize]?=?false;
????????????}
????????}
????}
????ans
}

fn?infect(grid:?&mut?Vec<Vec<i32>>,?i:?i32,?j:?i32,?v:?i32,?n:?i32,?m:?i32)?{
????if?i?<?0?||?i?==?n?||?j?<?0?||?j?==?m?||?grid[i?as?usize][j?as?usize]?!=?1?{
????????return;
????}
????grid[i?as?usize][j?as?usize]?=?v;
????infect(grid,?i?-?1,?j,?v,?n,?m);
????infect(grid,?i?+?1,?j,?v,?n,?m);
????infect(grid,?i,?j?-?1,?v,?n,?m);
????infect(grid,?i,?j?+?1,?v,?n,?m);
}


c完整代碼如下：

#include?<stdio.h>
#include?<stdbool.h>
#include?<string.h>
#define?MAX_SIZE?50

void?infect(int?grid[][MAX_SIZE],?int?i,?int?j,?int?v,?int?n,?int?m);
int?largestIsland(int?grid[][MAX_SIZE],?int?n,?int?m);

int?main()?{
????int?grid[][MAX_SIZE]?=?{?{1,?0},?{0,?1}?};
????int?n?=?2;
????int?m?=?2;
????int?ans?=?largestIsland(grid,?n,?m);
????printf("%d\n",?ans);?//?輸出?3
????return?0;
}

int?largestIsland(int?grid[][MAX_SIZE],?int?n,?int?m)?{
????int?id?=?2;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?1)?{
????????????????infect(grid,?i,?j,?id++,?n,?m);
????????????}
????????}
????}
????int?sizes[MAX_SIZE?*?MAX_SIZE];
????memset(sizes,?0,?sizeof(sizes));
????int?ans?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?>?1)?{
????????????????ans?=?ans?>?++sizes[grid[i][j]]???ans?:?sizes[grid[i][j]];
????????????}
????????}
????}
????bool?visited[MAX_SIZE?*?MAX_SIZE]?=?{?false?};
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?0)?{
????????????????int?up?=?i?-?1?>=?0???grid[i?-?1][j]?:?0;
????????????????int?down?=?i?+?1?<?n???grid[i?+?1][j]?:?0;
????????????????int?left?=?j?-?1?>=?0???grid[i][j?-?1]?:?0;
????????????????int?right?=?j?+?1?<?m???grid[i][j?+?1]?:?0;
????????????????int?merge?=?1?+?sizes[up];
????????????????visited[up]?=?true;
????????????????if?(!visited[down])?{
????????????????????merge?+=?sizes[down];
????????????????????visited[down]?=?true;
????????????????}
????????????????if?(!visited[left])?{
????????????????????merge?+=?sizes[left];
????????????????????visited[left]?=?true;
????????????????}
????????????????if?(!visited[right])?{
????????????????????merge?+=?sizes[right];
????????????????????visited[right]?=?true;
????????????????}
????????????????ans?=?ans?>?merge???ans?:?merge;
????????????????visited[up]?=?false;
????????????????visited[down]?=?false;
????????????????visited[left]?=?false;
????????????????visited[right]?=?false;
????????????}
????????}
????}
????return?ans;
}

void?infect(int?grid[][MAX_SIZE],?int?i,?int?j,?int?v,?int?n,?int?m)?{
????if?(i?<?0?||?i?==?n?||?j?<?0?||?j?==?m?||?grid[i][j]?!=?1)?{
????????return;
????}
????grid[i][j]?=?v;
????infect(grid,?i?-?1,?j,?v,?n,?m);
????infect(grid,?i?+?1,?j,?v,?n,?m);
????infect(grid,?i,?j?-?1,?v,?n,?m);
????infect(grid,?i,?j?+?1,?v,?n,?m);
}


c++完整代碼如下：

#include?<iostream>
#include?<cstring>
#define?MAX_SIZE?50

using?namespace?std;

void?infect(int?grid[][MAX_SIZE],?int?i,?int?j,?int?v,?int?n,?int?m);
int?largestIsland(int?grid[][MAX_SIZE],?int?n,?int?m);

int?main()?{
????int?grid[][MAX_SIZE]?=?{?{1,?0},?{0,?1}?};
????int?n?=?2;
????int?m?=?2;
????int?ans?=?largestIsland(grid,?n,?m);
????cout?<<?ans?<<?endl;
????return?0;
}

int?largestIsland(int?grid[][MAX_SIZE],?int?n,?int?m)?{
????int?id?=?2;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?1)?{
????????????????infect(grid,?i,?j,?id++,?n,?m);
????????????}
????????}
????}
????int?sizes[MAX_SIZE?*?MAX_SIZE];
????memset(sizes,?0,?sizeof(sizes));?//?初始化為0
????int?ans?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?>?1)?{
????????????????ans?=?max(ans,?++sizes[grid[i][j]]);
????????????}
????????}
????}
????bool?visited[MAX_SIZE?*?MAX_SIZE]?=?{?false?};?//?初始化為false
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?0)?{
????????????????int?up?=?i?-?1?>=?0???grid[i?-?1][j]?:?0;
????????????????int?down?=?i?+?1?<?n???grid[i?+?1][j]?:?0;
????????????????int?left?=?j?-?1?>=?0???grid[i][j?-?1]?:?0;
????????????????int?right?=?j?+?1?<?m???grid[i][j?+?1]?:?0;
????????????????int?merge?=?1?+?sizes[up];
????????????????visited[up]?=?true;
????????????????if?(!visited[down])?{
????????????????????merge?+=?sizes[down];
????????????????????visited[down]?=?true;
????????????????}
????????????????if?(!visited[left])?{
????????????????????merge?+=?sizes[left];
????????????????????visited[left]?=?true;
????????????????}
????????????????if?(!visited[right])?{
????????????????????merge?+=?sizes[right];
????????????????????visited[right]?=?true;
????????????????}
????????????????ans?=?max(ans,?merge);
????????????????visited[up]?=?false;
????????????????visited[down]?=?false;
????????????????visited[left]?=?false;
????????????????visited[right]?=?false;
????????????}
????????}
????}
????return?ans;
}

void?infect(int?grid[][MAX_SIZE],?int?i,?int?j,?int?v,?int?n,?int?m)?{
????if?(i?<?0?||?i?==?n?||?j?<?0?||?j?==?m?||?grid[i][j]?!=?1)?{
????????return;
????}
????grid[i][j]?=?v;
????infect(grid,?i?-?1,?j,?v,?n,?m);
????infect(grid,?i?+?1,?j,?v,?n,?m);
????infect(grid,?i,?j?-?1,?v,?n,?m);
????infect(grid,?i,?j?+?1,?v,?n,?m);
}


福大大架構(gòu)師每日一題

java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。

496篇原創(chuàng)內(nèi)容

公眾號(hào)