1.去重
有序
old_list = [2, 3, 4, 5, 1, 2, 3]
new_list = []
for i in old_list:
if i not in new_list:
new_list.append(i)
print(new_list) # [2, 3, 4, 5, 1]
set集合无序
old_list = [2, 3, 4, 5, 1, 2, 3]
new_list = list(set(old_list))
print(new_list) # 不保证顺序：[1, 2, 3, 4, 5]
set集合有序
old_list = [2, 3, 4, 5, 1, 2, 3]
new_list = list(set(old_list))
new_list.sort(key=old_list.index)
print(new_list) # 保留顺序：[2, 3, 4, 5, 1]
2.统计字符出现次序
from collections import Counter
list1 = ["a", "a", "a", "b", "c", "c", "f", "g", "g", "g", "f"]
dic = Counter(list1)
print(dict(dic)) #字典{'a': 3, 'b': 1, 'c': 2, 'f': 2, 'g': 3}按照降序排列
list1= sorted(dic.items(),key=lambda x:x[1]) #升序value的列表
print(list1) #[('b', 1), ('c', 2), ('f', 2), ('a', 3), ('g', 3)]
for i,v in dic.items(): #遍历key-value #结果:按统计次数降序排序
print(i,v)
for i in dic.keys(): #取字典的key
print(i)
for i in dic.values(): #取字典的value
print(i)
#必须带print输出
3.在字符串中找出第一个只出现一次的字符，Python实现https://www.cnblogs.com/springionic/p/10985925.html
3.双向队列[deque]
4.排序sort
reverse()方法
将列表中元素反转排序
x = [1,5,2,3,4]
>>> x.reverse()
>>> x
[4, 3, 2, 5, 1]
sort()排序方法
此函数方法对列表内容进行正向排序，排序后的新列表会覆盖原列表
a = [5,7,6,3,4,1,2]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5, 6, 7]
5.二分查找
def BinarySearch(nums:list,x:int) :
'''
nums: 列表
x: 目标值
'''
left,right = 0,len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] == x:
return mid
if nums[mid] < x:
left = mid+1
else:
right = mid-1
return None
5.顺序查找、线性查找（从头到尾）
def linear_search(lis,val):
for index,value in enumerate(lis):
if value == val:
return index
return None
6.Python中字符串反转
方法一：反转列表法
方法二：循环反向迭代法
方法三：倒序切片法
方法四：双向队列排序法
7.整数翻转
def reverse(x): #x翻转，x：int
res = 0
first = x
x = abs(x) #绝对值
if x > 999: #边界
return "out"
while x != 0: #循环条件
tmp = x%10
res = res*10 + tmp
x = x//10
if first < 0: #原来输入为负数，输出也是负数
return -res
return res #正数
8.从1到n去掉两个再把剩余的放进列表，列表乱序，怎么快速找到丢失的一个数
def missing(lis,n):
sum = 0
num = 0
for i in lis:
sum = sum ^ i
for j in range(1,n+1):
num = num ^ j
return sum ^ num
9.从1到n去掉两个再把剩余的放进列表，列表乱序，怎么快速找到丢失的n个数
def missing(lis,n):
example = set(range(1,n+1)) #set集合是散列排序，查值很快
frist = set(lis)
example = example.difference(first) #O(n)
return example
10.二叉树的实现：
class BiTreeNode(object):
def __init__(self,data):
self.data = data
self.lchild = None
self.rchild = None
a = BiTreeNode("A")
b = BiTreeNode("B")
a.rchild = c
c.lchild = b
root = a
10.python树的深度优先遍历
前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
深度优先有三种算法：前序遍历，中序遍历，后序遍历
def pre_order(root):
if root:
print(root.data,end=',')
pre_order(root,lchild)
pre_order(root,rchild)
def pre_order(root):
if root:
pre_order(root,lchild)
print(root.data,end=',')
pre_order(root,rchild)
def pre_order(root):
if root:
pre_order(root,lchild)
pre_order(root,rchild)
print(root.data,end=',')
11.python树的广度优先遍历（用栈实现）
从树的root开始，从上到下从左到右遍历整个树的节点
def breadth_travel(self, root):
"""利用队列实现树的层次遍历"""
if root == None:
return
queue = [] #或者用deque双向队列 append+popleft
queue.append(root)
while queue:
node = queue.pop(0)
print node.data #打印节点的数值
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
12.python求素数个数（大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数称为素数）
13.斐波那契数列
def fibana(num):
a = 0
b = 1
index = 0
while index < num:
result = a
a,b = b,a+b
index += 1
yield result
f = fibana(4) #调用
next(f)
14.单例模式
import threading
class SingleTon(object):
instance = None
lock = threading.RLock()
def __init__(self,name):
self.name = name
def __new__(self):
if cls.instance:
return cls.instance
with lock:
if not cls.instance:
super().__new__(cls)
return cls.instance
15.装饰器
def set_func(func):
def call_func(*args,*kwargs): #接收元组，接收字典
print("test test test")
return func(*args,*kwargs) #拆包
return call_func
@set_func
def test(num,*args,**kwargs):
return "ok"
16.Python将list中某个元素移至末尾
list = [1,88,33,13]
a = list.remove(list[n]) #移动下标为n的数
list.append(a)
17.单链表反转python版（https://blog.csdn.net/gongliming/article/details/88712221）
18.统计字符个数（https://huihe.blog.csdn.net/article/details/105008702?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link）
接上：sum为总的接收数，但是如果中间有回车则不包括
str为列表，每次回车前数据为一次值
所以blank为len-1
lower()：切换为小写字母 ord()：返回ascall码
19.统计某个指定符号的个数
20.字符串全排列python实现（即给定字符串输出排列组合）
https://blog.csdn.net/weixin_42587961/article/details/81111511
https://blog.csdn.net/m0_37422289/article/details/80570726
21.判断一个链表是否存在环（Python）https://blog.csdn.net/qq_34840129/article/details/80803169
解释：True代表有环
22.把一个列表中所有的字符串转换成小写，非字符串元素原样保留
L = ['TOM', 'Peter', 10, 'Jerry']
# 用列表生成式实现
list1 = [x.lower() if isinstance(x, str) else x for x in L]
# 用map() #map()就是把函数映射到序列中每个元素
def func(n):
if isinstance(n,str):
return n.lower() #lower()方法返回字符串小写
return n
list(map(func,l))
23.把一个列表中所有的字符串转换成小写，非字符串元素移除
L = ['TOM', 'Peter', 10, 'Jerry']
# 用列表生成式实现
list3 = [x.lower() for x in L if isinstance(x, str)]
# 用map() #map()就是把函数映射到序列中每个元素
def func(n):
if isinstance(n,str):
return n.lower() #lower()方法返回字符串小写
list(map(func,l))
24.两个栈实现一个队列
(以列表作为栈的底层实现，只要保证后进先出的约束就是栈)
入队：元素进栈A
出队：先判断栈B是否为空，为空则将栈A中的元素 pop 出来并 push 进栈B，再栈B出栈，如不为空则栈B直接出栈
class Queue:
def __init__(self):
self.stockA=[] #栈1
self.stockB=[] #栈2
def push(self, node):
self.stockA.append(node)
def pop(self):
if self.stockB==[]:
if self.stockA==[]:
return None
else:
for i in range(len(self.stockA)):
self.stockB.append(self.stockA.pop())
return self.stockB.pop()
24.两个队列实现一个栈
(实现：就以列表作为队列的底层实现，只要保证先进先出的约束就是队列。这里只实现进栈和出栈两个操作。)
进栈：元素入队列A
出栈：判断如果队列A只有一个元素，则直接出队。否则，把队A中的元素出队并入队B，直到队A中只有一个元素，再直接出队,实现出栈。为了下一次继续操作，互换队A和队B。
class Stock:
def __init__(self):
self.queueA=[]
self.queueB=[]
def push(self, node):
self.queueA.append(node)
def pop(self):
if len(self.queueA)==0:
return None
while len(self.queueA)!=1:
self.queueB.append(self.queueA.pop(0))
self.queueA,self.queueB=self.queueB,self.queueA #交换是为了下一次的pop
return self.queueB.pop()
24.python大数相乘
时间复杂度O(n^2)
1、把数据扔到list里然后逆转，list顺序0~n对应个位、十位...
2、创建存储结果list，长度默认为两个被乘数长度之和
3、按位相乘，相同竖线位置累加
4、结果list从0位开始遍历，如果大于9进位
5、结果逆序
list = list（str）
def mul(n1,n2):
n1.reverse()
n2.reverse()
n3=[] #新列表作为存储
print n1,n2
for i0 in range(len(n1)+len(n2)): #最大位数[之所以要最大因为后面的大于9进位要是没有最大位数的话无法写入进位，造成报错]
n3.append(0)
for i1 in range(len(n1)):
for i2 in range(len(n2)):
n3[i1+i2] += n1[i1]*n2[i2]
for i3 in range(len(n3)):
if(n3[i3]>9):
n3[i3+1] += n3[i3]//10
n3[i3] = n3[i3]%10
n3.reverse()
return n3
print mul([2,4,5,6,6],[4,5,2,0,5,3]) #调用
#[2,4,5,6,6]*[4,5,2,0,5,3]=[1, 1, 1, 0, 5, 1, 3, 3, 9, 9, 8]
25.Topk问题
（1）快排后切片 O(nlgn)
（2）选泡插 O(kn)
（3）堆排序 O(nlgk) 建立小根堆
1.取列表前k个元素建立小根堆，堆顶就是第k大的数，
2.依次往后遍历原列表，对于列表中的元素如果小于堆顶则忽略，如果大于堆顶则该数替换堆顶，并对堆进行一次调整（小根堆是基于列表，但是堆对于父与子是有序，但是对于整体列表不一定，所以要把最大的数移动到列表最后位置，所以要进行第三步遍历倒序弹出）
3.遍历所有元素后，倒序弹出堆顶
sift函数的作用：节点的左右树已经是小根堆，再把节点调整整体为小根堆
26.python优先队列
1.内置库：https://blog.csdn.net/liuweiyuxiang/article/details/97249128
2.自我实现：
27.图的深度优先遍历和广度优先遍历，【结果是输出遍历的顺序】
深度优先DFS:回溯操作(即有入栈、出栈操作)
广度优先BFS:重放操作(即有入队列、出队列操作)
深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
广度优先遍历可定义如下：首先访问出发点v，接着依次访问v的所有邻接点w1、w2......wt，然后依次访问w1、w2......wt邻接的所有未曾访问过的顶点。以此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
def DFS(graph, s): #深度
stack = [] #当前所在路径上的点
stack.append(s)
seen = [] # 记录已经遍历过的点，已经走过的点
seen.append(s)
while stack:
vertex = stack.pop() # 栈，当走不通的弹出最后一个值切换线路
nodes = graph[vertex]
for w in nodes:
if w not in seen:
stack.append(w)
seen.append(w)
print(vertex)
def BFS(graph, s): #广度
queue = [] # 建立队列
queue.append(s)
seen = [] # 记录已经遍历过的点
seen.append(s)
while queue:
vertex = queue.pop(0) # 队列，先进先出
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.append(w)
print(vertex)
if __name__ == '__main__':
# 图节点，邻接表
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'],
'E': ['C', 'D'],
'F': ['D']
}
BFS(graph, 'A')
DFS(graph, 'A')
28.图的找到到达目的节点的距离（有权和无权图）https://mp.weixin.qq.com/s/gjjrsj95X4w7QdWBlAKnaA
无权：广度优先遍历，最先到达的那条路径最短
有权：换句话说权值之和最小的路径，【迪杰斯特拉算法】
不断刷新起点与其他各个顶点之间的 “距离表”。从起点出发，每次配合距离起点最近的点,遍历该顶点,进行更新距离表。距离表中找到从起点A出发距离最短的点进行更新。
29.图的 “最短路径” 问题，找到具体路径
维护两个表：距离表和前置顶点表
更新距离表然后更新前置顶点表，根据前置顶点表的值为下标索引一步一步找到起点https://mp.weixin.qq.com/s/ALQntqQJkdWf4RbPaGOOhg
30.二进制与十进制转换
https://www.cnblogs.com/ddpeng/p/11302368.html
31.图的最小生成树（连接所有节点，权重尽可能小）
这个prime算法是以图的顶点为基础，从一个初始顶点开始，寻找触达其他顶点权值最小的边，并把该顶点加入到已触达顶点的集合中。不断从顶点集合寻找触达其他顶点的最小权值的边。当全部顶点都加入到集合时，算法的工作就完成了。
为了便于操作，我们的最小生成树用一维数组/列表来表达，列表下标所对应的元素，代表该顶点在最小生成树当中的父亲节点。
https://www.cnblogs.com/yichengming/p/11469454.html
https://mp.weixin.qq.com/s/x7JT7re7W7IgNCgMf1kJTA
32.python六大的设计原则和常见的设计模式
https://www.cnblogs.com/alex3714/articles/5760582.html
33.给定一个矩阵m*n，从左上角开始每次只能向右或者向下走，最后到右下角的位置共有多少种路径（用动态规划实现）
https://blog.csdn.net/rocsun01/article/details/89004668
"""
输入一个m*n的网格，输出从左上角到右下角的路线数量，只能向左或向右走
"""
def grid_go(m, n):
"""
此函数模拟m*n矩阵的路线数量，网格问题只需把m和n分别加一即可
:param m: 矩阵的长
:param n: 矩阵的宽
:return: 线路条数
"""
if m == 0 or n == 0:
total_times = 1
else:
total_times = grid_go(m - 1, n) + grid_go(m, n - 1)
return total_times
def main():
input_str = input('请输入网格的长和宽，用空格隔开：')
input_str_list = input_str.split(' ')
m = int(input_str_list[0])
n = int(input_str_list[1])
total_times = grid_go(m + 1, n + 1) # 模拟的是网格，所以要把m和n都加一
print('共有{}条路线'.format(total_times))
if __name__ == '__main__':
main()
34.首字母转大写+下划线转驼峰
def str2Hump(text):
arr = filter(None, text.lower().split('_')) #None作用：把序列中的False值，如空字符串、False、[]、None、{}、()等等都丢弃
res = ''
for i in arr:
res = res + i[0].upper() + i[1:] #upper() 方法将字符串中的小写字母转为大写字母
return res
小驼峰命名法：第一个单词以小写字母开始；第二个单词的首字母大写，例如：myNane，aDog。
大驼峰命名法：每一个单词的首字母都采用大写字母，例如：FirstName，LastName
小驼峰（如果要实现小驼峰，也是非常简单的。第一组不转换直接拼装就可以了。）
def str2Hump(text):
arr = filter(None, text.lower().split('_')) #None作用：把序列中的False值，如空字符串、False、[]、None、{}、()等等都丢弃
res = ''
res = res + i[0].upper() + i[1:]
for i in arr[1:]:
res = res + i[0].upper() + i[1:] #upper() 方法将字符串中的小写字母转为大写字母
return res
34.两个 list 获取交集
#方法一:
a=[2,3,4,5]
b=[2,5,8]
tmp = [val for val in a if val in b] #列表推导式求的两个列表的交集
print tmp
#[2, 5]
#方法二
print list(set(a).intersection(set(b))) #列用集合的取交集方法
- 获取两个list 的并集
print list(set(a).union(set(b)))
- 获取两个 list 的差集
print list(set(b).difference(set(a))) # b中有而a中没有的
另：火火火或或或
>>> x & y # 交集
set(['a', 'm'])
>>> x | y # 并集
set(['a', 'p', 's', 'h', 'm'])
>>> x - y # 差集
set(['p', 's'])
35.输入aaabbbbc----------输出：a_3_b_4_c_1
stri = 'aaabbbbc'
new_list = list(set(stri)) #集合去重
new_list.sort(key=list(stri).index) #保持原有的次序
i =new_list[0] #当集合内只有一个数值
number=stri.count(i)
result = i+"_"+str(number) #拼接
for i in new_list[1:]: #当集合内的数大于1
number=stri.count(i)
result = result + "_" + i+"_"+str(number) #拼接多一个“_”
print(result)
36.python实现两个文件合并功能
https://www.jb51.net/article/137539.htm（实现是错的，只看原理）
