首页 > 代码库 > 算法:几个重要函数应用于一个题目

算法:几个重要函数应用于一个题目

今天欣赏一个包含众多知识点的解法。题目是这样的:

给定两个字符串s1和s2,统计它们各自包含的各个小写字母的个数,然后互相比较。如果对某个字母,s1中出现的次数多,就打印“1:aaaa” (表示字母a在s1中出现了4次);如果s2中出现的次数多,就打印“2:aaaa”;如果次数相同,就打印“=:aaaa”。最后输出整个的比较结果,输出时先按次数排序,再按1-2-=排序,最后按字母排序。

举个例子:

s1 = "my&friend&Paul has heavy hats! &"

s2 = "my friend John has many many friends &"

mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss/1:l/1:t/1:u/1:v/2:o"

分析:

这个题目其实挺简单的。统计字母个数?遍历+字典轻松搞定。比较两个字典?逐个即可。最后输出的先按...排序,再按...排序,最后按...排序?有点麻烦,不过用itemgetter也可以做到。

本人参考两种解法,并比较两种解法的性能:

技术分享
 1 #-*- coding:utf-8 -*-
 2 __author__ = Administrator
 3 
 4 from collections import Counter
 5 import re
 6 import time
 7 #s1 = "my&friend&Paul has heavy hats! &"
 8 #s2 = "my friend John has many many friends &"
 9 #str_mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss/1:l/1:t/1:u/1:v/2:o"
10 def str_min(s1,s2):
11     c1=Counter(s1)
12     c2=Counter(s2)
13     d=[]
14     key1=c1.keys();
15     key2=c2.keys();
16 
17     for key in set(list(key1)+list(key2)):
18         if re.match("[a-z]",key):
19             if c1[key]>c2[key]:
20                 d.append(("1",key,c1[key]))
21             elif c1[key]<c2[key]:
22                 d.append(("2",key,c2[key]))
23             else:
24                 d.append(("=",key,c1[key]))
25 
26     rec=["{0}:{1}".format(v,s*n) for v,s,n in d]
27     return rec
28 
29 def str_min2(s1,s2):
30     c1=Counter(filter(str.islower,s1))
31     c2=Counter(filter(str.islower,s2))
32     d=[]
33     for key in set(list(c1.keys())+list(c2.keys())):
34         n1=c1.get(key,0)
35         n2=c2.get(key,0)
36         if n1>0 or n2>0:
37             if n1>n2:
38                 d.append(("1",key,n1))
39             elif n1<n2:
40                 d.append(("2",key,n2))
41             else:
42                 d.append(("=",key,n1))
43     rec=["{}:{}".format(v,s*n) for v,s,n in d]
44     return rec
45 
46 if __name__=="__main__":
47     s1 = "my&friend&Paul has heavy hats! &"
48     s2 = "my friend John has many many friends &"
49     t0=time.time()
50     for i in range(100000):
51          rec=str_min(s1,s2)
52     print(/.join(sorted(rec,key=lambda s:(-len(s),s))))
53     t1=time.time()-t0
54     print(t1)
55     print("-"*100)
56     t0=time.time()
57     for i in range(100000):
58          rec=str_min2(s1,s2)
59     print(/.join(sorted(rec,key=lambda s:(-len(s),s))))
60     t1=time.time()-t0
61     print(t1)
62     
63     
View Code

输出:

2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss/1:l/1:t/1:u/1:v/2:o
14.07480502128601
----------------------------------------------------------------------------------------------------
2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss/1:l/1:t/1:u/1:v/2:o
8.899508953094482

 

算法:几个重要函数应用于一个题目