99国产精品欲av蜜臀,可以直接免费观看的AV网站,gogogo高清免费完整版,啊灬啊灬啊灬免费毛片

網(wǎng)易首頁 > 網(wǎng)易號 > 正文 申請入駐

面試官出車禍了,面試要取消了。

0
分享至

專欄:50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄:50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友發(fā)文稱面試被取消了,原因是面試官在路上出車禍了。不知道是真出車禍,還是已經(jīng)找到合適的人不打算招了。如果是不打算招了,說明HR和面試官的關(guān)系很不好,不想招完全可以找個其他借口。我之前也遇到過面試取消的情況,面試的當天HR給出的理由是面試官出差去了,后面再約,結(jié)果直到我重新找到工作入職,也沒見她約。

不過也有可能是真的,不能瞎猜,不知道大家在面試中有沒有遇到取消的情況。






--------------下面是今天的算法題--------------

來看下今天的算法題,這題是LeetCode的第827題:最大人工島。

問題描述

來源:LeetCode第827題

難度:困難

給你一個大小為 n x n 二進制矩陣 grid 。最多只能將一格 0 變成 1 。返回執(zhí)行此操作后,grid 中最大的島嶼面積是多少?島嶼由一組上、下、左、右四個方向相連的 1 形成。

示例1:


輸入: grid = [[1, 0], [0, 1]] 輸出: 3 解釋: 將一格0變成1,最終連通兩個小島得到面積為 3 的島嶼。

示例2:


輸入: grid = [[1, 1], [1, 0]] 輸出: 4 解釋: 將一格0變成1,島嶼的面積擴大為 4。

  • n == grid.length

  • n == grid[i].length

  • 1 <= n <= 500

  • grid[i][j] 為 0 或 1

問題分析

這題說的是最多只能將一個 0 變成 1 ,然后求最大的島嶼面積,和我們之前講的 類似。

我們可以按照之前的方式先計算所有島嶼的面積,然后嘗試把 0 變成 1 ,計算最大面積。因為 0 變成的 1 的時候,兩個本來不相連的島嶼可能會相連,島嶼的面積就會增大,如下圖所示。


所以在計算完島嶼面積之后,需要再遍歷一次二維數(shù)組,如果是 0 ,就嘗試把它變成 1 ,然后把它的上下左右 4 個方向有島嶼的連在一起計算面積。

為了連接的時候防止島嶼有重復(fù),我們需要把每個島嶼編上號,如果號碼是一樣的,說明他們是同一個島嶼,不能連接,如下圖所示,紅色 0 的上下位置是同一個島嶼,不能相加。


JAVA:

// 每一個島嶼的區(qū)域標記為一個不同的數(shù)字 public int largestIsland(int[][] grid) {     int length = grid.length;     Map
         
  mp =  new HashMap<>();      int ans =  0; // 保存最大的島嶼      int landNo =  2; // 島嶼編號從 2 開始      for ( int i =  0; i < length; i++) {          for ( int j =  0; j < length; j++) {              if (grid[i][j] ==  1) {                  int area = dfs(grid, i, j, length, landNo);                 mp.put(landNo++, area); // 保存到map中,島嶼編號也要累加                 ans = Math.max(ans, area);             }         }     }     Set  mySet =  new HashSet<>(); // 去掉重復(fù)的      for ( int i =  0; i < length; i++) {          for ( int j =  0; j < length; j++) {              // 如果遇到0,嘗試把它的上下左右連接起來,保存最大面積。              if (grid[i][j] ==  0) {                  int up = i >  0 ? grid[i -  1][j] :  0;                  int down = i < length -  1 ? grid[i +  1][j] :  0;                  int left = j >  0 ? grid[i][j -  1] :  0;                  int right = j < length -  1 ? grid[i][j +  1] :  0;                  // 上下左右在連接之前肯定是不能相連的,如果是相連的,只能取一個                 mySet.clear();                 mySet.addAll(Arrays.asList(up, down, left, right));                  int tmp =  0;                  for ( int s : mySet) {                      if (s !=  0)                         tmp += mp.get(s);                 }                 ans = Math.max(ans, tmp +  1);             }         }     }      return ans; } // 通過dfs遍歷當前位置的上下左右四個方向 private int dfs(int[][] grid, int i, int j, int length, int landNo) {      // 越界處理      if (i <  0 || i >= length || j <  0 || j >= length || grid[i][j] !=  1)          return  0;      int res =  1;     grid[i][j] = landNo; // 相連的標記為同一個島嶼     res += dfs(grid, i -  1, j, length, landNo); // 上     res += dfs(grid, i +  1, j, length, landNo); // 下     res += dfs(grid, i, j -  1, length, landNo); // 左     res += dfs(grid, i, j +  1, length, landNo); // 右      return res; }

