上海网站制作与推广,没经验的人开什么店好,wordpress 可以干嘛,广东网站备案谷歌历年面试真题——数组和字符串系列真题练习。
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;…谷歌历年面试真题——数组和字符串系列真题练习。
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 1 输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2 输入height [4,2,0,3,2,5] 输出9 提示 n height.length1 n 2 * 1040 height[i] 105 思路一双指针
这个问题可以使用双指针的方法来解决。具体步骤如下
初始化左右指针 left 和 right分别指向数组的第一个和最后一个元素。初始化两个变量 left_max 和 right_max分别表示左侧柱子的最大高度和右侧柱子的最大高度初始值都为0。使用循环遍历数组当 left 指针小于等于 right 指针时执行以下步骤 如果 height[left] height[right]表示左侧柱子较低则计算当前位置的雨水量并更新左侧最大高度 left_max。否则表示右侧柱子较低则计算当前位置的雨水量并更新右侧最大高度 right_max。在计算雨水量时当前位置能够接的雨水量等于当前最小高度left_max和right_max中的较小值与当前柱子高度之差。 返回计算得到的总雨水量。
下面是相应的Python代码实现
def trap(height):if not height:return 0left, right 0, len(height) - 1left_max, right_max 0, 0ans 0while left right:if height[left] height[right]:if height[left] left_max:left_max height[left]else:ans left_max - height[left]left 1else:if height[right] right_max:right_max height[right]else:ans right_max - height[right]right - 1return ans# 示例 1
height1 [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出6# 示例 2
height2 [4,2,0,3,2,5]
print(trap(height2)) # 输出9这个函数使用双指针的方法通过一次遍历就可以计算出雨水的总量。
思路二栈
除了双指针的方法外还可以使用栈来解决这个问题。具体步骤如下
初始化一个栈 stack 和一个变量 ansans 用于记录接到的雨水量初始值为0。遍历数组 height 中的每一个柱子依次执行以下操作 如果栈为空或当前柱子高度小于等于栈顶柱子高度则将当前柱子下标入栈。否则说明当前柱子可能会形成一个水池将栈中元素逐个弹出直到遇到柱子高度大于当前柱子高度的位置。每次弹出时都计算当前柱子和栈顶柱子之间的距离并根据距离和高度差计算雨水量然后累加到 ans 中。最后将当前柱子下标入栈。 遍历完成后返回 ans 即为最终的雨水量。
下面是相应的 Python 代码实现
def trap(height):stack []ans 0for i in range(len(height)):while stack and height[i] height[stack[-1]]:top stack.pop()if not stack:breakdistance i - stack[-1] - 1bounded_height min(height[i], height[stack[-1]]) - height[top]ans distance * bounded_heightstack.append(i)return ans# 示例 1
height1 [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出6# 示例 2
height2 [4,2,0,3,2,5]
print(trap(height2)) # 输出9这个函数使用栈的方法通过一次遍历就可以计算出雨水的总量。
思路三动态规划
除了双指针和栈的方法外还可以使用动态规划来解决这个问题。具体步骤如下
初始化两个数组 left_max 和 right_max分别用于存储每个柱子左侧和右侧的最大高度。 left_max[i] 表示第 i 个柱子左侧包括自身的最大高度。right_max[i] 表示第 i 个柱子右侧包括自身的最大高度。 遍历数组 height从左向右更新 left_max从右向左更新 right_max。遍历数组 height对于每个柱子计算该位置上可以接到的雨水量即 min(left_max[i], right_max[i]) - height[i]。累加所有位置上的雨水量即为最终的雨水总量。
下面是相应的 Python 代码实现
def trap(height):n len(height)if n 0:return 0left_max [0] * nright_max [0] * n# 初始化 left_maxleft_max[0] height[0]for i in range(1, n):left_max[i] max(left_max[i - 1], height[i])# 初始化 right_maxright_max[n - 1] height[n - 1]for i in range(n - 2, -1, -1):right_max[i] max(right_max[i 1], height[i])# 计算雨水量ans 0for i in range(n):ans min(left_max[i], right_max[i]) - height[i]return ans# 示例 1
height1 [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1)) # 输出6# 示例 2
height2 [4,2,0,3,2,5]
print(trap(height2)) # 输出9这个函数使用动态规划的方法通过三次遍历就可以计算出雨水的总量。
