塞进裤子ヾ(≧O≦)〃嗷~

0%

python数据结构与算法

线性表

线性表包括顺序表和链表

顺序表

链表

注意特殊情况的处理(只有一个node,删除第一个结node,删除最后一个node)

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None

class SingleLinkList(object):
def __init__(self, node = None): #默认参数是None
self.__head = node #头指针 属于没有头结点的类型,直接指向第一个元素的值(head中就有elem)
# 双下划线表示私有属性

def isEmpty(self):
return self.__head == None

def length(self):
cur = self.__head #current当前结点
count = 0
while cur is not None:
cur = cur.next
count += 1
return count

def travel(self):
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next

def append(self, elem):#尾部插入元素 尾插法
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = newnode

def add(self, elem): #头部插入元素,头插法
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
else:
newnode.next = self.__head
self.__head = newnode

def insert(self, pos, elem):
#第一个数据的pos为0,insert(2,10):插入后位置2的数据变成了10
if pos <= 0: #看作头插法
self.add(elem)
elif pos > self.length():
self.append(elem)
else:
newnode = Node(elem)
cur = self.__head
count = 0
while count != pos - 1:
cur = cur.next
count += 1
newnode.next = cur.next
cur.next = newnode

def remove(self, elem):
pre = None
cur = self.__head
while cur != None:
if cur.elem == elem:
if cur == self.__head: #若是头结点要特殊处理
self.__head = cur.next
else:
pre.next =cur.next
break
else:
pre = cur
cur =cur.next

def check(self, elem):
#看elem是否存在
cur =self.__head
while cur != None:
if cur.elem == elem:
return True
else:
cur = cur.next
return False


ll = SingleLinkList()
ll.add(22)
ll.append(33)
print("dd")
ll.remove(22)
ll.travel()

双向链表

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

class Node(object):
def __init__(self, elem):
self.elem = elem
self.prev = None
self.next = None

class DoubleLinkList(object):
def __init__(self, node=None): # 默认参数是None
self.__head = node # 头指针 属于没有头结点的类型,直接指向第一个元素的值
# 双下划线表示私有属性

def isEmpty(self):
return self.__head == None

def length(self):
cur = self.__head # current当前结点
count = 0
while cur is not None:
cur = cur.next
count += 1
return count

def travel(self):
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next

def append(self, elem): # 尾部插入元素 尾插法
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = newnode
newnode.prev = cur

def add(self, elem): # 头部插入元素,头插法
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
else:
newnode.next = self.__head
self.__head.prev = newnode
self.__head = newnode


def insert(self, pos, elem):
# 第一个数据的pos为0,insert(2,10):插入后位置2的数据变成了10
if pos <= 0:
self.add(elem)
elif pos >= self.length():
self.append(elem)
else:
newnode = Node(elem)
cur = self.__head
count =0
while count < pos:
cur = cur.next
count += 1
cur.prev.next = newnode
newnode.prev = cur.prev
newnode.next = cur
cur.prev = newnode


def remove(self, elem):
cur = self.__head
while cur != None:
if cur.elem == elem:
if cur == self.__head:
self.__head = cur.next
if cur.next is not None: # None结点没有prev
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next is not None: # None结点没有prev
cur.next.prev = cur.prev
break
else:
cur = cur.next

def check(self, elem):
# 看elem是否存在
if self.isEmpty():
return False
else:
cur =self.__head
while cur is not None:
if cur.elem == elem:
return True
cur = cur.next
return False


dl = DoubleLinkList()
dl.append(3)
dl.append(4)
dl.add(2)
dl.travel()
print(dl.check(22))
dl.remove(2)
dl.travel()

单向循环链表

链表的最后一个node的next域不再为None,而是指向链表的首元结点。

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None

class SingleCycleLinkList(object):
def __init__(self, node=None):
self.__head = node
if node is not None:
node.next = node

def isEmpty(self):
return self.__head is None

def length(self):
cur = self.__head
count = 1
if self.isEmpty():
return 0
while cur.next != self.__head:
cur = cur.next
count += 1
return count

def travel(self):
if self.isEmpty():
return

cur = self.__head
while cur.next != self.__head:
print(cur.elem, end=" ")
cur = cur.next
#退出循环,最后一个结点未print,需print下
print(cur.elem, end=" ")

def add(self, elem):#头插法
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
self.__head.next = newnode
else:
cur = self.__head
newnode.next = cur
while cur.next != self.__head: #退出循环后,cur指向尾结点
cur =cur.next
cur.next = newnode
self.__head = newnode