C++:

public:     int largestIsland(vector

 > &grid) {         int length = grid.size();         unordered_map

  mp;         int ans = 0;// 保存最大的島嶼         // 每一個島嶼的區(qū)域標記為一個不同的數(shù)字         int landNo = 2;// 島嶼編號從 2 開始         for (int i = 0; i < length; i++) {             for (int j = 0; j < length; j++) {                 if (grid[i][j] == 1) {                     int area = dfs(grid, i, j, length, landNo);                     mp[landNo++] = area;// 保存到map中,島嶼編號也要累加                     ans = max(ans, area);                 }             }         }         unordered_set

  mySet;// 去掉重復(fù)的         for (int i = 0; i < length; i++) {             for (int j = 0; j < length; j++) {                 // 如果遇到0,嘗試把它的上下左右連接起來,保存最大面積。                 if (grid[i][j] == 0) {                     int up = i > 0 ? grid[i - 1][j] : 0;                     int down = i < length - 1 ? grid[i + 1][j] : 0;                     int left = j > 0 ? grid[i][j - 1] : 0;                     int right = j < length - 1 ? grid[i][j + 1] : 0;                     // 上下左右在連接之前肯定是不能相連的,如果是相連的,只能取一個                     mySet.clear();                     mySet.insert(up);                     mySet.insert(down);                     mySet.insert(left);                     mySet.insert(right);                     int tmp = 0;                     for (int s: mySet) {                         if (s != 0)                             tmp += mp[s];                     }                     ans = max(ans, tmp + 1);                 }             }         }         return ans;     }     // 通過dfs遍歷當前位置的上下左右四個方向     int dfs(vector

 > &grid, int i, int j, int length, int landNo) {         // 越界處理         if (i < 0 || i >= length || j < 0 || j >= length || grid[i][j] != 1)             return 0;         int res = 1;         grid[i][j] = landNo;// 相連的標記為同一個島嶼         res += dfs(grid, i - 1, j, length, landNo);// 上         res += dfs(grid, i + 1, j, length, landNo);// 下         res += dfs(grid, i, j - 1, length, landNo);// 左         res += dfs(grid, i, j + 1, length, landNo);// 右         return res;     }




Python:

def largestIsland(self, grid: List[List[int]]) -> int:     # 通過dfs遍歷當前位置的上下左右四個方向     def dfs(i, j, length, landNo):         # 越界處理         if i < 0 or i >= length or j < 0 or j >= length or grid[i][j] != 1:             return 0         res = 1         grid[i][j] = landNo  # 相連的標記為同一個島嶼         res += dfs(i - 1, j, length, landNo)  # 上         res += dfs(i + 1, j, length, landNo)  # 下         res += dfs(i, j - 1, length, landNo)  # 左         res += dfs(i, j + 1, length, landNo)  # 右         return res     length = len(grid)     mp = {}     ans = 0  # 保存最大的島嶼     landNo = 2  # 島嶼編號從 2 開始     for i in range(length):         for j in range(length):             if grid[i][j] == 1:                 area = dfs(i, j, length, landNo)                 mp[landNo] = area  # 保存到map中,島嶼編號也要累加                 ans = max(ans, area)                 landNo += 1     for i in range(length):         for j in range(length):             # 如果遇到0,嘗試把它的上下左右連接起來,保存最大面積。             if grid[i][j] == 0:                 up = grid[i - 1][j] if i > 0 else 0                 down = grid[i + 1][j] if i < length - 1 else 0                 left = grid[i][j - 1] if j > 0 else 0                 right = grid[i][j + 1] if j < length - 1 else 0                 # 上下左右在連接之前肯定是不能相連的,如果是相連的,只能取一個                 mySet = {up, down, left, right}  # 去掉重復(fù)的                 tmp = 0                 for s in mySet:                     if s != 0:                         tmp += mp[s]                 ans = max(ans, tmp + 1)     return ans

筆者簡介

博哥,真名:王一博,畢業(yè)十多年, 作者,專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解,在全球30多個算法網(wǎng)站中累計做題2000多道,在公眾號中寫算法題解800多題,對算法題有自己獨特的解題思路和解題技巧,喜歡的可以給個關(guān)注,也可以 下載我整理的1000多頁的PDF算法文檔 。

特別聲明:以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布,本平臺僅提供信息存儲服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相關(guān)推薦
熱點推薦
柬埔寨為何這么亂?來看看不為人知的一面

柬埔寨為何這么亂?來看看不為人知的一面

諾言卿史錄
2025-07-16 15:15:36
佛山一區(qū)將“防蚊令”列入村規(guī)民約,情節(jié)嚴重將停發(fā)分紅

佛山一區(qū)將“防蚊令”列入村規(guī)民約,情節(jié)嚴重將停發(fā)分紅

南方都市報
2025-07-25 20:49:15
吃相難看!張碧晨獨占《年輪》,汪蘇瀧攤牌收唱權(quán),騰訊做法亮了

吃相難看!張碧晨獨占《年輪》,汪蘇瀧攤牌收唱權(quán),騰訊做法亮了

銀河史記
2025-07-25 18:19:00
中國首位博物院女院長,一生未婚,跳塔身亡,死前給司機留下紙條

中國首位博物院女院長,一生未婚,跳塔身亡,死前給司機留下紙條

鬼谷子思維
2025-07-24 20:15:03
孫儷兒子“特殊愛好”曝光,網(wǎng)友炸了:你怎么養(yǎng)的娃?

孫儷兒子“特殊愛好”曝光,網(wǎng)友炸了:你怎么養(yǎng)的娃?

聽哲學(xué)
2025-07-25 21:58:05
Slater:勇士對庫明加要價1個年輕潛力球員+1首輪 太陽沒有首輪

Slater:勇士對庫明加要價1個年輕潛力球員+1首輪 太陽沒有首輪

直播吧
2025-07-25 08:58:09
《掃毒風暴》33集大結(jié)局:王輝醒了吳燕萍被抓,沒有第二個內(nèi)鬼

《掃毒風暴》33集大結(jié)局:王輝醒了吳燕萍被抓,沒有第二個內(nèi)鬼

跳跳歷史
2025-07-25 10:37:11
資深球迷張雪峰:沒看過蘇超,我也搶不到蘇超球票!支付寶淘寶紛紛拋出橄欖枝:歡迎張老師來常州隊比賽

資深球迷張雪峰:沒看過蘇超,我也搶不到蘇超球票!支付寶淘寶紛紛拋出橄欖枝:歡迎張老師來常州隊比賽

和訊網(wǎng)
2025-07-25 15:41:28
雨中老人送葬隊現(xiàn)身香港,老戲骨集體淋雨,港劇黃金年代徹底落幕

雨中老人送葬隊現(xiàn)身香港,老戲骨集體淋雨,港劇黃金年代徹底落幕

喜歡歷史的阿繁
2025-07-25 05:38:39
這次49歲的舒淇再次讓世界刮目相看,已是黎明“高攀不起”的存在

這次49歲的舒淇再次讓世界刮目相看,已是黎明“高攀不起”的存在

趣文說娛
2025-07-25 14:36:42
兩局苦戰(zhàn)失利!陳雨菲再負世界第一安洗瑩,無緣中國公開賽四強

兩局苦戰(zhàn)失利!陳雨菲再負世界第一安洗瑩,無緣中國公開賽四強

全景體育V
2025-07-25 19:47:12
女子沒叫公婆爸媽被逼道歉后續(xù)!女子已回娘家,丈夫和婆婆大吵架

女子沒叫公婆爸媽被逼道歉后續(xù)!女子已回娘家,丈夫和婆婆大吵架

清游說娛
2025-05-11 09:44:07
隨著中國籃協(xié)同意楊瀚森不參加本屆亞洲杯,無非就這兩點原因!

隨著中國籃協(xié)同意楊瀚森不參加本屆亞洲杯,無非就這兩點原因!

田先生籃球
2025-07-24 21:57:03
ESPN:新賽季弗拉格在數(shù)據(jù)端未必是最亮眼的新秀,但他所在球隊的戰(zhàn)績會更好

ESPN:新賽季弗拉格在數(shù)據(jù)端未必是最亮眼的新秀,但他所在球隊的戰(zhàn)績會更好

雷速體育
2025-07-25 17:12:40
醍醐灌頂——中國最著名的四篇演講

醍醐灌頂——中國最著名的四篇演講

尚曦讀史
2025-07-17 21:28:51
女籃打的是權(quán)力籃球,輸?shù)貌辉?>
    </a>
        <h3>
      <a href=綠野萍蹤
