python题目答案及分析python题目练习蓝桥杯c和Python题目一样吗
下载地址 https://share.weiyun.com/OvviwGnZ
资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题）
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题，涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全（附答案解析）
老男孩Python全栈7期练习题（面试真题模拟）
尚观python第一阶段考试（面试真题模拟）
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践（慕课版）郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)
举例 最小区间(超出时间限制)
题目要求
已知k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中
示例：
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
思路分析
列表里有K个元素，这些元素都是列表，下面的分析中，把这K个列表称之为小列表，外层的存储小列表的称之为大列表（big_lst）。题目要求找到一个最小的区间，是的这k个列表中的每个列表至少有一个数包含其中。
我们先随便定义一个区间，比如说[9, 18], 怎么判断这k个列表里每个列表都有元素包含其中呢？这需要遍历每一个列表，列表里的元素只要有一个在9到18之间就可以了。可是这样的遍历好麻烦，因为列表有多个，何不考虑把这k个列表合并成一个呢，这样就只有一个列表存在，寻找区间就不需要对每个列表都检查了。
但是合并区间带来一个新的问题，合并以后，对于一个数，你不知道这个数来自于哪个列表，因此，合并的过程，需要记录每一个数都在哪个列表中出现过，可以使用一个字典（index_dict），用数值做key,value设置为set，存入小列表在大列表中的索引。
经过上面两步分析，可以得到一个合并后的列表，且知道列表中的每个数在哪个小列表中出现过。
接下来就是寻找区间，还是老办法，考虑极值或边界情况，假设合并列表的第一个元素（item）就是最小区间开始的位置，那么只要解决结束位置就好了，要记住，每个元素曾经在哪个小列表中出现过是有记录的，此时可以查看第一个元素在小列表中出现的情况，如果len(index_dict[item]) 和 len(big_lst)相等，就可以证明，item在每个小列表中都出现过。这样最小区间就是[item, item]。
如果len(index_dict[item]) 和 len(big_lst) 不相等，就看item的下一个元素（next），看它有没有可能是最小区间结束的位置，方法也很简单，把index_dict[item] 和 index_dict[next]做union操作，假设结果为index_set，只要len(index_set) == len(big_lst),那么next就是最小区间结束的位置。如果len(index_set) != len(big_lst)呢，没关系，继续查看下一个，不停的执行index_set = index_dict[item].union(index_dict[next]), 一旦len(index_set) == len(big_lst) 成立，就找到了最小区间的结束位置。
前面的分析，是建立在合并列表的第一个元素是最小区间的起始元素的基础上，依靠这个边界条件，理清的思路，接下来要推广到合并列表的每一个元素，遍历合并列表，并假设当前遍历到的元素就是最小区间的起始元素，然后寻找最小区间结束的元素。
示例代码
# coding=utf-8
def get_small_range(lst):
index_dict = {} # 记录每一个数在哪个列表中出现过
merge_lst = [] # 把所有序列合并到一起
for index, item in enumerate(lst):
for number in item:
index_dict.setdefault(number, set([]))
index_dict[number].add(index)
merge_lst.extend(item)
# 合并以后要排序
merge_lst.sort()
small_range = None
small_range_lst = []
for index, item in enumerate(merge_lst):
# 获得item 都在哪些列表里出现
index_set = index_dict[item]
if len(index_set) == len(lst):
# 如果item在所有列表里都出现过,直接返回
return [item, item]
else:
# 把item作为区间开始的位置,下面的for循环去寻找区间结束的位置
for i in range(index+1, len(merge_lst)):
next = merge_lst[i]
index_set = index_set.union(index_dict[next])
# 从item 到 next, 这个范围内每个列表至少有一个元素包含其中
if len(index_set) == len(lst):
# 记录范围最小的区间
if small_range is None or small_range > next - item:
small_range = next - item
small_range_lst = [item, next]
break
return small_range_lst
if __name__ == '__main__':
lst = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
print(get_small_range(lst))
|