• 售前

  • 售后

热门帖子
入门百科

【Leetcode刷题】q42-接雨水标题

[复制链接]
狭缝求生室 显示全部楼层 发表于 2022-1-16 00:25:36 |阅读模式 打印 上一主题 下一主题
标题


本题具体要求见Leetcode-q42
解题思绪

起首看一下结果,固然是随机性比力高,但是团体来说,我们的这个解法速率照旧可以的:

这个题的解法title是基于双指针法的解法,重要缘故起因是双指针法并不是标题的最难点。
这道题的重要解法很简单:既然要接雨水,那么就要把整个数组分成几个小坑,每个小坑都由数值比力高的边界(edge)构成,这种edge的判定很简单,那就是左右双方的值都不比它大,那它就是边界了。
按照这种方式,用双指针法可以很快地分出各个小坑,但是如许会带来三个标题:

  • 怎样盘算雨水的数目?
  • 如果标题1用一边遍历一边盘算的方法算,那么它的焦点假设是,这个坑的左边界不大于右边界,如许才气顺着算下去,但是单纯判定edge并不可以大概确保这个假设,怎样确保这个假设对每个小坑创建?
  • 对于标题2,我们可以进一步遍历,获取strong-edge,如果遍历到反面有比左边界更大的edge,则给strong-edge的flag标志为True,然后可以直接盘算结果,但是如果遍历到末了都没有比左边界更大的edge,这时间怎么盘算?
对于标题3,我终极的解法是,把这个子坑逆转一下,送进算法再来一遍,如许的话,就可以完善办理这个标题了,而且这种子坑通常只会有一个,因此运算复杂度也不算很高,顶多就是2*n,照旧在O(n)的范畴。
代码

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         return trap1(height)
  4. def trap_edge(height: list, ind: int) -> bool:
  5.         if ind >= len(height):
  6.                 return False
  7.         left = 0 if ind == 0 else height[ind - 1]
  8.         right = 0 if ind == len(height) - 1 else height[ind + 1]
  9.         if height[ind] >= left and height[ind] >= right:
  10.                 return True
  11.         else:
  12.                 return False
  13. def trap1(height: list) -> int:
  14.         fast = 0
  15.         rain_total = 0
  16.         while(fast < len(height)):
  17.                 if trap_edge(height, fast):
  18.                         slow = fast
  19.                         # print(slow)
  20.                         rain_trap_total = 0
  21.                         fast += 1
  22.                         get_edge = False
  23.                         while(fast < len(height)):
  24.                                 if not trap_edge(height, fast):
  25.                                         rain_trap_total += max(0, height[slow] - height[fast])
  26.                                         fast += 1
  27.                                 else:
  28.                                         get_edge = True
  29.                                         if height[fast] < height[slow]:
  30.                                                 rain_trap_total += max(0, height[slow] - height[fast])
  31.                                                 strong_right = False
  32.                                                 right_edge = fast
  33.                                                 fast += 1
  34.                                         else:
  35.                                                 strong_right = True
  36.                                                 break
  37.                         if get_edge and (not strong_right):
  38.                                 sub_height = height[slow:(right_edge+1)]
  39.                                 sub_height.reverse()
  40.                                 rain_trap_total = trap1(sub_height)
  41.                         if get_edge:
  42.                                 rain_total += rain_trap_total
  43.                         if fast == len(height):
  44.                                 break
  45.                 else:
  46.                         fast += 1
  47.         return rain_total
复制代码
然而看完官方解法之后,感觉猛拍大腿啊。。。是本身对标题的分析不敷透彻,一眼就想到分成各个小坑,然后就沿着小坑的思绪去做了,实际上,一个点上能承载多少雨水,跟它所处的“坑”确实有关,但是跟坑里的别的点是无关的,只和坑的边界有关,也就是这个点左边和右边的最大高度,只要算出一个点左边和右边的最大高度,就可以算出它可以大概承载多少雨水了!
如许一建模,这个标题就比我们如今的解法更加清晰清朗了。讲讲区别:
我们的做法:把整个“构筑物”分成各个小坑,然后根据划出来的小坑来盘算每个点的雨水的量,但是小坑会被大坑包罗,这就导致了轻易出现标题,须要更多的判定和分析(也就是strong-right)那一步;
精确的做法:起首将这个标题要解的东西界说清晰,定!义!清!楚!这很告急,界说该点上的雨水值就是左边和右边的最大值的最小值减去该点的高度,那么标题就很好解了啊。
动态规划法:直接从左往右、从右往左得到各个点对应的左最大和右最大,然后盘算一把,完事;
双指针法:left=0,right=len-1,一个往右,一个往左,每一步都要更新一个左最大和一个右最大,当左最巨细于右最大的时间,由于left右边的最大值肯定大于便是现在的右最大,以是left上的雨水值就是左最大减去当前高度,然后left就可以更新了,right也是一样的,妙!双指针真是永世滴神!
双指针法的代码:
[code]class Solution:        def trap(self, height: List[int]) -> int:                if len(height)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作