学习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
10
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
2
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
10
# 集合解析
>>> { 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
7
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
18
# 常规方案
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
48
# 实现匹配出所有字符，并非对应所有字符
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