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

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
__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]

按:刚开始为了减压经常在操场上跑步,后来多亏了同学带我走上运动的道路,熟悉后开始在keep上面跟着做一些动作,最近在github上看到这些建议觉得蛮好的,与君共享。

阅读全文 »

昨晚要交一份报告,这件事情在一个月前就想到要做了,可是却一直没有做。是的,行动的矮子不就说的我自己么,并且这是我目前最大的缺点了,做的太少。

阅读全文 »

这两天江北的天气有点反复无常,前天淅沥沥的小雨下着,今天便艳阳高照,正午时分让人热得闷得慌。或许是我许久不曾在家呆这么久了。这三周断断续续下过三次雨,正是s雨水滋润了眼前这片油菜田,嚯,春天到了。

新冠肺炎疫情以及日常生活正在逐渐好转,过了漫长的冬季,面对眼前秀丽的田野风光,有种春回大地的感觉。嗯,一切都会好起来的。

阅读全文 »