当前位置 : 主页 > 手机开发 > 其它 >

[Swift]LeetCode1162. 地图分析 | As Far from Land as Possible

来源:互联网 收集:自由互联 发布时间:2021-06-11
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ?微信公众号:为敢(WeiGanTechnologies) ?博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/)

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

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

分享图片

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2 Explanation: The cell (1, 1) is as far as possible from all the land with distance 2. 

Example 2:

分享图片

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4 Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] is 0 or 1

你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋,请返回 -1

示例 1:

分享图片

输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释: 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。

示例 2:

分享图片

输入:[[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释: 
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

提示:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 不是 0 就是 1

Runtime: 828 ms Memory Usage: 21 MB
 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var s:[Int:Int] = [Int:Int]()
16     func maxLevelSum(_ root: TreeNode?) -> Int {
17         dfs(root,1)
18         var best:Int = s[1,default:0]
19         var v:Int = 1
20         for (key,val) in s
21         {
22             if val > best
23             {
24                 best = val
25                 v = key
26             }            
27         }
28         return v
29     }
30     
31     func dfs(_ root: TreeNode?,_ level:Int)
32     {
33         if root == nil {return}
34         dfs(root!.left, level + 1)
35         dfs(root!.right, level + 1)
36         s[level,default:0] += root!.val
37     }
38 }
网友评论