python笔试题110题Python笔试题一维二维python笔试题 内存10m
下载地址 https://share.weiyun.com/gcOeOitM
资料目录
100道Python面试题
5个等待挑战的Python面试题（附答案）
python基础面试题三十一道（附详细答案）
python面试基础题十大陷阱（附详细答案）
python面试真实笔试题带答案（1-10题）
Python面试中必看的8个必考问题（附详细答案）
Python爬虫开发面试常见问题（附详细答案）
Python爬虫面试题（附详细答案）
python数据分析师面试题选（附详细答案）
Python数据挖掘试题四十道（附答案）
阿里巴巴Python开发工程师面试题（附答案）
常见的25个python面试问答（附详细答案）
Python经典面试题和答案解析
四类必须提前准备的Python程序员面试问题
出现频率最高的python面试题集锦（附详细答案）
珍藏版Python web后端开发工程师面试试题
尚观python第一阶段考试（面试真题模拟）
老男孩Python全栈7期练习题（面试真题模拟）
傲梦python笔试题及答案
python 笔试题（附带答案）
Python题库(已收录100道真题）
python第一阶段考试题
python基础试题(含答案)
PYTHON测试题和答案
Python考试题复习知识点试卷试题
python期末考试复习试卷
举例 接雨水
题目要求
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
思路分析
思考才是最重要的
这个题目非常好的诠释了一句话----“技术，只是实现目标的方式和手段”。
很多人面对问题时，总是有一种较劲脑汁写算法的冲动，还有人，以为每一种问题都有一个成熟的解决方案，似乎接触过这个方案并记忆下来，今后再遇到时就可以迎刃而解了。殊不知，编程是一个创造性的思考过程，很多人不愿意思考，更喜欢走马观花般的背答案。短时间内的确可以提升算法能力，但长期来看，你的逻辑能力才是解决问题的根本，思考才是第一位的。
两个基本判断
我们先不去想怎么写算法，而是先分析，抽丝剥茧的对这个问题进行分析。
首先，最左侧的柱子和最右侧的柱子上面不可能存储雨水，这个判断很简单，不做讨论。
其次，每个柱子上能存储多少水，取决于它左右两侧最高柱子的高度，以索引为5的柱子为例，这个柱子的高度是0，它左侧最高的柱子是索引为3的柱子，高度为2， 它右侧最高的柱子是索引为7的柱子，高度为3，这两个柱子的高度决定了，索引为5的柱子上面可以存储水2个单位。
算法思路
经过上面的两点分析，解题的思路就非常清晰了。
遍历数组，计算每个柱子左右两侧的最高柱子的高度，这两个高度中选最小的，如果这个最小高度大于当前柱子的高度，那么差值就是当前这个柱子能够存储的水的量。
由于遍历的过程是从左向右，因此，左侧最高柱子的高度可以用一个变量保存起来，而右侧最高柱子的高度则需要每次都去计算,但是经过一次寻找后，这个最高柱子的位置就确定了，假设位置为K，对于这个柱子左侧的所有柱子来说，他们右侧的最高柱子都是固定的，因此，也可以存储起来，直到遍历过程中当前柱子的索引大于等于K，则需要重新寻找。
实例代码
def trap(lst):
left_height = 0
right_index = 0
rain = 0
for index, item in enumerate(lst):
# 第一个和最后一个不用考虑，因为柱子上方无法存储水
if index == len(lst) - 1 or index == 0:
left_height = item
continue
# 如果左侧最高为0或者和当前高度相同，当前这个柱子的上方无法存储水
if left_height == 0 or left_height == item:
left_height = item
continue
# 获取右侧最高的柱子高度， 取左右两侧较矮的，如果当前柱子高度小于它，则可以存储水
if index >= right_index:
right_index, right_heigth = find_right_heigth(index, lst)
min_heigth = min([left_height, right_heigth])
if min_heigth > item:
rain += min_heigth - item
# 更新左侧最高柱子的高度
if item > left_height:
left_height = item
return rain
def find_right_heigth(index, lst):
"""
返回index右侧最高柱子的位置和高度
:param index:
:param lst:
:return:
"""
right_heigth = 0
right_index = index
for i in range(index, len(lst)):
if lst[i] > right_heigth:
right_index = i
right_heigth = lst[i]
return right_index, right_heigth
if __name__ == '__main__':
lst = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(lst))
|