def append(self, elem):
newnode = Node(elem)
if self.isEmpty():
self.__head = newnode
self.__head.next = newnode
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = newnode
newnode.next = self.__head

def insert(self, pos, elem):
if pos<=0:
self.add(elem)
elif pos >= self.length():
self.append(elem)
else:
newnode = Node(elem)
count =0
cur = self.__head
while count < pos-1:
count += 1
cur = cur.next
newnode.next = cur.next
cur.next = newnode

def check(self, elem):
if self.isEmpty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.elem == elem:
return True
else:
cur = cur.next
# 退出循环,最后一个结点未check,需check下
if cur.elem == elem:
return True
return False

def remove(self, elem):
if self.isEmpty():
return
cur =self.__head
if cur.elem == elem and self.length()==1: #只有一个结点的情况
self.__head = None
return

pre =None
while cur.next != self.__head:
if cur.elem == elem:
if cur == self.__head: #头结点的情况
cur2 = self.__head
#还需改动尾部next
while cur2.next != self.__head: #找尾结点
cur2 = cur2.next
self.__head = cur.next
cur2.next = self.__head

else:
pre.next = cur.next #完美结点
return
else:
pre = cur
cur = cur.next
if cur.elem == elem: #尾结点的情况
pre.next = self.__head

scl = SingleCycleLinkList()
scl.add(2)
scl.append(3)
scl.insert(1, 4)
scl.travel()
scl.remove(2)
print("==")
scl.travel()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Stack(object):
# 借助list实现栈,list尾部作为栈顶(list作为顺序表在尾部插入删除是O(1),
# 而如果用单链表应该将头部作为栈顶才会有较低的时间复杂度)
def __init__(self):
self.__list = []

def pop(self):
"""弹出栈顶元素"""
return(self.__list.pop())

def peek(self):
"""返回栈顶元素"""
if self.__list:
return self.__list[-1]
else:
return None

def push(self, elem):
"""添加新元素到栈顶"""
self.__list.append(elem)

def isEmpty(self):
return self.__list == []

def length(self):
return len(self.__list)

def travel(self):
for i in self.__list:
print(i, end=" ")


s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.pop()
s.travel()

队列

普通队列

只允许在一段进行插入操作,而另一端进行删除操作的线性表。

允许删除的一段为队头,允许插入的一段为队尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Queue(object):
# 借助list实现队列
def __init__(self):
self.__list = []

def addqueue(self, elem):
"""在队尾添加元素"""
self.__list.append(elem)

def popqueue(self):
"""在队头删除元素"""
self.__list.pop(0)

def isEmpty(self):
return self.__list == []

def length(self):
return len(self.__list)

def travel(self):
for i in self.__list:
print(i, end=" ")

s = Queue()
s.addqueue(1)
s.addqueue(2)
s.addqueue(3)
s.travel()
s.popqueue()
s.travel()

双端队列

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Deque(object):
# 借助list实现队列
def __init__(self):
self.__list = []

def addFront(self, elem):
"""在头部添加元素"""
self.__list.insert(0, elem)

def addRear(self, elem):
"""在队尾添加元素"""
self.__list.append(elem)

def popFront(self):
"""在队头删除元素"""
self.__list.pop(0)

def popRear(self):
"""在队尾删除元素"""
self.__list.pop()

def isEmpty(self):
return self.__list == []

def length(self):
return len(self.__list)

def travel(self):
for i in self.__list:
print(i, end=" ")

二叉树

满二叉树

从形象来看的话满二叉树是一个绝对的三角形,最后一层全部是叶子节点

完全二叉树

从形象上讲它是个缺失的的三角形,但所缺失的部分一定是右下角某个连续的部分,最后那一行可能不是完整的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Node(object):
def __init__(self, elem):
self.elem = elem
self.lchild = None #左节点
self.rchild = None

class Tree(object):
def __init__(self):
self.root = None #根节点

def createfromlist(self, root, elemlist,index=0):
#RE:https://blog.csdn.net/lznsay/article/details/78710257
if index < len(elemlist):
if elemlist[index] < 0:
root = None
else:
root = Node(elemlist[index])
root.lchild = self.createfromlist(root.lchild,elemlist,2*index+1)
root.rchild = self.createfromlist(root.rchild,elemlist,2*index+2)
return root

