基本算法回顾1

从今天开始在学习编程同时,回顾数据结构算法的知识点,主要参考王铮老师的课。

今天先回顾大纲和一些简单的算法。

基础部分将回顾

数组、链表、栈、队列、递归、排序、线性排序、排序优化、

二分查找、跳表、散列表、哈希算法、

二叉树基础、红黑树、递归树、堆和堆排序、

图、深度优先和广度优先搜索、

字符串匹配、Trie树、AC自动机、

贪心算法、分治算法、回溯算法、

动态规划

高级篇

实战篇

项目地址:https://github.com/wangzheng0822/algo

学习路径图

复杂度分析

需要了解大O复杂度,分析算法复杂度,以及常见的复杂度量级。

复杂度量级

复杂度量级渐进情况

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
__author__ = "xx"
__date__ = "2020/6/27 21:29"


prices = {
'AAPL': 191.88,
'GOOG': 1186.96,
'IBM': 149.24,
'ORCL': 48.44,
'ACN': 166.89,
'FB': 208.09,
'SYMC': 21.29
}
# 生成式:用股票价格大于100元的股票构造一个新的字典
price2 = {key: value for key, value in prices.items() if value > 100}
print(price2)


## 嵌套列表:
# [[None]*2 for _ in range(3)]
# >>> [[None, None], [None, None], [None, None]]
def score_analysic():
names = ['关羽', '张飞', '赵云', '马超', '黄忠']
courses = ['语文', '数学', '英语']
scores = [[None] * len(courses) for _ in range(len(names))]
for row, name in enumerate(names):
for col, course in enumerate(courses):
scores[row][col] = float(input(f"请输入{name}{course}课程成绩:"))
print(scores)


# `heapq`模块(堆排序):
"""
从列表中找出最大的或最小的N个元素
堆结构(大根堆/小根堆)
"""
import heapq

list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
list2 = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
print(heapq.nsmallest(3, list1))
print(heapq.nlargest(2, list2, key=lambda x: x['shares']))


import itertools

itertools.cycle(('A', 'B', 'C'))

"""
算法

排序、查找
"""
def select_sort(items, comp=lambda x,y: x<y):
"""简单选择排序
每趟选取最小的元素,与位置i替换
"""
items = items[:]
for i in range(len(items)-1 ):
min_index = i
for j in range(i+1, len(items)):
if comp(items[j], items[min_index]):
min_index = j
# 注意:这个交换要在第i躺结束后做
items[i], items[min_index] = items[min_index], items[i]
return items


def bubble_sort(items, comp=lambda x,y: x>y):
"""冒泡排序
每次比较都对相邻的做移动,每趟将最大值移至后面,就像冒泡似的。
"""
items = items[:]
for i in range(len(items)-1 ):
# 设置swapped的隐含意思的:如果一趟下来无元素交换,说明已经有序了。
swapped = False
for j in range(len(items)-1-i):
if comp(items[j], items[j+1]):
items[j], items[j+1] = items[j+1], items[j]
swapped = True
if not swapped:
break
return items

def bubble_sort_plus(items, comp=lambda x,y: x>y):
"""冒泡排序 加强版

"""
pass

# 归并排序
# 将要排序的序列,分成两部分排序,再合并。可用递归
def merge(items1, items2, comp=lambda x,y: x<y):
"""
:items1 :有序
:items2 ;有序
由此可见,归并排序是不稳定的
"""
items = []
index1, index2 = 0,0
while index1 < len(items1) and index2<len(items2):
if comp(items1[index1], items2[index2]):
items.append(items1[index1])
index1 += 1
else:
items.append(items2[index2])
index2 += 1
# and的意思是两者都满足True才执行,结束while意味着其中一个序列已经结束了.剩下的直接加到items后面即可
items += items1[index1:]
items += items2[index2:]
return items

def _merge_sort(items, comp=lambda x,y: x<y):
"""归并排序"""
if len(items) < 2:
return items
mid = len(items) // 2
left = _merge_sort(items[:mid], comp)
right = _merge_sort(items[mid:], comp)
return merge(left, right, comp)

def merge_sort(items, comp=lambda x, y: x < y):
return _merge_sort(list(items), comp)


def seq_search(items, key):
"""顺序查找"""
for index, item in enumerate(items):
if item == key:
return index
return -1


def bin_search(items, key):
"""折半查找"""
start, end = 0, len(items)-1
while start <= end:
mid = (start + end) // 2
if key > items[mid]:
start = mid + 1
elif key < items[mid]:
end = mid-1
else:
return mid
return -1


list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
print("list1 排序后:")
print( _merge_sort(list1) )

# print(merge_sort(2, ))
# list(2) 怎么办
print(bin_search(list1, 2))



"""
贪婪法:
求解当前最满意的解,不需要最优,即快速、满意的解

输入:
20 6
电脑 200 20
收音机 20 4
钟 175 10
花瓶 50 2
书 10 1
油画 90 9
"""
class Thing(object):
"""物品"""
def __init__(self, name, price, weight):
self.name = name
self.price = price
self.weight = weight

@property
def value(self):
"""价格 重量比"""
return self.price / self.weight

def input_Thing():
"""录入信息,指定格式
没有做int格式检查,直接报错
"""
name_str, price_str, weight_str = input("请输入(油画 90 9)商品价格重量:").split()
return name_str, int(price_str), int(weight_str)

def thief_going():
max_weight, num_of_thing = map(int, input("小偷的最大负重 眼前想偷的物品件数:").split())
all_things = []
# * 没印象了
for _ in range(num_of_thing):
all_things.append(Thing(*input_Thing()))
all_things.sort(key=lambda x: x.value, reverse=True)
total_weight = 0
total_price = 0
for thing in all_things:
if total_weight + thing.weight <= max_weight:
print(f"小偷拿走了{thing.name}")
total_weight += thing.weight
total_price += thing.price
print(f"总价值:{total_price}元")

# thief_going()

"""
分治法:

快速排序: 选择枢轴对元素做划分,左边的比枢轴小,右边大

"""
def quick_sort(items, comp=lambda x,y: x<=y):
items = list(items)[:]
_quick_sort(items, 0, len(items)-1, comp)
return items

def _quick_sort(items, start, end, comp):
# if start < end:
# pos =
pass

"""
回溯法例子:试探,退回一步重新选择

[骑士巡逻](https://zh.wikipedia.org/zh/%E9%AA%91%E5%A3%AB%E5%B7%A1%E9%80%BB)。
八皇后、迷宫寻路
"""

"""
动态规划:
将求解问题分解为若干子问题。保留其解,避免产生大量运算。
"""


#
list(map( lambda x:x**2, filter(lambda x: x%2, range(1,10)) ))

[x**2 for x in range(1,10) if x%2]



本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!