2025-07-24 09:37:44
廣東宏遠已經(jīng)敲定兩名外援!全部是后衛(wèi),朱芳雨又要重蹈覆轍?

廣東宏遠已經(jīng)敲定兩名外援!全部是后衛(wèi),朱芳雨又要重蹈覆轍?

籃球大陸
2025-07-25 15:55:15
53歲汪峰再次喜當?shù)?個孩子4個媽,前妻葛薈婕:又在繁殖了

53歲汪峰再次喜當?shù)?個孩子4個媽,前妻葛薈婕:又在繁殖了

趙釔是個熱血青年
2025-06-01 05:12:17
貝索斯享約會夜,55歲新妻穿薄紗裙內(nèi)搭空氣,標志大嘴似有新填充

貝索斯享約會夜,55歲新妻穿薄紗裙內(nèi)搭空氣,標志大嘴似有新填充

譯言
2025-07-24 15:33:43
德國和江蘇同為8000多萬人,德國創(chuàng)造4.66萬億GDP,江蘇令人意外

德國和江蘇同為8000多萬人,德國創(chuàng)造4.66萬億GDP,江蘇令人意外

安珈使者啊
2025-07-25 16:21:28
2025-07-26 00:36:50
數(shù)據(jù)結(jié)構(gòu)和算法
數(shù)據(jù)結(jié)構(gòu)和算法
專門介紹和寫算法題解的號
238文章數(shù) 3關(guān)注度
往期回顧 全部