def allPath(self,root):
#返回根节点到叶子结点的所有路径,以二维列表形式
"""
思路,两个list,curpatlist记录树的根节点当前结点的路径;
pathlist记录根节点到叶节点的所有路径。
通过递归形式走到叶子节点,若到了叶节点,则将pathlist.append(curpathlist)
而且curpathlist要pop,返回上一层
"""

def get_paths(root, curpathlist, pathlist):
# 当前节点,当前路径(树根节点到当前结点的路径),所有的路径结果
if root:
curpathlist.append(root.elem)

left = get_paths(root.lchild, curpathlist, pathlist)
right = get_paths(root.rchild, curpathlist, pathlist)
#如果到达叶子结点,则将当前结果添加到所有结果列表中;
if left==False and right==False:
pathlist.append(curpathlist.copy())#把当前路径加入到结果列表中
#注意要copy下,若不copy,curpathlist.pop会改变pathlist
curpathlist.pop()#返回上一层递归时,弹出路径中的当前结点元素
return True
return False

if root is None:
return []
pathlist = []
get_paths(root, [], pathlist)
return pathlist

def add(self, elem):
#按广度优先添加元素
newNode = Node(elem)
if self.root == None:
self.root = newNode
return
queue= [self.root] #使用队列实现,先将root加入
while queue:
curNode = queue.pop(0) #获取队首节点
if curNode.lchild is None:
curNode.lchild = newNode #当前结点没有左孩子,直接加到左孩子上
return
else:
queue.append(curNode.lchild)
if curNode.rchild is None:
curNode.rchild = newNode
return
else:
queue.append(curNode.rchild)

def breadthTravel(self):
#广度优先遍历,用队列实现,
if self.root is None:
return
queue = [self.root]
while queue:
curNode = queue.pop(0)
print(curNode.elem, )
if curNode.lchild:
queue.append(curNode.lchild)
if curNode.rchild:
queue.append(curNode.rchild)

def preorder(self, node):
#先序遍历,根左右
if node is None:
return
print(node.elem, end=" ")
self.preorder(node.lchild)
self.preorder(node.rchild)

def inorder(self, node):
#中序遍历,左根右
if node is None:
return
self.inorder(node.lchild)
print(node.elem, end=" ")
self.inorder(node.rchild)

def postorder(self, node):
#后序遍历,左右根
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem, end=" ")

def depth(self,node):
#讲解二叉树的深度 [解答](https://sbaban.com/jzo55.html)
if node is None:
return 0
leftdepth = self.depth(node.lchild)
rightdepth = self.depth(node.rchild)
return max(leftdepth,rightdepth)+1



mytree =Tree()
#for i in range(10):
# mytree.add(i)
mytree.root = mytree.createfromlist(mytree.root,[1,2,3,-1,5,3,4,7,8,9])
mytree.breadthTravel()
# mytree.allPath(mytree.root)
mytree.depth(mytree.root)

参考《算法图解》与https://www.bilibili.com/video/av38669550/?p=36

红黑树

二叉查找树的一种。

四个性质:①每个节点不是红色就是黑色。 ②根节点和叶子结点(这里的叶子节点指的是None结点)是黑色

③不能出现连在一起的红色结点。 ④每个红色结点的两个子节点都是黑色。

代码待补充

堆排序的效率与快排、归并相同,都达到了基于比较的排序算法效率的峰值(时间复杂度为O(nlogn )

堆排序的空间复杂度是O(1 )

堆需要满足的条件:

  • 1.必须是二叉树,且必须是完全二叉树
  • 2.各个父节点必须大于或小于左右结点, 其中最顶层的根结点必须是最大或者最小的.
  • 3.堆中每个节点的子树都是堆树。

堆的创建与删除:https://www.bilibili.com/video/av18980178/

heapq模块

heapq不支持大根堆,在stackoverflow上看到了一个巧妙的实现:用小根堆来进行逻辑操作,在做push的时候,我们把最大数的相反数存进去,那么它的相反数就是最小数,仍然是堆顶元素,在访问堆顶的时候,再对它取反,就获取到了最大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import heapq

data = [5,0,1,2,9]

#建立堆,有两种方式,heappush()和heapify()。
# heapq.heapify(data) #直接将原列表转为堆,
heap = []
for i in data:
heapq.heappush(heap,i)
# print(heap) #[0, 2, 1, 5, 9]

#添加新数据
heapq.heappush(heap,0.5)
# print(heap) # [0, 2, 0.5, 5, 9, 1]

#弹出堆顶元素,并return 堆顶
heapq.heappop(heap) # return 0
print(heap) # [0.5, 2, 1, 5, 9]

#heapq.nlargest(n, iterable, key=None)
#返回可迭代对象iterable最大的n个元素(Top-K问题),key与sorted()的key类似
#https://blog.csdn.net/m0_38109046/article/details/86636511?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

heapq.nlargest(3, heap) #[9, 5, 2]
heapq.nlargest(3, heap, key=lambda x:x<5)#[0.5, 2, 1]
#heapq.nsmallest(n, iterable, key=None)
#返回最小的n个元素(Top-K问题)


# heapq.heappushpop(heap, elem)
#先把elem加入到堆中,然后再pop,比heappush()再heappop()要快得多

#heapq.heapreplace(heap, elem)
#先pop,然后再把elem加入到堆中,比heappop()再heappush()要快得多

排序

mark

排序算法的稳定性是指原本有相等键值的记录维持相对词序。

如(3,1)(3,4)排序后依然是(3,1)(3,7)

冒泡排序

bubble sort,需要进行n-1次冒泡。稳定性:稳定

1比较相邻元素,排序

2对每一对相邻元素同样的操作,

3重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bubbleSort(mylist):
n = len(mylist)
for i in range(0, n-1):#执行n-1次冒泡
for j in range(0, n-i-1):# n-i-1次相邻元素比较
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]

改进:
def bubbleSort(mylist):
n = len(mylist)
for i in range(0, n-1):#执行n-1次冒泡
count = 0
for j in range(0, n-i-1):# n-i-1次相邻元素比较
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
count += 1
if count == 0: #说明已经有序了
break

选择排序

遍历未排列的元素中,找出最小值,放入已排序序列。

重复

时间复杂度为$O(n^2)$,稳定性:不稳定(考虑升序排列,每次选择最大值放在右边)

1
2
3
4
5
6
7
8
9
10
11
12
13
mylist = [10,1,12,3,14,5]

def selectSort(mylist):
n = len(mylist)
for i in range(0, n-1):#找n-1次最小值
minIndex = i
for j in range(i+1, n):
if mylist[j] < mylist[minIndex]:
minIndex = j
mylist[i], mylist[minIndex] = mylist[minIndex], mylist[i]


print(selectSort(mylist))

插入排序

从无序序列中取一个元素,与有序序列中的元素比较插入,(打扑克).

稳定性:稳定

1
2
3
4
5
6
7
8
9
10
11
12

def insertSort(mylist):
n = len(mylist)
for i in range (1, n): #n-1个元素进行比较
j = i
while j > 0: #从右边无序序列汇总取第一个元素与排好序的序列比较
if mylist[j] < mylist[j-1]:
#每个元素都与前一个比较:
mylist[j], mylist[j-1] = mylist[j-1], mylist[j]
j -= 1
else: #优化,新元素比已排序的最后一个要大,此元素无需再比较
break

希尔排序

Shell Sort是插入排序的一种,也叫缩小增量排序。稳定性:不稳定

mark

注意对各个组插入排序的时候,不是先对一个组排序完再对另一个组进行排序,而是轮流对每个组进行插入排序。(77排序后,再对31与26排序,再44,再55.再20与【54,77】排序。。)

1
2
3
4
5
6
7
8
9
10
11
12
13
def shellSort(mylist):
n = len(mylist)
gap = n//2
while gap >= 1:
for i in range(gap, len(mylist)):#从gap索引处比较,注意是轮流对每个组插入排序
j = i
while j > 0: #小组的插入排序
if mylist[j] < mylist[j-gap]:
mylist[j], mylist[j-gap] = mylist[j-gap], mylist[j]
j -= gap
else: #
break
gap = gap // 2 #一次gap分组的排序完成,继续按gap分组

快速排序

采用分而治之策略,时间复杂度为$O(logn)$

首先选择一个元素作为基准,比它小的放左边,比它大的放右边。

同样地对左边的元素们进行此操作,对右边的元素们进行此操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
mylist = [10,1,2,13,4,5]

def quickSort(mylist):
if len(mylist) < 2:#base case只剩0或1个元素,不用排序
return mylist
else:
less = []
greater = []
base = mylist[0] #这里选的第一个元素用于比较,实际上应该随机选
for elem in mylist[1:]:
if elem <= base:
less.append(elem)
else:
greater.append(elem)
return quickSort(less) + [base] + quickSort(greater)

