每日一题 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()是从左端。


相关文章
|
1月前
|
机器学习/深度学习 数据采集 自然语言处理
【2023 - 探索】博0到博1,游戏新地图的探索日志
【2023 - 探索】博0到博1,游戏新地图的探索日志
43 0
|
1月前
|
定位技术
leetcode-1765:地图中的最高点
leetcode-1765:地图中的最高点
24 0
|
2天前
|
前端开发 JavaScript 算法
程序技术好文:高德地图经纬度坐标拾取工具
程序技术好文:高德地图经纬度坐标拾取工具
|
1月前
|
算法
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
26 3
|
1月前
每日一题!如约而至!(图片整理,寻找数组的中心下标)
每日一题!如约而至!(图片整理,寻找数组的中心下标)
19 0
|
10月前
|
定位技术
LeetCode-1765 地图中的最高点
LeetCode-1765 地图中的最高点
|
1月前
代码随想录Day51 完结篇 LeetCode T84 柱状图的最大矩形
代码随想录Day51 完结篇 LeetCode T84 柱状图的最大矩形
25 0
|
前端开发 定位技术 Python
使用brython做个迷宫游戏-2:制作地图
使用brython做个迷宫游戏-2:制作地图
108 1
|
11月前
|
定位技术
高德地图进阶开发实战案例(5):矩形可视范围的东北西南角经纬度的获取
高德地图进阶开发实战案例(5):矩形可视范围的东北西南角经纬度的获取
97 0
|
11月前
|
定位技术 API
高德地图进阶开发实战案例(2):电子围栏(多边形的绘制)的展示
高德地图进阶开发实战案例(2):电子围栏(多边形的绘制)的展示
422 0