学习Python数据结构和算法的笔记(一)

前言

虽然学习和使用Python已经多年,但是对于算法这一块基本上已经忘的差不多了,正好有机会阅读 用Python解决数据结构和算法 来巩固一下知识点。

目标

学习的目标是什么,或者动力是什么?

  1. 了解计算机科学、程序设计和问题解决的基本概念;
  2. 理解抽象和抽象在问题解决过程中的作用;
  3. 理解抽象数据类型的概念以及运用

算法 即写出一组解决问题可能出现的任何情况的步步为营的指令。算法通过有线的过程解决问题,是一种解决方案。
程序设计 将算法编码为计算机可执行的表示法或编程语言的过程。

Python基础

为什么要学习算法?
通过研究大量不同的算法,可以发展出模式识别机制,当以后出现相似问题时可以更好的解决掉。

Python是一种支持面向对象的编程范式,意味着Python把数据当做问题解决过程的重点。 去描述数据的外观(状态)和功能(行为)。“类”类似于抽象数据类型,“类”的用户只能看到数据项的状态和行为。数据项在面向对象的范式里被称为对象(objects)。对象是类的一个实例。

接下来的内容讲述了Python的基本数据类型:

  • int和float
  • list和set
  • string
  • dict

列表解析

现在尝试解决一些问题。修改代码,是最终列表只包含字母的单一副本['c','a','t','d','o','g','r','b','i'],源码如下:

1
2
3
4
5
6
7
8
9
wordlist = ['cat','dog','rabbit']
letterlist = [ ]
for aword in wordlist:
for aletter in aword:
letterlist.append(aletter)
print(letterlist)

# 输出
['c', 'a', 't', 'd', 'o', 'g', 'r', 'a', 'b', 'b', 'i', 't']

修改后的代码:

1
2
3
4
5
6
7
8
9
wordlist = ['cat','dog','rabbit']
letterlist = [ ]
for aword in wordlist:
for aletter in aword:
letterlist.append(aletter)
print(list(set(letterlist)))

# 输出
['a', 'i', 'b', 'd', 'g', 'o', 'r', 'c', 't']

其实,作者的本意可能是让使用列表解析的方式来达到目的,但是我们有更好的方法,使用set()来去重后再转为list()类型就可以了。

语法

在列表中,存在一种替代方法使用迭代和选择结构创建列表,被称为列表解析

1
newlist = [Expression for var in list]

说明如下:

  • newlist 新生成的列表名称
  • Expression 表达式,用于计算新列表的元素
  • var 变量,值为后面列表的每个元素值
  • list 用于生成新列表的原列表

带有条件的解析

1
newlist = [Expression for var in list if condition]

condition 条件表达式,用于筛选条件。

解析规则

Python中内置类型的解析规则:

  1. 如果使用中括号,表示为列表解析;
  2. 如果使用大括号,表示为集合解析
  3. 如果使用大括号且元素为k:v形式,表示为字典解析。
1
2
3
4
5
6
7
8
9
# 集合解析
>>> { i*2 for i in "abcd"}
{'aa', 'cc', 'dd', 'bb'}

# 字典解析
>>> { k:v for k,v in zip(("one","two","three"),(1,2,3)) }
{'one': 1, 'two': 2, 'three': 3}
>>> { k: k*2 for k in "abcd" }
{'a': 'aa', 'b': 'bb', 'c': 'cc', 'd': 'dd'}
工作方式

首先用迭代工具for对容器中的元素进行跌打,每个元素都经过筛选,对符合条件的元素执行外部表达式,每个外部表达式都生成一个新的元素,然后昨晚新列表的一个元素,从而推导出一个新的列表。

列表解析可以让你创建基于某些处理或选择条件的列表。比如创建一个小于10的整数的平方的列表:

1
2
3
4
5
6
7
8
9
10
11
12
sqlist = list()
for i in range(1,11):
sqlist.append(i*i)
print(sqlist)

sqlist = [i*i for i in range(1,11)]
print(sqlist)

# 输出

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

上面的代码中,第一段是先循环出一个整数,计算后再塞入list。第二段代码其实也是差不多,先取出一个整数,计算平方后再塞入新建的列表中。列表解析还可以使用选择语句,代码如下:

1
2
3
4
5
6
sqlist = [i*i for i in range(1,11) if i%2 !=0]
print(sqlist)

# 输出

[1, 9, 25, 49, 81]

上述代码中取整数后判断是否为奇数,如果是则进行平方计算并塞入新的列表中。

练习——列表解析

删除重复元素:['c', 'a', 't', 'd', 'o', 'g', 'r', 'a', 'b', 'b', 'i', 't']

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 常规方案
s = ['c', 'a', 't', 'd', 'o', 'g', 'r', 'a', 'b', 'b', 'i', 't']
sqlist = list()
for i in s:
if i not in sqlist:
sqlist.append(i)
print(sqlist)

# 列表解析
animal = ['c', 'a', 't', 'd', 'o', 'g', 'r', 'a', 'b', 'b', 'i', 't']
newlist = list()
sqlist = [newlist.append(i) for i in animal if i not in newlist]
print(newlist)

# 输出

['c', 'a', 't', 'd', 'o', 'g', 'r', 'b', 'i']

这里和之前不一样的是,步骤如下:

  1. 循环取出一个元素;
  2. 判断元素是否属于定义的newlist;
  3. 如果不属于则插入到newlist;
  4. 输出newlist.
练习——函数

编写一个函数,该函数生成一个27个字符长度的字符串,从26个字母和空格中随机选择一个字符。编写另一个函数,比较随机生成的字符串和目标字符串。第三个函数将反复调用生成和比较函数,那么如果所有目标字母都在随机字符串中出现了,那么就完成了。如果字母没有全部出现,那么会生成一个全新的字符串。

  1. 第一个函数生成随机字符,从26个字母和空格里;
  2. 第二个函数来比较随机生成的字符和目标字符;
  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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 实现匹配出所有字符,并非对应所有字符
import math
import random


def get_chars():
# 获取26个字符,使用ASCII码表来定位,并生成列表
chars = [chr(i) for i in range(97, 123)]
# 添加空格至列表
chars.append(chr(32))
return ''.join(random.choice(chars) for _ in range(27))


def diff_chars(chars_list, random_chars):
new_chars_list = list()
[new_chars_list.append(i) for i in chars_list if i not in new_chars_list]
random_chars_list = list()
[random_chars_list.append(i) for i in random_chars if i not in random_chars_list]

successful_chars = list()
for i in new_chars_list:
if i in random_chars_list:
successful_chars.append(i)
score = '%.2f' % (len(successful_chars) / len(new_chars_list) * 100)
return score


def get_result():
num = 0
chars = 'methinks it is a weasel'
chars_list = [i for i in chars]
while True:
random_chars = get_chars()
res = float(diff_chars(chars_list, random_chars))
# 如果得分为100或次数等于10000则退出
if math.isclose(res, 100.0, abs_tol=0) or num >= 10000:
print(num, random_chars)
break
num += 1


if __name__ == '__main__':
get_result()

# 输出

323 wc uhtveaimrzvmbrsbmcnlnky
------ 本文结束 ------

版权声明

Medivh's Notes by Medivh is licensed under a Creative Commons BY-NC-ND 4.0 International License.
Medivh创作并维护的Medivh's Notes博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于Medivh 博客( http://www.mknight.cn ),版权所有,侵权必究。