• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode827.最大人工岛|MakingALargeIsland

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10569639.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4. 

Notes:

  • 1 <= grid.length = grid[0].length <= 50.
  • 0 <= grid[i][j] <= 1.

在二维地图上, 0代表海洋, 1代表陆地,我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后,地图上最大的岛屿面积是多少?(上、下、左、右四个方向相连的 1 可形成岛屿)

示例 1:

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

示例 2:

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

示例 3:

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

说明:

  • 1 <= grid.length = grid[0].length <= 50
  • 0 <= grid[i][j] <= 1

Runtime: 104 ms
Memory Usage: 19.9 MB
 1 class Solution {
 2     var N:Int = 0
 3     func largestIsland(_ grid: [[Int]]) -> Int {
 4         var grid = grid
 5         N = grid.count
 6         var index:Int = 3
 7         var res:Int = 0
 8         var area:[Int:Int] = [Int:Int]()
 9         for x in 0..<N
10         {
11             for y in 0..<N
12             {
13                 if grid[x][y] == 1
14                 {
15                     area[index] = dfs(&grid, x, y, index)
16                     res = max(res, area[index,default:0])
17                     index += 1
18                 }
19             }
20         }
21         for x in 0..<N
22         {
23             for y in 0..<N
24             {
25                 if grid[x][y] == 0
26                 {
27                     var seen:Set<Int> = Set<Int>()
28                     var cur:Int = 1
29                     for (key,val) in move(x, y)
30                     {
31                         index = grid[key][val]
32                         if index > 1 && !seen.contains(index)
33                         {
34                             seen.insert(index)
35                             cur += area[index,default:0]
36                         }
37                     }
38                     res = max(res, cur)
39                 }
40             }
41         }
42         return res
43     }
44     
45     func move(_ x:Int,_ y:Int) -> [(Int,Int)]
46     {
47         var res:[(Int,Int)] = [(Int,Int)]()
48         if valid(x, y + 1) {res.append((x, y + 1))}
49         if valid(x, y - 1) {res.append((x, y - 1))}
50         if valid(x + 1, y) {res.append((x + 1, y))}
51         if valid(x - 1, y) {res.append((x - 1, y))}
52         return res        
53     }
54     
55     func valid(_ x:Int,_ y:Int) -> Bool
56     {
57         return 0 <= x && x < N && 0 <= y && y < N
58     }
59     
60     func dfs(_ grid:inout [[Int]],_ x:Int,_ y:Int,_ index:Int) -> Int
61     {
62         var area:Int = 0
63         grid[x][y] = index
64         for (key,val) in move(x, y)
65         {
66             if grid[key][val] == 1
67             {
68                 area += dfs(&grid, key, val, index) 
69             }
70         }
71         return area + 1
72     }
73 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
为mac编写swift脚本发布时间:2022-07-13
下一篇:
[Swift]LeetCode752.打开转盘锁|OpentheLock发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap