前言
虽然学习和使用Python已经多年,但是对于算法这一块基本上已经忘的差不多了,正好有机会阅读 用Python解决数据结构和算法 来巩固一下知识点。
目标
学习的目标是什么,或者动力是什么?
- 了解计算机科学、程序设计和问题解决的基本概念;
- 理解抽象和抽象在问题解决过程中的作用;
- 理解抽象数据类型的概念以及运用
算法 即写出一组解决问题可能出现的任何情况的步步为营的指令。算法通过有线的过程解决问题,是一种解决方案。
程序设计 将算法编码为计算机可执行的表示法或编程语言的过程。
Python基础
为什么要学习算法?
通过研究大量不同的算法,可以发展出模式识别机制,当以后出现相似问题时可以更好的解决掉。
Python是一种支持面向对象的编程范式,意味着Python把数据当做问题解决过程的重点。类 去描述数据的外观(状态)和功能(行为)。“类”类似于抽象数据类型,“类”的用户只能看到数据项的状态和行为。数据项在面向对象的范式里被称为对象(objects)。对象是类的一个实例。
接下来的内容讲述了Python的基本数据类型:
- int和float
- list和set
- string
- dict
列表解析
现在尝试解决一些问题。修改代码,是最终列表只包含字母的单一副本['c','a','t','d','o','g','r','b','i']
,源码如下:
1 | wordlist = ['cat','dog','rabbit'] |
修改后的代码:
1 | wordlist = ['cat','dog','rabbit'] |
其实,作者的本意可能是让使用列表解析的方式来达到目的,但是我们有更好的方法,使用set()
来去重后再转为list()
类型就可以了。
语法
在列表中,存在一种替代方法使用迭代和选择结构创建列表,被称为列表解析。
1 | newlist = [Expression for var in list] |
说明如下:
- newlist 新生成的列表名称
- Expression 表达式,用于计算新列表的元素
- var 变量,值为后面列表的每个元素值
- list 用于生成新列表的原列表
带有条件的解析
1 | newlist = [Expression for var in list if condition] |
condition 条件表达式,用于筛选条件。
解析规则
Python中内置类型的解析规则:
- 如果使用中括号,表示为列表解析;
- 如果使用大括号,表示为集合解析
- 如果使用大括号且元素为k:v形式,表示为字典解析。
1 | # 集合解析 |
工作方式
首先用迭代工具for对容器中的元素进行跌打,每个元素都经过筛选,对符合条件的元素执行外部表达式,每个外部表达式都生成一个新的元素,然后昨晚新列表的一个元素,从而推导出一个新的列表。
列表解析可以让你创建基于某些处理或选择条件的列表。比如创建一个小于10的整数的平方的列表:
1 | sqlist = list() |
上面的代码中,第一段是先循环出一个整数,计算后再塞入list。第二段代码其实也是差不多,先取出一个整数,计算平方后再塞入新建的列表中。列表解析还可以使用选择语句,代码如下:
1 | sqlist = [i*i for i in range(1,11) if i%2 !=0] |
上述代码中取整数后判断是否为奇数,如果是则进行平方计算并塞入新的列表中。
练习——列表解析
删除重复元素:['c', 'a', 't', 'd', 'o', 'g', 'r', 'a', 'b', 'b', 'i', 't']
代码如下:
1 | # 常规方案 |
这里和之前不一样的是,步骤如下:
- 循环取出一个元素;
- 判断元素是否属于定义的newlist;
- 如果不属于则插入到newlist;
- 输出newlist.
练习——函数
编写一个函数,该函数生成一个27个字符长度的字符串,从26个字母和空格中随机选择一个字符。编写另一个函数,比较随机生成的字符串和目标字符串。第三个函数将反复调用生成和比较函数,那么如果所有目标字母都在随机字符串中出现了,那么就完成了。如果字母没有全部出现,那么会生成一个全新的字符串。
- 第一个函数生成随机字符,从26个字母和空格里;
- 第二个函数来比较随机生成的字符和目标字符;
- 第三个函数返回目前为止能匹配上的字符串以及尝试次数。
代码示例:
1 | # 实现匹配出所有字符,并非对应所有字符 |