LeetCode攀登之旅(7)
- 2019 年 10 月 6 日
- 筆記
LeetCode攀登之旅(7)
0.说在前面
1.最长公共前缀
2.实现
3.zip与map
4.作者的话
0.说在前面
本节主要刷的题是最长公共前缀，同时借助本题，来讲一下python高级用法，zip与map。
1.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"] 输出: "fl"
示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
2.实现
【优良算法】
算法思想：
当list为空或者第一个字符串为空，直接返回空字符串；
如果list只有一个字符串，直接返回即可。
剩余情况下面对比实现，选出列表中最小的字符串，设长度为min_length，list长度为s_len，那么我们只要循环min_legth的长度，然后在内层嵌套s_len长度的循环，通过s_len的长度，检测list中所有字符串相同位置的字符是否一致，这里检测方法是，所有的字符与最后一个字符相比，只要检测到不一致，直接退出程序，返回结果。
class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ s_len = len(strs) if s_len==0 or strs[0]=="": return "" if s_len==1: return strs[0] # 找出最小的字符串长度 min_lenght = len(min(strs,key=len)) print(min_lenght) # 定义公共前缀长度 t=0 # 最小长度循环 for i in range(min_lenght): count = 0 # 最后一个数与前面所有的数的第i位相比较 for j in range(s_len): if strs[j][i]!=strs[s_len-1][i]: break count+=1 # 判断当前i是否有公共字符，如果有公共字符，此时的count==s_len，否则就小于s_len if count<s_len: break t += 1 return strs[0][:t]
解法一图
【优秀算法】
算法思想
strs=["flower","flow","flight"]
通过zip(*strs)将上述list分解为下面的元组，然后通过for循环，迭代取值，取出每个元组，并通过set将每个元组进行合并，我们知道set中不会出现相同的数，也就是三个字符直接合并后为1个，则表示为相同字符，否则不相同，直接退出循环即可。
('f', 'f', 'f') ('l', 'l', 'l') ('o', 'o', 'i') ...............
实现
# 这个代码参考自https://blog.csdn.net/qq_34364995/article/details/80274107 class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if len(strs) == 0: return "" count = 0 for i in zip(*strs): print(i) if len(set(i)) == 1: count += 1 else: return strs[0][:count] return strs[0][:count] s = Solution() str = ["flower","flow","flight"] t = s.longestCommonPrefix(str) print(t)
解法二图
3.zip与map
【zip】
zip(seq[, seq, ...])
zip函数会对每个seq对象依次取相同index的值到一个tuple中，然后返回一个由这些tuple组成l可迭代对象。
tuple的数量根据seq中具有最少的索引的seq决定，多余的便不再继续操作。
l1 = [10,20,31,4] l2 = [[53,47],[19,37]] a,b = zip(l1,l2) print(a,b) print("---循环取出---") for i in zip(l1,l2): print(i)
(10, [53, 47]) (20, [19, 37]) ---循环取出--- (10, [53, 47]) (20, [19, 37])
zip(*)
是一个zip的逆操作,操作对象必须是多维的且可迭代。还原回去的是元组形式！
比如我们想把上面zip后的结果给还原回去
l1,l2=zip(*zip(l1,l2)); print(l1,l2) print(list(l1),list(l2))
(10, 20) ([53, 47], [19, 37]) [10, 20] [[53, 47], [19, 37]]
【map】
map(function, iterable, ...)
第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。
将第二个参数（一般是数组）中的每一个项，处理为第一个参数的类型
例子1：设置类型
for i in map(str,[1,2]): print(i) print(type(i))
1 <class 'str'> 2 <class 'str'>
例子2：function使用
当然函数也可以自己定义或者用lambda
for i in map(lambda x: x+1, range(3)): print(i) a,b,c = map(lambda x: x+1, range(3)) print(a,b,c)
1 2 3 1 2 3
【zip与map结合】 再来个精彩的例子！ 排序！ 下面实现按字典value排序 关键点说明：
di.items包含了key与value,后面的key参数表示按照哪一个排序，0表示key，1表示value，reverse默认为False，从小到大，当为Ture，表示从高到低排序，zip(*)的目的是分解key与value，然后将后面处理的结果处理为list类型，返回出来即可，如果前面不是k,v，则要通过循环取出！
from operator import itemgetter di={'word1':22, 'word2':45, 'word3':66} k,v=map(list, zip(*sorted(di.items(), key=itemgetter(1), reverse=True))) print(k,v)
['word3', 'word2', 'word1'] [66, 45, 22]
4.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号算法系列！