print(quickSort(mylist))

这段代码虽然短小利于理解,但是其效率很低,主要体现在以下方面:

  • 分组基准的选取过于随便,不一定可以取到列表的中间值

  • 空间复杂度大,使用了两个列表(less和greater),而且每次选取进行比较时需要遍历整个序列。

  • 若序列长度过于小(比如只有几个元素),快排效率就不如插入排序了。

  • 递归影响性能,最好进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
下面用Python写一个C风格的快排(这里可以体会到快排的精髓):
mylist = [4,5,7,1,3]

def partition(mylist,low,high):
#选择mylist[low]元素作为分界点,low和high是mylist的下标
#此函数将比分界点小的放左边,比分界点大的放右边,
#返回分界点的位置索引low
midValue = mylist[low]
while low<high:#high左移和low右移交替进行
while low<high and mylist[high]>= midValue:
#mylist[high]>midvalue,high就一直左移
high -= 1
mylist[low] = mylist[high]#high处元素小于midValue,赋给low所在位置,赋值后high处的元素就没意义了

while low<high and mylist[low] < midValue: #low一直右移
low += 1
mylist[high] = mylist[low] # 赋给high所在位置,

mylist[low] = midValue
return low #返回分界点索引


def quicksort(mylist, low, high):
"""
:param mylist:
:param low:第一个元素下标
:param high: 最后一个元素下标
:return: none
"""
if low < high:
middleIndex = partition(mylist,low,high)

quicksort(mylist, low, middleIndex-1) #递归处理前半段
# 注意不能用切片,即quicksort( mylist[:low])
# 因为mylist[;low]和mylist的id不同,更改mylist[:low]不能改变mylist,要传递完整的list
quicksort(mylist, middleIndex+1, high) #递归处理后半段
return mylist

归并排序

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
mylist = [10,1,2,13,4,5]

def mergeSort(mylist):
n = len(mylist)
if n < 2:
return mylist
mid = n // 2
# 分别对左右两个list进行处理,分别返回两个排序对list
left = mergeSort(mylist[:mid])
right = mergeSort(mylist[mid:])
# 对排序好的两个列表合并,产生一个新的排序好的列表
return merge(left, right)

def merge(left, right):
#合并两个有序的list
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

print(mergeSort(mylist))

查找

二分查找

输入必须是有序的元素列表,时间复杂度为$O(logn)$。

对于包含n个元素的列表,二分查找最多需要$log_2 ^n$步。

比较中间的值,比中间值小,在左边元素里查找,大了就在右边找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
mylist = [0,1,2,3,4,5]

def binary_search(mylist, item):
"""
:param mylist: 有序列表
:param item: 要查找的元素
:return: 返回其位置
"""
low = 0
high = len(mylist) - 1

while low <= high:
mid = int((low + high) / 2)
guess = mylist[mid]

if guess == item:
return mid
elif guess < item:
low = mid + 1
else:
high = mid - 1
return None

print(binary_search(mylist,3))

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#错误代码
def binary_search(mylist, item):

mid = int(len(mylist)/2)
print(mid)

if item < mylist[mid]:
binary_search(mylist[:mid], item)
elif item > mylist[mid]:
binary_search(mylist[mid+1:], item)
else:
return True# 不能用递归,这里并不会结束,而是会返回递归的上一次继续执行binarySerach
#这句话是我之前分析的错误原因,now发现问题了。
#问题的原因在于if和else里没加return,返回不到之前的层。
改正:
def binarySearch(mylist, item):
if len(mylist) > 0:
mid = int(len(mylist)/2)
if item < mylist[mid]:
return binarySearch(mylist[:mid], item)
elif item > mylist[mid]:
return binarySearch(mylist[mid+1:], item)
else:
return True
return False

递归

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。

1
2
3
4
5
6
def countdown(i):#倒计时
print i
if i <= 0: #base case
return
else:
countdown(i-1) #recursive case

哈希表

哈希函数是这样的函数,即无论你给它什么数据,它都还你一个数字,即将不同的输入映射到不同的数字。

python的字典dict {}就是哈希表的实现

冲突

不同的键key映射到了相同的位置

解决方法:

如果两个键映射到了同一个位置,就在这个位置存储一个链表。

mark

比如apples和avocadado映射到了同一位置,可在这个位置存储一个链表。