頭條要聞

8旬翁下葬前墓地被人埋死狗沿路埋鐵釘暗器 官方介入

頭條要聞

8旬翁下葬前墓地被人埋死狗沿路埋鐵釘暗器 官方介入

體育要聞

3年過去了,她還是歐洲杯上最酷的姐

娛樂要聞

汪蘇瀧不忍了 !張碧晨痛失《年輪》演唱權(quán)

財經(jīng)要聞

劉煜輝:當下重要不是找確定性而是轉(zhuǎn)折點

科技要聞

36款熱門車高危智駕場景測試,“團滅”!

汽車要聞

李斌一口氣講了近3個小時樂道L90 原因是為啥?

態(tài)度原創(chuàng)

教育
藝術(shù)
游戲
親子
軍事航空

教育要聞

389分撿漏鄭大,367分讀華水,河南考生咋沒這個命

藝術(shù)要聞

故宮珍藏的墨跡《十七帖》,比拓本更精良,這才是地道的魏晉寫法

育碧下一款《幽靈行動》將改用虛幻5 重返系列本源

親子要聞

爸爸被娃嫌,被狗嫌,被我嫌都是自找的

軍事要聞

吳謙少將任中國駐埃及使館國防武官

無障礙瀏覽 進入關(guān)懷版 主站蜘蛛池模板: 巴彦县| 新巴尔虎左旗| 双牌县| 资阳市| 沧州市| 鄂托克前旗| 上虞市| 车致| 北票市| 化德县| 清涧县| 嵩明县| 西乌| 南陵县| 杭州市| 新密市| 娄烦县| 秭归县| 江山市| 休宁县| 扬州市| 盘山县| 交口县| 逊克县| 洛川县| 灵璧县| 博爱县| 儋州市| 新闻| 冕宁县| 华蓥市| 隆安县| 嘉祥县| 博白县| 扎赉特旗| 大田县| 古浪县| 东海县| 化德县| 都安| 朝阳区|