每日一题 1765. 地图中的最高点

简介: 每日一题 1765. 地图中的最高点

题:求二维地图上可能存在的最高点的高度。即在地图上给出水域,求对空白区域填充陆地的方法。

输入m*n的二维数组isWater,表示该位置是否为水域。1是0否。

求高度时,水域高度为0。且相邻陆地高度差最多为1。

解:

参考题解。广度优先BFS,从水域开始,填充相邻且未被设置的格子。

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[water-1 for water in row] for row in isWater] #初始化,将水域高度设置为0.陆地初始化-1
        q = deque((i,j) for i, row in enumerate(isWater) for j,water in enumerate(row) if water)#水域入队
        while q:
            i, j = q.popleft()
            for x,y in ((i-1,j),(i+1, j), (i, j-1), (i, j+1)):
                if 0<=x<m and 0<=y<n and ans[x][y] == -1:
                    ans[x][y] = ans[i][j] +1
                    q.append((x,y))
        return ans
 

补充:

1.Python中比较运算可以任意串连;例如,x < y <= z 等价于 x < y and y <= z。

2.deque 双向队列,添加或弹出元素都可以是双向的。

collections --- 容器数据类型 — Python 3.10.2 文档


append(), pop()是从右端。

appendleft(), popleft()是从左端。


相关文章
|
7月前
|
定位技术
leetcode-1765:地图中的最高点
leetcode-1765:地图中的最高点
40 0
|
6月前
|
程序员 定位技术
程序员必知:地图坐标转换器
程序员必知:地图坐标转换器
49 0
|
定位技术
LeetCode-1765 地图中的最高点
LeetCode-1765 地图中的最高点
|
程序员 定位技术 容器
ChatGPT工作提效之使用百度地图在首都为六一儿童节献爱心(多边形覆盖物、文本标注、自动获取经纬度、爱心函数)
ChatGPT工作提效之使用百度地图在首都为六一儿童节献爱心(多边形覆盖物、文本标注、自动获取经纬度、爱心函数)
128 0
|
数据可视化
好玩的DEM制图:等高线地形图入门与进阶
好玩的DEM制图:等高线地形图入门与进阶
108 0
|
数据采集 运维 NoSQL
数据地图?地图数据?傻傻分不清楚!
数据地图?地图数据?傻傻分不清楚!

热门文章

最新文章