目录

一、思路总结

二、B站地址

三、相关书籍

四、《程序员代码面试指南》Python实现

 

一、思路总结

学习其刷题习惯和思考思路

1. 案例一：水王数问题

 1 # coding:utf-8
 2 """
 3 输入：一个列表，如果列表中有一个数出现的频率超过总个数的一半，则称其为水王
 4 输出：水王数，如果没有则返回-1
 5 要求：时间复杂度O(n),空间复杂度O(1)
 6 例如：[3,2,1,2,3,3,3,4,3,3]，返回 3
 7 思路：每次从列表中取两个不同的数删掉，
 8     1）如果没有数剩下，则没有水王，返回-1
 9     2）最后留下来一个数，判断其在列表中出现的频率是否超过总数一半，是则为水王，否则没有水王，返回-1
10 引申：总统选举问题，每次两张选票对比是否相同，候选人票数超过一半则选举有效，再通过比对频率找到总统
11 """
12 class Solution :
13     def findShuiKing(self, alist) :
14         if len(alist) == 0 :
15             return -1
16         #候选人
17         candicate = 0
18         #血量，血量为0则无候选人，血量大于0则有候选人
19         HP = 0
20         for i in range(len(alist)) :
21             #如果无候选人，则把当前数立为候选人，HP赋值为1
22             if HP == 0 :
23                 candicate = alist[i]
24                 HP = 1
25             #如果有候选人且候选人和当前数不等，则HP -1
26             elif alist[i] != candicate :
27                 HP -= 1
28             #如果有候选人且候选人和当前数相等，则HP +1
29             else :
30                 HP += 1
31         #如果最终的血量为0，则没有候选人
32         if HP == 0 :
33             return -1
34         #如果最终有候选人，判断候选人出现的频率，超过一半则就是水王，否则不存在水王
35         if alist.count(candicate) > len(alist) // 2 :
36             return candicate
37         else :
38             return -1
39 
40 s = Solution()
41 alist = [3,2,1,2,3,3,3,4,3,3]
42 res = s.findShuiKing(alist)
43 print(res)

 

 

二、B站地址

https://www.bilibili.com/video/BV1to4y1D7ka?p=2

 

 

三、相关书籍

《程序员代码面试指南》

 

 

四、《程序员代码面试指南》Python实现

博客地址：https://blog.csdn.net/qq_34342154/article/details/77918297

代码地址：https://github.com/Liwenbin1996/Data_Structures_and_Algorithms