LeetCode攀登之旅(7)
LeetCode攀登之旅(7)
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.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号算法系列！