填装因子(包含的元素数/空间总数)越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

广度优先搜索

breadtf-first search(BFS)主要解决两类问题:

第一类问题:从节点A出发,有前往节点B的路径吗?

第二类问题:从节点A出发,前往节点B的哪条路径最短(这里的最短不是指最快,而是指段数最少)

可用队列实现BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 有向图中以广度优先搜索找以m结尾的人

from collections import deque

# 用dict创建有向图
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def isPerson(name):#检测是否是要找的人
return name[-1] == 'm'

def search():
search_queue = deque() # 创建一个队列
search_queue += graph['you'] # 将图的第一层加入队列
searched = []
#记录已经找过的人,节省时间,同时避免陷入死循环(a朋友里有b,b朋友里有a)

while search_queue: #搜索队列不为空
person = search_queue.popleft() #取出队列的第一个
if person not in searched:
if isPerson(person):
print("find ")
return True
else:#若不是,将此人的朋友(第二层图)加入到队列后,继续搜索队列中的第一层图。
search_queue += graph[person]
searched.append(person)
print("not find")
return False


search()

狄杰斯特拉

可应用于有向无向有环无环图,不能用于有负权边的图(对于负权边最短路径,可用贝尔曼福德算法(Bellman-Ford)。

(1) 找出“最便宜”的节点,即可在最短时间内到达的节点。
(2) 对于剩下的结点,检查在该节点基础上是否有前往它们的更短路径,如果有,就更新其开销。
(3) 重复这个过程,直到对图中的每个节点都这样做了。
(4) 计算最终路径。

以下图为例

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
graph = {}
graph ['start']= {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph ['b']= {}
graph['b']['a'] = 3
graph['b']['end'] = 5
graph['a'] = {}
graph['a']['end'] = 1
graph['end'] = {}


# 创建cost表,cost指从起点到该点的cost
infinity = float("inf") #表示无穷大
costs ={}
costs['a'] = 6 #起点到a的cost为6
costs['b'] = 2
costs['end'] = infinity

#存储父节点的哈希表
parents = {}
parents['a'] = "start"
parents['b'] = "start"
parents['end'] = None

processed = [] #记录已处理过的结点

def find_lowest_cost_node(costs):
#在costs中找cost最小的
lowest_cost = infinity
lowest_cost_node = None
for node in costs:
if costs[node] < lowest_cost and node not in processed:
lowest_cost = costs[node]
lowest_cost_node = node
return lowest_cost_node

node = find_lowest_cost_node(costs) #在未处理的nodes中找cost最小的
while node is not None:
cost = costs[node] #起点到该node 的cost
neighbors = graph[node] #该node 的下一站结点

#在该node基础上,更新前往剩余nodes的更小的cost
for n in neighbors.keys(): #对该node的每个neighbor,n是neigbor
newcost = cost + graph[node][n]
if newcost < costs[n]:
costs[n] = newcost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)

print(costs[end]) #到end的最短路径
#倒序输出最短路径
node = 'end'
print(node)
while parents[node] != 'start':
node = parents[node]
print(node)

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#选择最少的广播台覆盖所有的8个州
#使用贪心算法,每次选择覆盖州最多的广播台

# 需要被覆盖的州,即还未覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])
# 广播台清单
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
#最终选择的广播台
final_stations = set()

while states_needed: #只要未覆盖完
best_station = None
states_covered = set() #存储已经覆盖的州

#每次取覆盖最多的州的广播台
for station, states_for_station in stations.items():
covered = states_for_station & states_needed #该广播台能覆盖的州
if len(covered) > len(states_covered):
states_covered = covered
best_station = station

states_needed = states_needed - states_covered # 从要覆盖的州中减去已经覆盖过的
print('states_needed:', states_needed)

final_stations.add(best_station)

print(final_stations)

动态规划

0-1背包最大价值

mark

动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。这意味着使用动态规划算法解决不了去巴黎玩的问题。

在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。

最长公共子串

mark

mark

需要注意的一点是,这个问题的最终答案并不在最后一个单元格中!对于前面的背包问题,
最终答案总是在最后的单元格中。但对于最长公共子串问题,答案为网格中最大的数字——它可
能并不位于最后的单元格中。

最长公共子序列

子串要求在原字符串中是连续的,而子序列只需保持相对顺序一致,但不要求连续。

mark

mark

if help:小手一抖点个广告 or 大手一挥资助一下