- 关于作者
- 1.数据类型篇
- 2. 基础语法篇
- 3. 内置函数篇
- 4. 字符串方法
- 5. 排序算法篇
- 6. 简单算法篇
- 7 中等难度算法练习题
- 8 地狱难度算法练习题
关于作者
5年C++，培养了良好的算法功底
5年Python,积累了丰富经验
130道练习题，涵盖基础内容的方方面面
- 第1篇 数据类型篇
- 第2篇 基础语法篇
- 第3篇 内置函数篇
- 第4篇 字符串方法
- 第5篇 排序算法篇
- 第6篇 简单算法篇
- 第7篇 中等难度算法篇
- 地狱难度算法篇
学习过程中，如有问题，可以加QQ群： 211426309 一起讨论
如果你希望有人能够指导你学习python，可以加我微信

1.数据类型篇
本篇的练习题旨在考察你对基本数据类型的理解熟悉程度，适合刚接触python的初学者用来巩固对基础知识的理解
1.1 基本数据类型
1.1.1 逻辑推理练习（类型转换）
不运行程序，说出下面程序的执行结果
1. 4.0 == 4
2. "4.0" == 4
3. bool("1")
4. bool("0")
5. str(32)
6. int(6.26)
7. float(32)
8. float("3.21")
9. int("434")
10. int("3.42")
11. bool(-1)
12. bool("")
13. bool(0)
14. "wrqq" > "acd"
15. "ttt" == "ttt "
16. "sd"*3
17. "wer" + "2322"
答案如下
1. True
2. False
3. True
4. True
5. '32'
6. 6
7. 32.0
8. 3.21
9. 434
10. 会报错
11. True
12. False
13. False
14. True
15. False
16. "sdsdsd"
17. 'wer2322'
关于这些答案，要做到知其然且知其所以然，编程需要精准的知道每一个细节，下面对其中一些可能让你感到困惑的知识点进行讲解
1.1.1.1 bool函数转换规则
bool函数进行转换时，其结果取决于传入参数与True和False的等价关系，只需记住一点即可
0 , 空字符串, None在条件判断语句中等价于False, 其他数值都等价于True
bool函数在做数据类型转换时遵循该原则
1.1.1.2 int("3.42") 为什么会报错
字符串"3.42"可以转成float类型数据3.42, 3.42可以转成int类型数据3，但是字符串"3.42"却不可以直接使用int函数转成3，讲实话，我也觉得这个函数有些不灵活，或许是语言的发明者有自己的考虑吧，咱们对这种问题，不必深究，先做到知道它是什么，将来再去研究为什么
1.1.1.3 字符串大小比较规则
两个字符串在比较大小时，比的不是长度，而是内容
字符串左对齐后，逐个字符依次比较，直到可以分出胜负
1.1.1.4 "sd"*3
"sd"*3 的意思是sd重复3次，生成一个新的字符串
1.1.2 数据类型考察
请说出下面表达式结果的类型
1. "True"
2. "Flase"
3. 4 >= 5
4. 5
5. 5.0
6. True
非常简单的送分题
1. str
2. str
3. bool
4. int
5. float
6. bool
唯一需要解释的是4 >= 5,4比5小，怎么可能大于等于5呢，这是错误的，既然是错的，那么就等于False,False的类型是bool
1.1.3 交互式解释器练习
请在交互式解释器里回答下面的题目
1. 3的5次方
2. 7对2求模
3. 9除5，要求有小数部分
4. 9除5，要求没有小数部分
5. 用程序计算根号16，也就是16的2分之一次方
答案如下
1. 3**5
2. 7%2
3. 9/5
4. 9//5
5. import math
math.sqrt(16)
知识点讲解
- 幂运算用两个， 2的2次方表示为2*2
- 求模运算用%， 其实就是求余数，不知道余数的打电话给小学老师
- 除法中，希望结果有小数部分时用/， 希望只保留整数部分时用 // ,没啥可解释的，请记住他们的区别，懒得记，就别学编程，编程不适合懒惰的人
- 开根号，要用到math模块的sqrt方法，这个题目需要你自己去百度或是谷歌，第一次明确的建议你，一定要好好利用搜索引擎，不会用搜索引擎的程序员，永远是菜鸟
1.2 字符串练习题
1.2.1 字符串内置方法练习
在交互式解释器中完成下列题目
- 将字符串 "abcd" 转成大写
- 计算字符串 "cd" 在 字符串 "abcd"中出现的位置
- 字符串 "a,b,c,d" ，请用逗号分割字符串，分割后的结果是什么类型的？
- "{name}喜欢{fruit}".format(name="李雷") 执行会出错，请修改代码让其正确执行
- string = "Python is good", 请将字符串里的Python替换成 python,并输出替换后的结果
- 有一个字符串 string = "python修炼第一期.html"，请写程序从这个字符串里获得.html前面的部分，要用尽可能多的方式来做这个事情
- 如何获取字符串的长度？
- "this is a book",请将字符串里的book替换成apple
- "this is a book", 请用程序判断该字符串是否以this开头
- "this is a book", 请用程序判断该字符串是否以apple结尾
- "This IS a book"， 请将字符串里的大写字符转成小写字符
- "This IS a book"， 请将字符串里的小写字符，转成大写字符
- "this is a book\n"， 字符串的末尾有一个回车符，请将其删除
在看答案之前，我要非常明确的告诉你，答案所涉及的每一个字符串方法，都是需要你记忆下来的，就像九九乘法表那样熟记于心，这不是要求，而是必须，否则，你凭什么说你会一门编程语言呢？ 聪明从来不自己骗自己！
答案如下
1. "abcd".upper()
2. "abcd".find('cd')
3. "a,b,c,d".split(',')
4. "{name}喜欢{fruit}".format(name="李雷", fruit='苹果')
5. string.replace('Python', 'python')
6. string[0:string.find('.html')] 或者string[0:-5]
7. 使用len函数
8. "this is a book".replace('book', 'apple')
9. "this is a book".startswith('this')
10. "this is a book".endswith('apple')
11. "This IS a book".lower()
12. "This IS a book".upper()
13. "this is a book\n".strip()
这里只对其中2个题目讲解
第4小题的程序直接运行会报错，因为字符串里面有两个需要替换的位置，而format方法里只传入了一个参数，显然是不够
第13小题，strip() 方法用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列， \n 就是换行符，这里又涉及到转义字符这个概念，本篇不做详细讲解，求知欲强的同学可以自己百度一下
1.2.2 逻辑推理练习（字符串）
不用代码，口述回答下面代码的执行结果
string = "Python is good"
- string[1:20]
- string[20]
- string[3:-4]
- string[-10:-3]
- string.lower()
- string.replace("o", "0")
- string.startswith('python')
- string.split()
- len(string)
- string[30]
- string.replace(" ", '')
答案如下
1. 'ython is good'
2. 报错
3. 'hon is '
4. 'on is g'
5. 'python is good'
6. 'Pyth0n is g00d'
7. False
8. ['Python', 'is', 'good']
9. 14
10. 报错
11. 'Pythonisgood'
第2题和第10题都报错，是因为超出了索引范围，字符串长度为14，你去20和30的位置取值，当然会报错
关于切片操作，只需要知道从哪里开始到哪里结束就一定能推导出答案，以string[3:-4]为例，3是开始的位置，-4是结束的位置，但这个范围是左闭右开的，从3开始没错，但不会到-4，而是到-5，更前面的一个位置，python支持负数索引，或者说是反向索引，从右向左从-1开始逐渐减小。
第一题中，做切片的时候是从1开始，到20结束，即便是右开，直到19，也仍然超出了索引范围，为什么不报错呢，这就是语言设计者自己的想法了，切片时，不论是开始位置还是结束位置，超出索引范围都不会报错，我猜，大概是由于切片是一个范围操作，这个范围内有值就切出来，没值返回空字符串就好了。
1.3 列表与元组练习题
1.3.1 列表基础考察
已知一个列表
lst = [1,2,3,4,5]
- 求列表的长度
- 判断6 是否在列表中
- lst + [6, 7, 8] 的结果是什么？
- lst*2 的结果是什么
- 列表里元素的最大值是多少
- 列表里元素的最小值是多少
- 列表里所有元素的和是多少
- 在索引1的后面新增一个的元素10
- 在列表的末尾新增一个元素20
答案如下
1. len(lst)
2. 6 in lst
3. [1,2,3,4,5,6,7,8]
4. [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
5. max(lst)
6. min(lst)
7. sum(lst)
8. lst.insert(1, 10)
9. lst.append(20)
以上都是对列表基础操作，所用到的每一个函数，列表的每一个方法，都是需要你熟记于心的
1.3.2 修改列表
lst = [1, [4, 6], True]
请将列表里所有数字修改成原来的两倍
答案如下
lst[0] = 2
lst[1][0] = 4
lst[1][1] = 12
你以为存在一个函数，其功能便是将列表里所有的数据都变成原来的两倍，这样才显得变成语言是一个非常神奇的东西，但是很遗憾的告诉你，那些神奇的东西都是程序员自己实现的。
想要修改列表里的数据，必须通过索引对其重新赋值，上面的方法很low，你也可以写一个函数来实现这个功能，我们假设要处理的列表里只int,float,bool,和list数据，不管嵌套基层list，这个函数都应该能正确处理，下面是一段示例代码
def double_list(lst):
for index, item in enumerate(lst):
if isinstance(item, bool):
continue
if isinstance(item, (int, float)):
lst[index] *= 2
if isinstance(item, list):
double_list(item)
if __name__ == '__main__':
lst = [1, [4, 6], True]
double_list(lst)
print(lst)
1.3.3 元组概念考察
写出下面代码的执行结果和最终结果的类型
- (1, 2)*2
- (1, )*2
- (1)*2
答案如下
1. (1, 2, 1, 2)
2. (1, 1)
3. 2
第一题应该没有异议，关键是第2题和第3题，元组里只有一个数据时，必须有逗号，如果没有逗号，就变成了第3题的形式，第3题本质上是1*2,那对小括号就如同我们小学学过的小括号一样，只是为了体现运算优先级而已。
当元组只有一个数据时，如果不省略了逗号，那么小括号的作用就不再是表示元组，而是表示运算优先级
1.3.4 合并列表
lst = [1,2,3]
lst2 = [4,5,6]
不使用 + 号运算符，将lst2合并到lst的末尾，并思考，这个过程中，是否产生了新的列表
答案
lst.extend(lst2)
这个过程中不会产生新的列表，最直观的检验方式就是print(id(lst)),合并前后，lst的内存地址都没有发生变化，只是列表里的内容发生了变化
1.3.5 合并字符串
str1 = "1,2,3"
str2 = "4,5,6"
请将str2合并到str1的末尾，并思考，这个过程中，是否产生了新的字符串
答案
str1 += str2
这个过程中，产生的新的字符串，字符串是不可变对象，从字面上理解，似乎str1的内容发生变化了，但本质上是产生了新的字符串并赋值给str1， print(str1)， 合并前后的内存地址是不一样的
1.3.6 统计练习
列表lst 内容如下
lst = [2, 5, 6, 7, 8, 9, 2, 9, 9]
请写程序完成下列题目
- 找出列表里的最大值
- 找出列表里的最小值
- 找出列表里最大值的个数
- 计算列表里所有元素的和
- 计算列表里元素的平均值
- 计算列表的长度
- 找出元素6在列表中的索引
答案
1. max(lst)
2. min(lst)
3. lst.count(max(lst))
4. sum(lst)
5. sum(lst)/float(len(lst))
6. len(lst)
7. lst.index(6)
这道题考察的是你对内置函数的理解和运用
下面的题目不允许写代码，仅凭思考来回答
- lst[2:4] 的值是什么
- lst[1: -3]的值是什么
- lst[-5]的值是什么
- lst[:-4] 的值是什么
- lst[-4:] 的值是什么
这个题目主要考察你对列表切片操作的理解
1. [6, 7]
2. [5, 6, 7, 8, 9]
3. 8
4. [2, 5, 6, 7, 8]
5. [9, 2, 9, 9]
列表的切片操作，最关键的一点在于左闭右开，结束位置的数据不会列入结果中
1.3.7 列表操作练习
列表lst 内容如下
lst = [2, 5, 6, 7, 8, 9, 2, 9, 9]
请写程序完成下列操作
- 在列表的末尾增加元素15
- 在列表的中间位置插入元素20
- 将列表[2, 5, 6]合并到lst中
- 移除列表中索引为3的元素
- 翻转列表里的所有元素
- 对列表里的元素进行排序，从小到大一次，从大到小一次
答案
1. lst.append(15)
2. lst.insert(len(lst)//2, 20)
3. lst.extend([2, 5, 6])
4. lst.remove(lst[3])
5. lst = lst[::-1]
6. lst.sort() lst.sort(reverse=True)
1.3.8 复杂列表练习
列表lst 内容如下
lst = [1, 4, 5, [1, 3, 5, 6, [8, 9, 10, 12]]]
不写任何代码，仅凭思考来回答下列问题
- 列表lst的长度是多少
- 列表lst中有几个元素
- lst[1] 的数据类型是什么
- lst[3]的数据类型是什么
- lst[3][4] 的值是什么
- 如果才能访问到 9 这个值
- 执行lst[3][4].append([5, 6])后，列表lst的内容是什么，手写出来
- lst[-1][-1][-2]的值是什么
- lst[-2]的值是什么
- len(lst[-1]) 的值是什么
- len(lst[-1][-1])的值是什么
- lst[-1][1:3] 的值是什么
- lst[-1][-1][1:-2]的值是什么
第1题和第2题其实是一个意思，原本统计列表里数据个数不是什么难事，可一旦出现了嵌套列表的情况，有人就分不清了，列表里的数据是以逗号分隔的，lst[3] 是一个列表，其余都是int类型数据，因此lst的长度是4
第3题，lst[1] = 4,是int类型数据
第4题，lst[3] 的数据类型是列表
第5题，lst[3]的值是[1, 3, 5, 6, [8, 9, 10, 12]]，仍然是一个列表，其索引为4的数据是[8, 9, 10, 12]，是列表
第6题，lst[3][4][1]
第7题，[1, 4, 5, [1, 3, 5, 6, [8, 9, 10, 12, [5, 6]]]],参考5，6两个题目的解答
第8题，lst[-1]的值是[1, 3, 5, 6, [8, 9, 10, 12]]， 再次取索引为-1的数据为[8, 9, 10, 12]，取索引为-2的数据为10
第9题，5
第10题，5
第11题，4
第12题， [3, 5]， lst[-1]的值是[1, 3, 5, 6, [8, 9, 10, 12]]
第13题，[9]， lst[-1][-1]的值是[8, 9, 10, 12]，切片起始位置索引是1，值为9，结束位置是-2，值为10，由于左闭右开，最终结果是[9]
1.4 字典练习题
1.4.1 字典基本操作
字典内容如下
dic = {
'python': 95,
'java': 99,
'c': 100
}
用程序解答下面的题目
- 字典的长度是多少
- 请修改'java' 这个key对应的value值为98
- 删除 c 这个key
- 增加一个key-value对，key值为 php, value是90
- 获取所有的key值，存储在列表里
- 获取所有的value值，存储在列表里
- 判断 javascript 是否在字典中
- 获得字典里所有value 的和
- 获取字典里最大的value
- 获取字典里最小的value
- 字典 dic1 = {'php': 97}， 将dic1的数据更新到dic中
第1题，len(dic),结果为3
第2题，dic['java'] = 98,对字典里value的修改，必须通过key才可以
第3题，del dic['c']
第4题，dic['php'] = 90
第5题，lst = list(dic.keys())
第6题，lst = list(dic.values())
第7题，'javascript' in dic
第8题，sum(dic.values())
第9题，max(dic.values())
第10题，min(dic.values())
第11题，dic.update(dic1)
1.4.2 字典应用（买水果）
小明去超市购买水果，账单如下
苹果 32.8
香蕉 22
葡萄 15.5
请将上面的数据存储到字典里，可以根据水果名称查询购买这个水果的费用
很简单哦，用水果名称做key，金额做value，创建一个字典
info = {
'苹果':32.8,
'香蕉': 22,
'葡萄': 15.5
}
1.4.3 字典应用（买水果2）
小明，小刚去超市里购买水果
小明购买了苹果，草莓，香蕉，一共花了89块钱，，小刚购买了葡萄，橘子，樱桃，一共花了87块钱
请从上面的描述中提取数据，存储到字典中，可以根据姓名获取这个人购买的水果种类和总费用。
以姓名做key，value仍然是字典
info = {
'小明': {
'fruits': ['苹果', '草莓', '香蕉'],
'money': 89
},
'小刚': {
'fruits': ['葡萄', '橘子', '樱桃'],
'money': 87
}
}
1.5 集合练习题
集合间的运算
lst1 = [1, 2, 3, 5, 6, 3, 2]
lst2 = [2, 5, 7, 9]
- 哪些整数既在lst1中，也在lst2中
- 哪些整数在lst1中，不在lst2中
- 两个列表一共有哪些整数
虽然题目一直在问两个列表，但用列表解答这3个题目效率很低，你应该用集合
lst1 = [1, 2, 3, 5, 6, 3, 2]
lst2 = [2, 5, 7, 9]
set1 = set(lst1)
set2 = set(lst2)
# 哪些整数既在lst1中，也在lst2中
print(set1.intersection(set2))
# 哪些整数在lst1中，不在lst2中
print(set1.difference(set2))
# 两个列表一共有哪些整数
print(set1.union(set2))
2. 基础语法篇
基础语法篇的练习题，不涉及复杂的逻辑推理，旨在检查你对基础语法的掌握情况
2.1 if 条件语句
2.1.1 单个条件分支
使用input函数接收用户的输入，如果用户输入的整数是偶数，则使用print函数输出"你输入的整数是:{value}, 它是偶数", {value}部分要替换成用户的输入。
完成这个练习题需要你掌握下面4个知识点
- input函数的作用
- 字符串转int
- 取模运算
- 字符串格式化
value = input("请输入一个整数:")
i_value = int(value)
if i_value % 2 == 0:
print("你输入的整数是:{value}, 它是偶数".format(value=value))
2.1.2 if ... else ...
使用input函数接收用户的输入，如果用户输入的整数是偶数，则使用print函数输出"你输入的整数是:{value}, 它是偶数",如果是奇数，则使用print函数输出"你输入的整数是:{value}, 它是奇数"
value = input("请输入一个整数:")
i_value = int(value)
if i_value % 2 == 0:
print("你输入的整数是:{value}, 它是偶数".format(value=value))
else:
print("你输入的整数是:{value}, 它是奇数".format(value=value))

2.1.3 多条件分支
使用input函数接收用户的输入数据，如果用户输入python，则输出90， 如果用户输入java,输出95，如果用户输入php，输出85，其他输入，程序输出0
value = input("请输入一个整数:")
if value == 'python':
print(90)
elif value == 'java':
print(95)
elif value == 'php':
print(85)
else:
print(0)

2.1.4 复杂条件判断
使用input函数接收用户的输入，如果输入的数据不可以转换成int类型数据，则输出"无法使用int函数转换"，如果可以，则将用户的输入转成int类型数据并继续判断。
如果输入数据是奇数，则将其乘以2并输出，如果是偶数，则判断是否能被4整除，如果可以则输出被4整除后的值，若不能被4整数，则判断是否大于20，如果大于20则输出与20的差值，如果小于等于20，则直接输出该值
程序代码如下
value = input("请输入一个整数:")
if not value.isdigit():
print('无法使用int函数转换')
else:
i_value = int(value)
if i_value % 2 == 1:
print(i_value*2)
elif i_value % 4 == 0:
print(i_value / 4)
elif i_value > 20:
print(i_value - 20)
else:
print(i_value)
画出程序流程图如下

2.2 for循环
2.2.1 range函数基本使用
range(3, 20, 4)
range(10, -3, -4)
range(10, 5)
range(2, 12)
不使用程序，说出上面4个range产生的整数序列
2.2.2 利用range函数遍历列表
lst = [1, 3, 5, 2, 7, 9]
for index in range(len(lst)):
print(lst[index])
- 参照上面的代码，从后向前遍历
- 遍历输出列表里的所有偶数
- 遍历列表，输出大于3的奇数
2.2.3 使用for循环遍历字典
遍历字典有两种方法
方法1
dic = {
'python': 90,
'java': 95
}
for key in dic:
print(key, dic[key])
方法2
dic = {
'python': 90,
'java': 95
}
for key, value in dic.items():
print(key, value)
2.2.4 continue练习
2.2.5 break练习
从列表 lst = [1, 3, 5, 2, 7, 9, 10] 中寻找1个偶数并输出，代码如下
lst = [1, 3, 5, 2, 7, 9, 10]
for item in lst:
if item % 2 == 0:
print(item)
break
题目要求寻找一个偶数，当找到这个偶数后，循环就可以终止了，使用break可以终止本次循环，你可以去掉代码中的break，再次执行代码，观察代码的执行效果
2.2.6 寻找列表中的最大值,最小值
lst = [3, 6, 1, 8, 1, 9 , 2]
max_value = lst[0]
for item in lst:
if item > max_value:
max_value = item
print(max_value)
- 参照上面的代码，写代码寻找列表的最小值
- 写代码寻找列表里的最小偶数
- 写代码寻找列表里的最大奇数
2.2.7 寻找组合
lst1 = [3, 6, 1, 8, 1, 9 , 2]
lst2 = [3, 1, 2, 6, 4, 8, 7]
for item1 in lst1:
for item2 in lst2:
if item1 + item2 == 10:
print((item1, item2))
上面的代码利用嵌套循环，从两个列表里各取1个数，如果这两个数的和等于10，则以元组的方式输出这两个数
- 参照上面的代码，寻找两个数的差的绝对值等于2的组合
- 两个列表里各取出一个值，item1和item2， 请计算item1*item2的最大值
2.3 while循环
2.3.1 奇偶数判断
使用input函数接收用户输入的整数，如果是偶数，则使用print函数输出"你输入的是一个偶数",反之输出"你输入的是一个奇数"，用户可以输入多次，直到输入quit时程序退出
while True:
input_str = input("请输入一个正整数，想退出程序请输入 quit:")
if input_str == "quit":
break
number = int(input_str)
if number % 2 == 0:
print("你输入的是一个偶数")
else:
print("你输入的是一个奇数")
2.3.2 for循环与while循环嵌套
已知 lst = [2, 3, 4]
依次要求用户输入2，3，4 的整数倍，先让用户输入2的倍数，如果用户输入的正确，输出“输入正确”，否则输出 “输入错误”，如果用户输入quit，则停止当前的输入，让用户输入3的倍数，输入3的倍数的过程中，如果用户输入quit，则让用户输入4的倍数
lst = [2, 3, 4]
for item in lst:
while True:
input_str = input("请输入{number}的倍数,想停止输入时，输入quit:".format(number=item))
if input_str == 'quit':
break
number = int(input_str)
if number % item == 0:
print("输入正确")
else:
print("输入错误")
2.3.3 continue的好处
break是跳出循环体，continue是跳过continue语句后面的代码块，循环并不停止
题目要求：
使用input函数接受用户的输入，如果用户输入的数值小于等于10，则判断是奇数还是偶数，如果数值大于10，则输出“输入大于10，不判断奇偶”,用户输入quit，结束程序
while True:
input_str = input("请输入一个正整数,如果想停止程序，输入quit:")
if input_str == 'quit':
break
number = int(input_str)
if number > 10:
continue
if number % 2 == 0:
print("输入为偶数")
else:
print("输入为奇数")
当number大于10 的时候，后面的那4行代码就不会被执行，直接进入到下一次循环。
上面的代码，也可以不使用continue
while True:
input_str = input("请输入一个正整数,如果想停止程序，输入quit:")
if input_str == 'quit':
break
number = int(input_str)
if number < 10:
if number % 2 == 0:
print("输入为偶数")
else:
print("输入为奇数")
两段代码，实现了一样的功能，但对比一下不难发现，使用了不使用continue，代码的嵌套层次更深，如果嵌套多了，会让代码变得难以阅读，难以管理
但使用continue，就可以减少代码层次，代码的理解和管理都更容易，大于10的时候，continue跳过后面的代码，在逻辑思考时，这种一刀两断的方法让思路更清晰。
3. 内置函数篇
本篇的练习题不是考察你如何使用python的内置函数，而是通过实现与内置函数相同功能的函数来达到锻炼提升编码能力的目的
3.1 abs
题目要求
abs函数返回数字的绝对值，请实现下面的函数，模仿abs函数的功能,返回数字的绝对值
def my_abs(number):
pass
思路分析
处于程序健壮性考虑，要对传入的number参数进行检查，判断其类型是否为数字类型，float和int是比较常用的数据类型，复数类型基本接触不到，因此不考虑。
判断变量类型，可以使用isinstance函数，该函数的第一个参数是需要检查类型的对象，第二个参数可以是数据类型，也可以是一个元组，元组里是多个数据类型，只要满足其中一个就返回True
如果number的数值小于0，乘以-1就得到了绝对值
示例代码
def my_abs(number):
if not isinstance(number, (float, int)):
return number
if number < 0:
number *= -1
return number
if __name__ == '__main__':
print(my_abs(-3))
print(my_abs(-3.9))
print(my_abs(54.3))
3.2 sum
题目要求
sum函数可以获取列表所有数据的总和，模仿这个功能实现下面的函数，
def my_sum(lst):
"""
返回列表里所有数据的总和
如果列表里有非数字类型的数据，忽略不管
:param lst:
:return:
"""
pass
思路分析
- 对传入的参数lst，要进行类型检查
- 遍历列表，遇到数字类型的数据就进行加和操作
示例代码
def my_sum(lst):
"""
返回列表里所有数据的总和
:param lst:
:return:
"""
sum_res = 0
if not isinstance(lst, list):
return sum_res
for item in lst:
if isinstance(item, (float, int)):
sum_res += item
return sum_res
if __name__ == '__main__':
lst = [3, 4, '43', 5.4]
print(my_sum(lst))
3.3 max
max函数返回序列中的最大值，传入的参数可以是列表，也可以是元组，实现下面的函数，实现同样的功能，如果序列里有非数字类型的数据，可以忽略,如果序列是空的，可以直接返回None
def my_max(seq):
"""
返回序列里的最大值
:param lst:
:return:
"""
思路分析
对传入的参数seq要进行类型检查，如果既不是列表，也不是元组，那么就返回None
如果序列是空的，也可以直接返回None
遍历序列里的元素，如果数据的类型不属于数字类型，那么就忽略该数据
示例代码
def my_max(seq):
"""
返回序列里的最大值
:param lst:
:return:
"""
max_value = None
if not isinstance(seq, (list, tuple)):
return max_value
if len(seq) == 0:
return max_value
max_value = seq[0]
for item in seq:
if not isinstance(item, (float, int)):
continue
if item > max_value:
max_value = item
return max_value
if __name__ == '__main__':
lst = [3, 4, '43', 5.4]
print(my_max(lst))
3.4 min
min函数返回序列中的最小值，传入的参数可以是列表，也可以是元组，实现下面的函数，实现同样的功能，如果序列里有非数字类型的数据，可以忽略
def my_min(seq):
"""
返回序列里的最小值
:param lst:
:return:
"""
pass
思路分析
整体思路与3.3的my_max函数相同
示例代码
def my_min(seq):
"""
返回序列里的最小值
:param lst:
:return:
"""
min_value = None
if not isinstance(seq, (list, tuple)):
return min_value
if len(seq) == 0:
return min_value
min_value = seq[0]
for item in seq:
if not isinstance(item, (float, int)):
continue
if item < min_value:
min_value = item
return min_value
if __name__ == '__main__':
lst = [3, 4, '43', 5.4]
print(my_min(lst))
3.5 int
内置函数int，可以将float,全是数字的字符串转成int类型的数据，为了降低难度，这个练习题只要求你实现其中一种功能，将全是由数字组成的字符串转成int类型数据，例如将字符串"432" 转成整数432，函数定义如下
def my_int(string):
"""
将字符串string转成int类型数据
不考虑string的类型,默认就是符合要求的字符串
传入字符串"432" 返回整数432
:param string:
:return:
"""
pass
思路分析
题目的要求非常明确，只将"432"这种全是由数字组成的字符串转成int类型数据，这样就没什么难度了
遍历字符串，每个将字符串里的每个字符转成int类型的数值，这个过程可以使用字典来完成，建立一个字典，字符串的数字做key，int类型的数字做value,例如下面的字典
str_int_dic = {
'0': 0,
'1': 1,
'2': 2,
'3': 3,
'4': 4,
'5': 5,
'6': 6,
'7': 7,
'8': 8,
'9': 9
}
得到数字后，还得考虑这个数字是哪一位的，是千位还是百位，这里可以使用一个技巧，遍历的过程是从左向右进行的，设置一个变量保存转换后的int数据，初始值赋为0，每一次循环后，都用这个变量乘10再加上所遍历到数值，这样就巧妙的解决了位数问题。
示例代码
str_int_dic = {
'0': 0,
'1': 1,
'2': 2,
'3': 3,
'4': 4,
'5': 5,
'6': 6,
'7': 7,
'8': 8,
'9': 9
}
def my_int(string):
"""
将字符串string转成int类型数据
不考虑string的类型,默认就是符合要求的字符串
传入字符串"432" 返回整数432
:param string:
:return:
"""
res = 0
for item in string:
int_value = str_int_dic[item]
res = res*10 + int_value
return res
if __name__ == '__main__':
print(my_int('432'))
3.6 str
题目要求
内置函数str的功能非常强大，想要模仿实现一个相同功能的函数是非常困难的，因此本练习题只要求你将int类型的数据转换成字符串，实现下面的函数
def my_str(int_value):
"""
将int_value转换成字符串
:param int_value:
:return:
"""
pass
思路分析
int类型的数据，不能像字符串那样使用for循环进行遍历，但可以结合 / 和 % 操作符从个位向高位进行遍历，获取到某一位的数字之后，将其转换成字符串，append到一个列表中。
遍历结束之后，翻转列表，用空字符串join这个列表，即可得到转换后的字符串。
单个数字，如何转成字符串呢？可以使用3.6中类似的方法，创建一个字典，数字为key，字符串数字为value
int_str_dict = {
0: '0',
1: '1',
2: '2',
3: '3',
4: '4',
5: '5',
6: '6',
7: '7',
8: '8',
9: '9',
}
获得某一位数字后，通过字典获得对应的字符串，此外，还可以通过ascii码表来获得与之对应的数字字符。以3为例，chr(3+48)即可得到字符串'3'，其原理，字符串3的ascii码表十进制数值为51，恰好比3大48，其他数值，也同样如此。
大致的思路已经清晰了，接下来是一些细节问题
- 如果传入的参数是0，那么直接返回字符串'0'
- 如果传入的参数是负数，需要标识记录，最后在列表里append一个'-' 字符串。
- lst = [1, 2, 3],想要翻转，lst = lst[::-1]
示例代码
def my_str(int_value):
"""
将int_value转换成字符串
:param int_value:
:return:
"""
if int_value == 0:
return '0'
lst = []
is_positive = True
if int_value < 0:
is_positive = False
int_value = abs(int_value)
while int_value:
number = int_value%10
int_value //= 10
str_number = chr(number+48)
lst.append(str_number)
if not is_positive:
lst.append('-')
lst = lst[::-1]
return ''.join(lst)
if __name__ == '__main__':
print(my_str(0))
print(my_str(123))
print(my_str(-123))
3.7 float
题目要求
为了降低难度，本题目只要求你将字符串转换成float类型的数据，且字符串都是符合”xx.xx“格式的字符串，例如"34.22"
def my_float(string):
"""
将字符串string转换成float类型数据
:param string:
:return:
"""
pass
题目分析
使用split函数，以"."做分隔符，可以将字符串分割为两部分，整数部分和小数部分，这两个部分可以分别用3.5 中的my_int 函数进行处理，以"34.22"为例，分别得到整数34 和22，对于22，不停的乘以0.1，知道它的数值小于1，就得到了小数部分
示例代码
str_int_dic = {
'0': 0,
'1': 1,
'2': 2,
'3': 3,
'4': 4,
'5': 5,
'6': 6,
'7': 7,
'8': 8,
'9': 9
}
def my_int(string):
"""
将字符串string转成int类型数据
不考虑string的类型,默认就是符合要求的字符串
传入字符串"432" 返回整数432
:param string:
:return:
"""
res = 0
for item in string:
int_value = str_int_dic[item]
res = res*10 + int_value
return res
def my_float(string):
"""
将字符串string转换成float类型数据
:param string:
:return:
"""
arrs = string.split('.')
int_value = my_int(arrs[0])
float_value = my_int(arrs[1])
while float_value > 1:
float_value *= 0.1
return int_value + float_value
if __name__ == '__main__':
print(my_float("34.22"))
3.8 len
题目要求
内置函数可以获得可迭代对象的长度，例如字符串，列表，元组，字典，集合。实现一个类似功能的函数，获得数据的长度。
def my_len(obj):
"""
获得obj对象的长度
:param obj:
:return:
"""
pass
思路分析
使用for循环遍历对象，循环的次数就是这个对象的长度，只需要一个变量来保存循环的次数就可以了。
对obj参数的检查，可以使用isinstance判断是否为列表，元组，字典，集合，字符串中的某一个，更为简便的做法，这些对象都是可迭代对象，isinstance(obj, Iterable) 可以判断obj是否为可迭代对象
示例代码
from collections import Iterable
def my_len(obj):
"""
获得obj对象的长度
:param obj:
:return:
"""
if not isinstance(obj, Iterable):
return None
length = 0
for item in obj:
length += 1
return length
if __name__ == '__main__':
print(my_len('232'))
print(my_len([3, 4, 2, 1]))
print(my_len({'a': 4, 'b': 4}))
print(my_len((3, 5, 6, 6, 3)))
print(my_len(set([3, 5, 6, 6, 3])))
3.9 enumerate
题目要求
enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中，下面是使用示例
lst = ['a', 'b', 'c']
for index, item in enumerate(lst):
print(index, item)
程序输出
0 a
1 b
2 c
请仿造该功能实现下面的函数
def my_enumerate(lst):
"""
实现和enumerate 类似的功能
:param lst:
:return:
"""
pass
思路分析
想要实现这个函数，只需两行代码就可以了,不过，这需要你对生成器有一定的理解和认识。
一个函数里如果出现了yield关键字，那么这个函数就是生成器函数，该函数返回的是一个生成器。
yield有着和return相似的功能，都会将数据返回给调用者，不同之处在于，return执行后，函数结束了，而yield执行后，会保留当前的状态，等到下一次执行时，恢复之前的状态，继续执行。
在函数内部，使用for循环通过索引
遍历lst, 使用yield返回索引和索引位置上的元素。
示例代码
def my_enumerate(lst):
"""
实现和enumerate 类似的功能
:param lst:
:return:
"""
for i in range(len(lst)):
yield i, lst[i]
lst = ['a', 'b', 'c']
for index, item in my_enumerate(lst):
print(index, item)
3.10 all
题目要求
all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 True，示例代码如下
lst = [True, False, True]
print(all(lst))
最终输出结果是False,实现下面的函数，完成类似的功能
def my_all(seq):
"""
如果列表里所有的元素都是True,则函数返回True,反之,返回False
:param seq: 列表
:return:
"""
pass
为了简化难度，参数seq默认只传列表
思路分析
老规矩，使用for循环遍历列表，当前遍历到的元素如果是False，直接返回False
示例代码
def my_all(seq):
"""
如果列表里所有的元素都是True,则函数返回True,反之,返回False
:param seq: 列表
:return:
"""
for item in seq:
if not item:
return False
return True
if __name__ == '__main__':
print(my_all([True, False, True]))
3.11 any
题目要求
any函数用于判断给定的可迭代参数 iterable 中的所有元素是否至少有一个为True
示例代码
lst = [True, False, False]
print(any(lst))
输出结果为True
实现下面的函数，完成类似的功能，默认传入的参数是列表
def my_any(lst):
"""
列表lst中有一个True,则函数返回True
:param lst:
:return:
"""
pass
思路分析
老规矩，遍历列表，当前遍历到的元素如果为True，则函数返回True
示例代码
def my_any(lst):
"""
列表lst中有一个True,则函数返回True
:param lst:
:return:
"""
for item in lst:
if item:
return True
return False
if __name__ == '__main__':
print(my_any([True, False, False]))
3.12 bin
函数bin可以获得整数的二进制形式，示例代码如下
print(bin(10))
程序输出结果为0b1010。
实现下面的函数，完成相同的功能，为了降低难度，你的算法只需要考虑正整数，而且二进制前面不需要加0b
def my_bin(value):
"""
返回正整数value的二进制形式
:param value:
:return:
"""
思路分析
在算法面试中，有一道题目经常被使用，它要求应聘者计算一个整数的二进制中1的个数。解决的思路是判断二进制最后一位是否为1，如果为1，则计数器加1，判断完成后，整数向右位移一位（使用位运算符 >>） ，继续判断二进制的最后一位是否为1.
本练习题可以采用相同的思路
示例代码
def my_bin(value):
"""
返回正整数value的二进制形式
:param value:
:return:
"""
lst = []
while value:
if value % 2 == 1:
lst.append('1')
else:
lst.append('0')
value = value >>1
lst = lst[::-1]
return ''.join(lst)
print(bin(10))
if __name__ == '__main__':
print(my_bin(3))
print(my_bin(8))
print(my_bin(10))
4. 字符串方法
4.1 find
def my_find(source, target, start=0):
"""
返回字符串source中 子串target开始的位置， 从start索引开始搜索
如果可以找到多个，返回第一个
:param source:
:param target:
:param start:
:return:
"""
if not source or not target:
return -1
# 不合理的搜索起始位置
if start < 0 or start >= len(source):
return -1
if len(target) > len(source):
return -1
for index in range(start, len(source) - len(target)+1):
t_index = 0
while t_index < len(target):
if target[t_index] == source[t_index+index]:
t_index += 1
else:
break
if t_index == len(target):
return index
return -1
if __name__ == '__main__':
print(my_find('this is a book', 'this'))
print(my_find('this is a book', 'this', start=1))
print(my_find('this is a book', 'book'))
print(my_find('this is a book', 'k', start=10))
print(my_find('this is a book', 'book', start=10))
print(my_find('this is a book', 'a', start=3))
4.2 replace
def my_replace(source, oldsub, newsub):
"""
将字符串里所有的oldsub子串替换成newsub
:param source:
:param old:
:param new:
:return:
"""
if not source or not oldsub:
return source
new_string = ""
start_index = 0
index = my_find(source, oldsub, start=start_index)
while index != -1:
new_string += source[start_index:index] + newsub
start_index = index+len(oldsub)
index = my_find(source, oldsub, start=start_index)
new_string += source[start_index:]
return new_string
def my_find(source, target, start=0):
"""
返回字符串source中 子串target开始的位置， 从start索引开始搜索
如果可以找到多个，返回第一个
:param source:
:param target:
:param start:
:return:
"""
if not source or not target:
return -1
# 不合理的搜索起始位置
if start < 0 or start >= len(source):
return -1
if len(target) > len(source):
return -1
for index in range(start, len(source) - len(target)+1):
t_index = 0
while t_index < len(target):
if target[t_index] == source[t_index+index]:
t_index += 1
else:
break
if t_index == len(target):
return index
return -1
if __name__ == '__main__':
print(my_replace('this is a book', 'this', 'it'))
print(my_replace('this is a this book', 'this', 'it'))
print(my_replace('this is a this bookthis', 't2his', 'it'))
4.3 split
def my_find(source, target, start=0):
"""
返回字符串source中 子串target开始的位置， 从start索引开始搜索
如果可以找到多个，返回第一个
:param source:
:param target:
:param start:
:return:
"""
if not source or not target:
return -1
# 不合理的搜索起始位置
if start < 0 or start >= len(source):
return -1
if len(target) > len(source):
return -1
for index in range(start, len(source) - len(target)+1):
t_index = 0
while t_index < len(target):
if target[t_index] == source[t_index+index]:
t_index += 1
else:
break
if t_index == len(target):
return index
return -1
def my_split(source, sep, maxsplit=-1):
"""
以sep分割字符串source
:param source:
:param sep:
:param maxsplit:
:return:
"""
if not source or not sep:
return []
lst = []
max_split_count = maxsplit if maxsplit >0 else len(source)
split_count = 0
start_index = 0
index = my_find(source, sep, start=start_index)
while split_count < max_split_count and index != -1:
sep_str = source[start_index:index]
lst.append(sep_str)
split_count += 1
start_index = index + len(sep)
index = my_find(source, sep, start=start_index)
sep_str = source[start_index:]
lst.append(sep_str)
return lst
if __name__ == '__main__':
print(my_split("1,3,4", ','))
print(my_split("1,,3,,4", ',,'))
print(my_split("abcadae", 'a'))
print(my_split("abcadae", 'a', maxsplit=2))
print(my_split("aaaa", 'a'))
4.4 字符串大写转小写
题目要求
实现函数
def lower(string):
"""
将字符串string里所有的大写字母改成小写字母，并返回一个新的字符串
:param string:
:return:
"""
思路分析
实现大小写转换，首先要能识别出一个字符是否为大写字母，你可以在得到这个字符后，判断其是否在A和Z之间，更专业的办法是通过ord 函数获得这个字符的ASCII码表的十进制数值，判断其是否在65和90之间。
获得字符的ASCII码表的十进制数值，其目的不仅仅是判断它是否为大写字母，第二个目的是通过这个十进制数值与32相加，来获得大写字母所对应的小写字母的十进制数值，这样，才能准确的转换成小写字母。
我在程序里使用list函数将字符串转成列表，之所以这样做，是因为字符串是不可变类型的数据，无法直接修改，只好先将其转成列表，将列表里的大写字母转成小写字母，再将列表转成字符串。
示例代码
def lower(string):
"""
将字符串string里所有的大写字母改成小写字母，并返回一个新的字符串
:param string:
:return:
"""
if not string:
return None
lst = list(string)
for index, item in enumerate(lst):
ascii_index = ord(item)
if 65 <= ascii_index <= 90:
s = chr(ascii_index+32)
lst[index] = s
return ''.join(lst)
if __name__ == '__main__':
print(lower('232rSFD'))
4.5 判断字符串是否全部为小写字母
题目要求
实现函数
def islower(string):
"""
如果字符串string 里所有区分大小写的字符都是小写，则返回True
:param string:
:return:
"""
pass
比如传入字符串 "iwj32as"，函数应该返回True
思路分析
字符串里，常见的只有26个英文字母是区分大小写的，因为，咱们只关心英文字母即可。
遍历字符串，逐个字符进行检查，获得其ASCII码表里的十进制数值，如果该数值在65到90之间，一定是大写字母，此时返回False，如果for循环结束后，仍然没有返回False，那么就说明，字符串里没有大写字母，可以返回True
示例代码
def islower(string):
"""
如果字符串string 里所有区分大小写的字符都是小写，则返回True
:param string:
:return:
"""
if not string:
return False
for item in string:
if 65 <= ord(item) <= 90:
return False
return True
if __name__ == '__main__':
print(islower('232r'))
4.6 实现isdigit
题目要求
实现函数isdigit， 判断字符串里是否只包含数字0~9
def isdigit(string):
"""
判断字符串只包含数字
:param string:
:return:
"""
pass
思路分析
遍历字符串，对每个字符做检查，如果都是0到9的某个数值，那么函数返回True，只要有一个不是0到9，就返回False。
如何确定一个字符是不是0到9中的某一个呢，方法很多，你可以用if条件判断语句判断字符是否在列表['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']中，也可以像我下面示例代码一样，使用ord函数获得字符的ASCII编码对应的10进制数值，接着判断是否在48到57之间。
示例代码
def isdigit(string):
"""
判断字符串只包含数字
:param string:
:return:
"""
if not string:
return False
for item in string:
if not (48 <= ord(item) <= 57):
return False
return True
if __name__ == '__main__':
print(isdigit('232'))
print(isdigit('232r'))
print(isdigit(''))
4.7 startswith
题目要求
实现函数is_startswith，如果字符串source是以substr开头的，则函数返回True,反之返回False
def is_startswith(source, substr):
"""
判断字符串source是否以substr开头
:param source:
:param substr:
:return:
"""
pass
思路分析
函数首先要判断传入的参数是否合法，这里默认传入的都是字符串，那么我们要需要判断字符串是否有空串的情况
如果substr的长度大于source的长度，直接返回False
从索引0开始，遍历substr,从source上获得相同索引的字符，两者进行比较，只要有一个字符不相同，则可以立即返回False
示例代码
def is_startswith(source, substr):
"""
判断字符串source是否以substr开头
:param source:
:param substr:
:return:
"""
if not source or not substr:
return False
if len(substr) > len(source):
return False
for index, item in enumerate(substr):
if item != source[index]:
break
else:
return True # 如果for循环不是因为break结束的，就会进入到else语句块
return False
if __name__ == '__main__':
print(is_startswith("python", 'py'))
4.8 endswith
题目要求
实现函数is_endswith，判断字符串source是否以substr结尾
def is_endswith(source, substr):
"""
判断字符串source 是否以substr结尾
:param source:
:param substr:
:return:
"""
pass
思路分析
这个练习题的解法其实和is_startswith函数相差无几，所不同的是，在is_startswith函数中，要从索引0开始进行相同位置字符的比较，而现在，是要判断是否以substr结尾，所以我们从索引len(source) - len(substr)开始逐一进行比较
示例代码
def is_endswith(source, substr):
"""
判断字符串source 是否以substr结尾
:param source:
:param substr:
:return:
"""
if not source or not substr:
return False
if len(substr) > len(source):
return False
start_index = len(source) - len(substr)
for index in range(start_index, len(source)):
if source[index] != substr[index-start_index]:
break
else:
return True
return False
if __name__ == '__main__':
print(is_endswith("python", 'thon'))
4.9 实现字符串capitalize方法
题目要求
capitalize方法将字符串的第一个字母转成大写，其他字母转成小写，请实现函数my_capitalize，完成同样的功能
def my_capitalize(string):
pass
思路分析
遍历字符串，如果首字母是小写，则转成大写，其余索引上的字母如果是大写，则转成小写
大小写转换的方法，可以参考lower函数的实现
示例代码
def my_capitalize(string):
if not string:
return string
lst = []
for index, item in enumerate(string):
ascii_index = ord(item)
if index == 0:
if 97 <= ascii_index <= 122:
item = chr(ascii_index-32)
else:
if 65 <= ascii_index <= 90:
item = chr(ascii_index+32)
lst.append(item)
return "".join(lst)
print(my_capitalize('this is A book'))
4.10 实现字符串count方法
题目要求
字符串count方法，可以返回指定范围内的子串的数量，下面是用法示例
source = "this is a book"
target = 'is'
print(source.count(target))
程序输出2
请仿照字符串的count方法，实现下面的函数
def my_count(source, target, start, end):
"""
函数返回字符串source在start 和 end之前，子串target 的数量， 索引范围左闭右开
:param source:
:param target:
:param start:
:param end:
:return:
"""
pass
思路分析
对于传入的参数进行合法性判断，是编写函数时必须要考虑的事情
- 字符串source，target为空判断
- start >= end判断
- start范围判断，不能小于0，也不能大于等于len(source)
- 如果end大于len(source)，则重新对end赋值，让其等于len(source)，算是一种合理的补救
经过前面的4个判断后，基本上可以保证传入的参数是合法的，不至于因为参数不合法导致程序出错
具体实现思路，将字符串target索引0与字符串source索引start进行对齐，然后逐个字符比较，只要有一个不相同，就说明，source[start: len(target)] != target，那么就需要向右移动一位，比较source[start+1: len(target)]是否与target相等。
代码里最精髓的是if t_index == len(target)这行，如果对比过程中，触发了break，那么t_index一定不会与len(target)相等，就依靠这个条件判断，就可以知道是不是找到了子串。
示例代码
def my_count(source, target, start, end):
"""
函数返回字符串source在start 和 end之前，子串target 的数量， 索引范围左闭右开
:param source:
:param target:
:param start:
:param end:
:return:
"""
if not source or not target:
return 0
if start >= end:
return 0
if start >= len(source) or start < 0:
return 0
count = 0
if end > len(source):
end = len(source)
index = start
while index < end:
t_index = 0
while t_index < len(target) and index+len(target) <= end:
if target[t_index] != source[index+t_index]:
break
t_index += 1
if t_index == len(target):
index += len(target)
count += 1
else:
index += 1
return count
source = "this is a book"
target = 'is'
print(my_count(source, target, 0, len(source)))
5. 排序算法篇
排序算法最能体现一个程序员的算法功底，也是面试时经常被拿来考察候选者的题目，本篇章一共讲解8种排序算法。
5.1 冒泡排序
冒泡排序的核心思想是相邻的两个数据进行比较，假设数列A有n个数据，先比较第1个和第2个数据，如果A1 > A2,则交换他们的位置，确保较大的那个数在右侧。
接下来比较A2和A3，采用相同的规则，较大的数向右移动，最后会比较An-1 和An的大小，如果An-1 > An，那么交换他们的位置，这时，An是数列中的最大值。
你肯定已经发现，经过这一轮比较后，数列仍然是无序的，但是没有关系，我们已经找到了最大值An，而且它在队列的末尾。
接下来要做的事情，就是简单的重复之前的过程，整个数列，先暂时把An排除在外，这n-1个无序的数，仍然可以采用之前的方法，找出n-1个数当中的最大值，这样An-1就是第2大的数，继续对n-2个数做相同的事情
为了让你更容易理解冒泡排序，我们先实现一个简单的函数
def move_max(lst, max_index):
"""
将索引0到max_index这个范围内的最大值移动到max_index位置上
:param lst:
:param max_index:
:return:
"""
for i in range(max_index):
if lst[i] > lst[i+1]:
lst[i], lst[i+1] = lst[i+1], lst[i]
if __name__ == '__main__':
lst = [7, 1, 4, 2, 3, 6]
move_max(lst, len(lst)-1)
print(lst)
这个函数只完成一个简单的功能，它将列表从索引0到max_index之间的最大值移动max_index索引上，这正是冒泡排序的核心思想。
当我们完成这一步，剩下的事情，就是不断的重复这个过程。
def pop_sort(lst):
for i in range(len(lst)-1, 1, -1):
move_max(lst, i)
def move_max(lst, max_index):
"""
将索引0到max_index这个范围内的最大值移动到max_index位置上
:param lst:
:param max_index:
:return:
"""
for i in range(max_index):
if lst[i] > lst[i+1]:
lst[i], lst[i+1] = lst[i+1], lst[i]
if __name__ == '__main__':
lst = [7, 1, 4, 2, 3, 6]
pop_sort(lst)
print(lst)
5.2 快速排序
快速排序的思路可以归结为3个步骤
- 从待排序数组中随意选中一个数值，作为基准值
- 移动待排序数组中的元素，是的基准值左侧的数值都小于等于它，右侧的数值大于等于它
- 基准值将原来的数组分为两部分，针对这两部分，重复步骤1，2， 3
通过分析，可以确定，必然要使用递归算法，遇到递归不要害怕，先把1，2两步分区实现，最后实现第3步的递归
先实现分区
def partition(lst,start,end):
"""
用lst[start] 做基准值，在start到end这个范围进行分区
"""
pivot = lst[start]
while start < end :
while start < end and lst[end] >= pivot:
end -= 1
lst[start] = lst[end]
while start < end and lst[start] <= pivot:
start += 1
lst[end] = lst[start]
lst[start] = pivot
return start
partition函数返回基准值最后的索引，知道这个索引，才能将之前的待排序数组分为两部分，下面是递归部分的实现
def my_quick_sort(lst,start,end):
if start>= end:
return
index = partition(lst,start,end)
my_quick_sort(lst,start,index-1)
my_quick_sort(lst,index+1,end)
虽然这两段代码里的逻辑，你还有些不清楚，但整个的分析过程应该说是比较清晰的，先实现分区，然后实现递归，在编写算法时，很忌讳大包大揽的考虑问题，不分层次，不分先后，不分轻重。
分区虽然没有让整个数组变得有序，但是让基准值找到了自己应该在的位置，对左右两侧重复分区动作，每一次分区动作都至少让一个元素找到自己应该在的位置。
验证代码
if __name__ == '__main__':
lst = [4,3,2,4,1,5,7,2]
my_quick_sort(lst,0,len(lst)-1)
print lst
5.3 希尔排序
算法定义
希尔排序，又称缩小增量排序，不要被这个名字吓到，其实，它只是对插入算法的改进而已。
当待排序列基本有序的情况下，插入算法的效率非常高，那么希尔排序就是利用这个特点对插入算法进行了改造升级
分组
待排序数组为
4,1,67,34,12,35,14,8,6,19
第一轮希尔排序
希尔排序的关键在于对待排序列进行分组，这个分组并不是真的对序列进行了拆分，而仅仅是虚拟的分组
首先，用10/2 = 5, 这里的5就是缩小增量排序中的那个“增量”。从第0个元素开始，每个元素都与自己距离为5的元素分为一组，那么这样一来分组情况就是
4 35
1 14
67 8
34 6
12 19
需要注意的是，所谓的分组，仅仅是逻辑上的分组，这10个元素仍然在原来的序列中。上面一共分了5组，每一组都进行插入排序，67 和 8 交换位置，34 和6 交换位置，这样第一次分组后并对各组进行插入排序后，序列变成了
4, 1, 8, 6, 12, 35, 14, 67, 34, 19
第二轮希尔排序
上一轮排序时，增量为5，那么这一轮增量为5/2 = 2，这就意味着，从第0个元素开始，每个元素都与自己距离为2的元素分为一组，分组情况如下
4 8 12 14 34
1 6 35 67 19
整个序列被分成了两组，分别对他们进行插入排序，排序后的结果为
4, 1, 8, 6, 12, 19, 14, 35, 34, 67
第三轮希尔排序
上一轮排序时，增量为2，这一轮增量为2 /2 = 1，当增量为1的时候，其实就只能分出一个组了，这样，就完全的退化成插入排序了，但是，由于已经进行了两轮希尔排序，使得序列已经基本有序了，那么此时进行插入排序，效果就会非常好
增量从5变为2，从2变为1，是逐渐减小的过程，增量是分组时所使用的步长。
示例代码
有了前面的概念以及算法的理解，写出代码就变得容易了，先分组，然后进行插入排序，你唯一要注意的地方是进行插入排序时，要弄清楚，哪些元素是一组的
lst = [4,1,67,34,12,35,14,8,6,19]
length = len(lst)
step = length//2
while step > 0:
for i in range(step):
# 插入排序
for j in range(i+step, length, step):
if lst[j] < lst[j-step]:
tmp = lst[j]
k = j-step
while k >= 0 and lst[k] > tmp:
lst[k+step] = lst[k]
k -= step
lst[k+step] = tmp
step //= 2 #缩小增量
print lst
5.4 归并排序
合并两个有序集合
有两个有序的序列，分别为 [1,4,7] ,[2,3,5],现在请考虑将这两个序列合并成一个有序的序列。
其实方法真的非常简单
首先创建一个新的序列，分别从两个序列中取出第一个数，1和2，1比2小，把1放到新的序列中
第一个序列中的1已经放到新序列中，那么拿出4来进行比较，2比4小，把2放到新的序列中
第二个序列中的2已经放到新序列中，那么拿出3来进行比较，3比4小，把3放到新的序列中
第二个序列中的3已经放到新序列中，那么拿出5来进行比较，4比5小，把4放到新的序列中
第一个序列中的4已经放到新序列中，那么拿出7来进行比较，5比7小，把5放到新的序列中
最后把7放入到新的序列中
合并的方法就是分别从两个序列中拿出一个数来进行比较，小的那一个放到新序列中，然后，从这个小的数所属的序列中拿出一个数来继续比较
示例代码
def merge_lst(left_lst,right_lst):
left_index, right_index = 0, 0
res_lst = []
while left_index < len(left_lst) and right_index < len(right_lst):
# 小的放入到res_lst中
if left_lst[left_index] < right_lst[right_index]:
res_lst.append(left_lst[left_index])
left_index += 1
else:
res_lst.append(right_lst[right_index])
right_index += 1
# 循环结束时,必然有一个序列已经都放到新序列里,另一个却没有
if left_index == len(left_lst):
res_lst.extend(right_lst[right_index:])
else:
res_lst.extend(left_lst[left_index:])
return res_lst
5.5 归并排序
归并排序，利用了合并有序序列的思想，把一个序列分成A,B两个序列，如果这两个序列是有序的，那么直接合并他们不就可以了么，但是A，B两个序列未必是有序的，没关系，就拿A序列来说，我把A序列再分一次，分成A1,A2，如果A1，A2有序我直接对他们进行合并，A不就变得有序了么，但是A1，A2未必有序啊，没关系，我继续分，直到分出来的序列里只有一个元素的时候，一个元素，就是一个有序的序列啊，这个时候不就可以合并了
这样一层一层的分组，分到最后，一个组里只有一个元素，终于符合合并的条件了，再一层一层的向上合并
完成示例代码：
def merge_lst(left_lst,right_lst):
left_index, right_index = 0, 0
res_lst = []
while left_index < len(left_lst) and right_index < len(right_lst):
# 小的放入到res_lst中
if left_lst[left_index] < right_lst[right_index]:
res_lst.append(left_lst[left_index])
left_index += 1
else:
res_lst.append(right_lst[right_index])
right_index += 1
# 循环结束时,必然有一个序列已经都放到新序列里,另一个却没有
if left_index == len(left_lst):
res_lst.extend(right_lst[right_index:])
else:
res_lst.extend(left_lst[left_index:])
return res_lst
def merge_sort(lst):
if len(lst) <= 1:
return lst
middle = len(lst)//2
left_lst = merge_sort(lst[:middle])
right_lst = merge_sort(lst[middle:])
return merge_lst(left_lst, right_lst)
if __name__ == '__main__':
lst = [19,4,2,8,3,167,174,34]
print merge_sort(lst)
5.6 选择排序
假设有一个序列，a[0],a[1],a[2]...a[n]现在，对它进行排序。我们先从0这个位置到n这个位置找出最小值，然后将这个最小值与a[0]交换，然后呢，a[1]到a[n]就是我们接下来要排序的序列
我们可以从1这个位置到n这个位置找出最小值，然后将这个最小值与a[1]交换，之后，a[2]到a[n]就是我们接下来要排序的序列
每一次，我们都从序列中找出一个最小值，然后把它与序列的第一个元素交换位置，这样下去，待排序的元素就会越来越少，直到最后一个
示例代码
def select_sort(lst):
for i in range(len(lst)):
min = i
for j in range(min,len(lst)):
# 寻找min 到len(lst)-1 这个范围内的最小值
if lst[min] > lst[j]:
min = j
lst[i], lst[min] = lst[min], lst[i]
lst = [2,6,1,8,2,4,9]
select_sort(lst)
print lst
5.7 堆排序
堆的概念
堆是一种数据结构，分最大堆和最小堆，最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。
我们用list来描述它
lst = [9, 6, 8, 3, 1, 4, 2]
你看不出这个lst有什么特别，别着急，再介绍两个概念给你
父节点，子节点
列表中的每一个元素都是一个节点，以lst[0] 为例，他的子节点分别是lst[1],lst[2]，同时我们也说lst[1]的父节点是lst[0]
我们可以计算每一个节点的子节点，假设当前节点的序号是i，那么它的左子节点则是 i2 +1,右子节点则是i2 + 2
最大堆，最小堆
所谓最大堆就是指每一个节点的值都比它的子节点的值大，最小堆就是指每一个节点的值都比它的子节点的值小
现在，我们再来看上面给出的列表
lst[0] = 9,它的子节点分别是lst[1]=6,lst[2]=8
lst[1] = 6,它的子节点分别是lst[3]=3,lst[4]=1
lst[2] = 8,它的子节点分别是lst[5]=4,lst[6]=2
lst[3] = 3,它的子节点分贝是lst[7]和lst[8]，但这两个节点是不存在的
后面的也就不用再看了，这个列表符合最大堆的要求，父节点的值大于两个子节点的值，而且最重要的一点，堆中任意一颗子树仍然是堆
如何建立一个堆
关于堆的应用，非常多，比如堆排序，在应用之前，我们必须先建立一个堆，刚才给出的列表，恰好是一个堆，如果不是堆呢，我们需要将其变成堆，例如下面这个列表
lst = [3, 9, 2, 6, 1, 4, 8]
这个列表里的元素和上一个列表里的元素是一样的，只是顺序不同，建立堆的过程，就是调整顺序的过程，使其满足堆的定义
不是所有节点都有子节点
如果当前节点的位置是i,那么子节点的位置是i2 + 1 和 i2 +2 ，因此，不是所有节点都有子节点，假设一个堆的长度为n，那么n/2 - 1 及以前的节点都是有子节点的，这是一个非常简单的算数题，你稍微用脑就能理解。
那么建立堆的过程，就是从n/2 - 1 到0 逐渐调整的过程，如何调整呢？
每个节点都和自己的两个子节点中最大的那个节点交换位置就可以了，这样，节点值较大的那个就会不停的向上调整
示例代码
def adjust_heap(lst, i, size):
lchild = 2 * i + 1 # 计算两个子节点的位置
rchild = 2 * i + 2
max = i
if i < size // 2:
if lchild < size and lst[lchild] > lst[max]:
max = lchild
if rchild < size and lst[rchild] > lst[max]:
max = rchild
# 如果max != i成立,那么就说明,子节点比父节点大,要交换位置
if max != i:
lst[max], lst[i] = lst[i], lst[max]
# 向下继续调整,确保子树也符合堆的定义
adjust_heap(lst, max, size)
def build_heap(lst):
for i in range((len(lst)//2)-1, -1, -1):
adjust_heap(lst, i, len(lst))
print lst # 此处输出,可以观察效果
lst = [3,9,2,6,1,4,8]
build_heap(lst)
print lst
最大堆，最小堆
关于最大堆，最小堆，我们只要掌握一点就好了，对于最大堆，堆定的元素一定是整个堆里最大的，但是，如果我们去观察，整个堆并不呈现有序的特性，比如前面建立的堆
[9, 6, 8, 3, 1, 4, 2]
堆顶元素为9，是最大值，但是从0到最后一个元素，并不是有序的
堆排序的思路
lst = [9, 6, 8, 3, 1, 4, 2]
（1）将lst[0] 与 lst[6]交换，交换后为[2, 8, 6, 4, 3, 1, 9],现在，这个堆已经被破坏掉了
（2）那么我们可以利用adjust_heap函数重新把它调整成一个堆，adjust_heap(lst,0,6)，这样调整后，lst=[8, 6, 4, 3, 1, 2, 9]
注意看lst[0]到lst[5],这个范围内的数据被调整成了一个堆，使得lst[0]也就是8是这个范围内的最大值
我们只需要重复刚才的两个步骤，就可以将堆的大小逐步缩小，同时，从后向前让整个lst变得有序
示例代码
def adjust_heap(lst, i, size):
lchild = 2 * i + 1 # 计算两个子节点的位置
rchild = 2 * i + 2
max = i
if i < size // 2:
if lchild < size and lst[lchild] > lst[max]:
max = lchild
if rchild < size and lst[rchild] > lst[max]:
max = rchild
# 如果max != i成立,那么就说明,子节点比父节点大,要交换位置
if max != i:
lst[max], lst[i] = lst[i], lst[max]
# 向下继续调整,确保子树也符合堆的定义
adjust_heap(lst, max, size)
def build_heap(lst):
for i in range((len(lst)//2)-1, -1, -1):
adjust_heap(lst, i, len(lst))
print lst # 此处输出,可以观察效果
lst = [3,9,2,6,1,4,8]
def heap_sort(lst):
size = len(lst)
# 建立一个堆,此时lst[0]一定是最大值
build_heap(lst)
print '*'*20
for i in range(size-1, -1, -1):
# 将lst[0] 与lst[i] 交换,这样大的数值就按顺序排到了后面
lst[0], lst[i] = lst[i], lst[0]
# 交换后,重新将0到i这个范围内的数据调整成堆,这样lst[0]还是最大值
adjust_heap(lst, 0, i)
print lst,i # 此处输出可以查看效果
heap_sort(lst)
print '*'*20
print lst
5.8 插入排序
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
咱们举一个例子，你就能明白插入排序的精髓所在
lst = [1, 2, 6, 7, 5]
lst是一个待排序的列表，你仔细观察不难发现，这个列表里的前4个数据已经是有序的了，现在，只需要把最后一个元素5插入到一个合适的位置就可以了。
从7开始向左遍历，比5大的数向右移动，当遇到一个小于等于5的数就停下来，这个位置就是5应该在的位置。当7向右移动时，占据了5的位置，因此，程序里需要一个变量把5保存下来，还需要一个变量把向左遍历时的索引记录下来，最后这个索引就是5应该在的位置。
def insert(lst, index):
"""
列表lst从索引0到索引index-1 都是有序的
函数将索引index位置上的元素插入到前面的一个合适的位置
:param lst:
:param index:
:return:
"""
if lst[index-1] < lst[index]:
return
tmp = lst[index]
tmp_index = index
while tmp_index > 0 and lst[tmp_index-1] > tmp:
lst[tmp_index] = lst[tmp_index-1]
tmp_index -= 1
lst[tmp_index] = tmp
if __name__ == '__main__':
lst = [1, 2, 6, 7, 5]
insert(lst, 4)
print(lst)
函数默认列表lst从0到index-1都是有序的，现在只需要将索引index位置上的数据插入到合适的位置就可以了。
你可能已经产生了疑惑，咱们是要排序啊，你这函数默认前面index-1个数据都是有序的，这不合理啊，前面index-1个数据如果是无序的，你怎么办呢？
看下面的代码，你就全明白了
def insert(lst, index):
"""
列表lst从索引0到索引index-1 都是有序的
函数将索引index位置上的元素插入到前面的一个合适的位置
:param lst:
:param index:
:return:
"""
if lst[index-1] < lst[index]:
return
tmp = lst[index]
tmp_index = index
while tmp_index > 0 and lst[tmp_index-1] > tmp:
lst[tmp_index] = lst[tmp_index-1]
tmp_index -= 1
lst[tmp_index] = tmp
def insert_sort(lst):
for i in range(1, len(lst)):
insert(lst, i)
if __name__ == '__main__':
lst = [1, 6, 2, 7, 5]
insert_sort(lst)
print(lst)
第1个元素单独看做一个数列，它本身就是有序的，那么只需要执行insert(lst, 1)，就可以保证前两个数据变成有序的，然后执行insert(lst, 2)，此时，从索引0到索引1是有需的，只需要将索引为2的数据插入到合适的位置就可以了。
6. 简单算法篇
6.1 打印杨辉三角
题目要求
给定一个正整数N,打印杨辉三角的前N行
杨辉三角形态如下
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
杨辉三角的每一行第一个和最后一个元素都是1
中间的元素,由上一行的两个元素相加得到,第N行的第index元素
是由第N-1 行的第index-1元素和第index相加得到的
思路分析
- 杨辉三角的每一行的第一个元素和最后也元素都是1
- 中间的元素可以由上一行的元素两两相加得到
第N行元素，可以由第N-1 行变化而来，这正是递归算法的精髓，把新的问题转化成老的问题，而老的问题转化成更老的问题，最终必然有一个老问题给出答案，然后整个逻辑链条上的问题都有了答案
代码示例
def print_yanghui(n):
"""
递归算法打印杨辉三角
:param n:
:return:
"""
if n == 1:
print([1])
return [1]
elif n == 2:
print_yanghui(1)
print([1, 1])
return [1, 1] # 这里如果不返回,第三行就无法生成
else:
lst = [1] # 第一个元素
pre_lst = print_yanghui(n - 1) # 得到上一行的元素
# 根据第n -1 行的元素,生成第n行的中间元素
for i in range(len(pre_lst) -1):
lst.append(pre_lst[i] + pre_lst[i+1])
lst.append(1) # 最后一个元素
print(lst)
return lst
if __name__ == '__main__':
print_yanghui(6)
6.2 计算三角形的周长和面积
题目要求
写一段程序，让用户输入三角形的三条边长，如果三条边长不能构成三角形，则提示用户重新输入
如果可以构成三角形，则计算周长和面积
思路分析
对于用户的输入，首先要约定格式，这里简单的约定为每个边长之间用空格间隔
在获得用户的输入以后，要对输入进行检查，有两点需要检查
（1） 检查是不是输入了三条边的边长，输入2个或者4个都是错误的
（2） 检查输入的内容是不是数值型，如果输入的是字母，那根本驴唇不对马嘴
以上两点是编程时要考虑的，经过上面的分析你应该有所体会，编程，并不是你掌握一门语言然后用它在计算机上做各种操作
编程，是对问题的思考，我这里约定让用户一次性输入三条边的边长，中间用空格隔开，你也可以让用户输入三次，也可以让用户输入一次但用别的字符做间隔，这些都是没有定论的，完全取决于你的思考
对于输入内容检查，你可能会以为python会自己完成，但其实不会，input获得的就是字符串，你必须理解什么是字符串，必须清楚的知道input的作用，这些都是最最基础的内容，如果你不掌握这些，那你就无法思考
根本不存在一种方法或者操作可以满足你的要求，可以解决实际的问题，编程就是分析问题然后你自己解决问题的过程
def get_edge(line):
"""
根据用户的输入获得三条边
用户输入三条边的长度,用空格隔开 类似于 3 4 5
:param line:
:return:
"""
edge_lst = line.split(" ")
# 如果输入条数不是3
if len(edge_lst) != 3:
return False, (0, 0, 0)
try:
# raw_input 获得用户的输入,得到的是字符串,这里把字符串转成float数值
edge_lst = [float(item) for item in edge_lst]
except:
return False, (0, 0, 0)
return True, (edge_lst[0], edge_lst[1], edge_lst[2])
def is_able_triangle(a, b, c):
"""
判断能否构成三角形
:param a:
:param b:
:param c:
:return:
"""
return (a + b > c) and (a + c > b) and (c + b > a)
def triangle_func():
while True:
line = input('输入三角形的三个边长,用空格隔开,退出请输入q:')
if line == 'q':
break
input_correct, edges = get_edge(line)
if not input_correct:
print('输入错误')
continue
if not is_able_triangle(edges[0], edges[1], edges[2]):
print('不能构成三角形')
continue
perimeter = sum(edges)
half_perimeter = perimeter//2
area = (half_perimeter*(half_perimeter-edges[0])*(half_perimeter-edges[1])*(half_perimeter-edges[2])) ** 0.5
print('周长: {perimeter} 面积:{area}'.format(perimeter=perimeter, area=area))
if __name__ == '__main__':
triangle_func()
6.3 忽略大小比较字符串是否相等
题目要求
比较两个字符串，忽略大小写，比如字符串"abc"和字符串"ABC",在忽略大小写的情况下是相等的，实现函数
def is_same_ignore_case(str1, str2):
"""
忽略大小写比较两个字符串是否相等
:param str1:
:param str2:
:return:
"""
pass
要求，不能使用字符串的lower方法和upper方法
思路分析
题目要求不能使用字符串的lower方法和upper方法，之所以这样要求，是希望你能从更基础的编程做起，培养更深入的思考。
要解这个练习题，你需要对ASCII码表有一定的了解，在ASCII码表中，大小写字母的十进制编码相差32。
通过for循环，遍历str1,同时获取与之相对应索引上的字母，因为要忽略大小写，因此，将他们都转换成ASCII码表里的十进制数值，并且统一转成小写字母的十进制数值。
在进行正式比较前，严谨的判断逻辑应该是先判断传入的参数str1和str2是否有效，然后判断这两个字符串的长度是否相等，这些都是从程序的健壮性和效率上考虑的。
enumerate函数是一个非常方便且有用的函数，在for循环中，既能获得遍历的元素，又能获得该元素的索引。
示例代码
def get_ord_value(string):
value = ord(string)
if 65 <= value <= 90:
value += 32
return value
def is_same_ignore_case(str1, str2):
"""
忽略大小写比较两个字符串是否相等
:param str1:
:param str2:
:return:
"""
if not isinstance(str1, str) or not isinstance(str2, str):
return False
if len(str1) != len(str2):
return False
# 统一转成小写
for index, item in enumerate(str1):
value1 = get_ord_value(item)
value2 = get_ord_value(str2[index])
if value1 != value2:
return False
return True
if __name__ == '__main__':
print(is_same_ignore_case('ABC', 'abc'))
print(is_same_ignore_case('ABC', 'abd'))
6.4 寻找数组最大值和最小值
题目要求
只遍历一遍，寻找出数组中的最大值和最小值，实现函数
def find_max_min(lst):
pass
思路分析
如果只是要去你使用for循环找出列表里的最大值或者最小值，是一件非常简单的事情。题目要求实现函数find_max_min，找出列表的最大值和最小值，首先你要明白，python中，函数可以有多个返回值。
在for循环中，使用两个if条件语句，分别寻找最大值和最小值就可以了。
实例代码
def find_max_min(lst):
if not lst or not isinstance(lst, list):
return None, None
max_value, min_value = lst[0], lst[0]
for item in lst:
if item > max_value:
max_value = item
if item < min_value:
min_value = item
return max_value, min_value
if __name__ == '__main__':
lst = [43, 1, 12, 435, 456, 13]
max_value, min_value = find_max_min(lst)
print(max_value, min_value)
6.5 先递增后递减数组最大值
题目要求
一个数组先递增后递减，要求找到最大值，数组示例
lst = [1, 3, 6, 8, 5, 3, 2]
思路分析
既然是先递增，后递减，这样的数组至少应该有3个元素，才能符合这样的描述，而且，最大值一定不是首元素或者末尾元素。
从索引0开始遍历数组，如果下一个元素小于当前元素，那么当前这个元素一定是数组中最大的那个数据
示例代码
def find_max(lst):
if not lst or not isinstance(lst, list):
return None
for index, item in enumerate(lst):
if item > lst[index+1]:
return item
if __name__ == '__main__':
lst = [1, 3, 6, 8, 5, 3, 2]
max_value = find_max(lst)
print(max_value)
拓展
上面的算法并不是最高效的，鉴于其有序性，也可以使用二分法进行查找，对于初学者稍微有些困难，感兴趣的朋友可以自己去探索。
6.6 生成矩阵
题目要求
已知两个列表
lst_1 = [1, 2, 3, 4]
lst_2 = ['a', 'b', 'c', 'd']
请写算法，将两个列表交叉相乘，生成如下的矩阵
[['1a', '2a', '3a', '4a'],
['1b', '2b', '3b', '4b'],
['1c', '2c', '3c', '4c'],
['1d', '2d', '3d', '4d']]
思路分析
观察生成的矩阵，可以得出这样的结论，lst_1的长度决定了矩阵有多少列，lst_2的长度决定了生成的矩阵有多少行。
既然是交叉相乘，那么可以写两个for循环，嵌套遍历这两个列表，对lst_2的遍历放在外层，对lst_1的遍历放在内层。
示例代码
import pprint
lst_1 = [1, 2, 3, 4]
lst_2 = ['a', 'b', 'c', 'd']
lst = []
for item2 in lst_2:
tmp = []
for item1 in lst_1:
tmp.append(str(item1) + item2)
lst.append(tmp)
pprint.pprint(lst)
6.7 矩阵对角线元素和
题目要求
求一个3*3矩阵中对角线上元素之和
先模拟一个3*3矩阵
3 5 6
4 7 8
2 4 9
思路分析
在C语言里，这种数据要用二维数组来存储，在python里，没有二维数组这个专业用语，概念上，你可以理解为嵌套列表，其定义如下
lst = [
[3,5,6],
[4,7,8],
[2,4,9]
]
lst中有3个元素，均是列表，lst[0]是一个列表，该列表里有3个元素。
题目要求计算对角线元素和，也就是lst[0][0] + lst[1][1] + lst[2][2],写一个for循环，用range(3)产生一个从0到2的序列，即可实现这三个元素的相加
实例代码
lst = [
[3,5,6],
[4,7,8],
[2,4,9]
]
sum = 0
for i in range(3):
sum += lst[i][i]
print sum
6.8 输出今天的信息
按照下面的格式，输出今天的时间信息
今天是2019年4月18日，星期四，今年的第108天，这一年29.59%的时间已流逝
思路分析
对日期的操作，使用datetime模块
today = datetime.datetime.now()
today存储了今天的日期信息，包括年月日，时分秒。
today.isoweekday() 返回的是数字1到7，对应周一到周日。
计算距离今年第一天的天数方法如下
days = int(today.strftime('%j'))
计算时间流逝的百分比，需要计算出今年一共有多少天，如果是闰年，是366天，本练习题并不复杂，考察你对datetime模块的熟练程度
示例代码
import datetime
out_put_str = "今天是{date_str}，{weekday}，今年的第{days}天，这一年{pass_ratio}%的时间已流逝"
year_days = 365 # 一年有365天
today = datetime.datetime.now()
date_str = '{year}年{month}月{day}日'.format(year=today.year, month=today.month, day=today.day)
year = today.year
# 判断是否为闰年，闰年的条件： 能被100乘除时，如果可以被400乘除，那么是闰年，不能被100乘除，能被4整除是闰年
b_runnian = False
if year % 100 == 0:
if year % 400 == 0:
b_runnian = True
elif year % 4 == 0:
b_runnian = True
if b_runnian:
year_days = 366
# 今年的第几天
days = int(today.strftime('%j'))
# 数字星期与中文星期的映射关系
week_map = {
1: '星期一',
2: '星期二',
3: '星期三',
4: '星期四',
5: '星期五',
6: '星期六',
7: '星期日',
}
# 星期几
week_day = week_map[today.isoweekday()]
# 已经过去了多少
pass_ratio = round((days / year_days)*100, 2)
out_put = out_put_str.format(date_str=date_str, weekday=week_day, days=days, pass_ratio=pass_ratio)
print(out_put)
6.9 可变对象与不可变对象考察
下面的题目，要求你在不执行程序的情况下说出程序的执行结果，然后，执行程序，将程序输出结果与自己的理解进行对比
6.9.1 不可变对象考察
lst = [1, 2, 3, 4, 5]
for item in lst:
item = 0
print(lst)
上面的代码输出结果是
A. [1, 2, 3, 4, 5]
B. [0, 0, 0, 0, 0]
答案是 A， 在遍历过程中，item的数据类型是int,是不可变对象，item = 0仅仅是重新对item变量进行赋值，改变的是item变量的指向，并没有改变列表内容
6.9.2 可变对象考察
lst = [[1, 2, 3, 4], [5, 6, 7, 8]]
for item in lst:
item.append(0)
print(lst)
请写出上面程序的输出结果
答案是
[[1, 2, 3, 4, 0], [5, 6, 7, 8, 0]]
遍历过程中，item的数据类型是列表，列表是可变对象，item.append(0) 这个操作，没有改变item变量的指向，而是修改了它所指向的列表里的内容
6.9.3 不可变对象考察
my_dic = {
'class1': 90,
'class2': 95,
'class3': 100
}
for key, value in my_dic.items():
value = 100
print(my_dic)
请输出上面程序的输出结果
答案是my_dic不发生任何变化，原理与6.9.1相同
6.9.4 可变对象考察
my_dic = {
'class1': [1,2],
'class2': [3,4],
'class3': [5,6]
}
for key, value in my_dic.items():
value.append(0)
print(my_dic)
请输出上面程序的输出结果
答案是
my_dic = {
'class1': [1,2,0],
'class2': [3,4,0],
'class3': [5,6,0]
}
原理与6.9.2相同
6.10统计日期间隔
题目要求
需要编写一个函数get_day_diff(date_lst, target)， 入参示例如下
date_lst = [
'2019-01-01', '2019-01-15',
'2019-01-30', '2019-02-01',
'2019-02-05', '2019-02-15',
'2019-03-06', '2019-03-15',
'2019-04-01', '2019-04-05',
'2019-04-13', '2019-04-30',
'2019-05-05', '2019-05-06'
]
target = '2019-05-08'
函数计算date_lst里的日期与target的间隔天数，然后统计这些天数信息，最后返回的结果示例如下
{'7_days': 2, '30_days': 4, '90_days': 9, '180_days': 14}
7_days 表示时间间隔小于7天的日期个数
思路分析
不可能直接用字符串计算日期的间隔，需要将这些字符串转成datetime类型，这样才能计算两个日期的间隔
最终的结果需要用字典来保存，因此函数里需要初始化一个字典
info = {
'7_days': 0,
'30_days': 0,
'90_days': 0,
'180_days':0
}
用列表里的日期和target求间隔，然后做统计，如果间隔天数小于等于7天，则info['7_days'] += 1, 需要注意的地方是，一共有4个条件判断，而且这些条件判断之间不是互斥的关系，不能使用if else 这种逻辑判断，只需要4个if判断即可
示例代码
import datetime
def get_day_diff(date_lst, target):
info = {
'7_days': 0,
'30_days': 0,
'90_days': 0,
'180_days':0
}
target_date = datetime.datetime.strptime(target, '%Y-%m-%d')
for date_str in date_lst:
date = datetime.datetime.strptime(date_str, '%Y-%m-%d')
day_diff = (target_date - date).days
if day_diff <= 180:
info['180_days'] += 1
if day_diff <= 90:
info['90_days'] += 1
if day_diff <= 30:
info['30_days'] += 1
if day_diff <= 7:
info['7_days'] += 1
return info
if __name__ == '__main__':
date_lst = [
'2019-01-01', '2019-01-15',
'2019-01-30', '2019-02-01',
'2019-02-05', '2019-02-15',
'2019-03-06', '2019-03-15',
'2019-04-01', '2019-04-05',
'2019-04-13', '2019-04-30',
'2019-05-05', '2019-05-06'
]
info = get_day_diff(date_lst, '2019-05-08')
print(info)
6.11 修改字典里的value
题目要求
有一个字典，保存的是学生各个编程语言的成绩，内容如下
data = {
'python': '90',
'c++': '95',
'java': '90'
}
请编写函数 transfer_score，将value修改成int类型，最终字典内容变成
data = {
'python': 90,
'c++': 95,
'java': 90
}
完善下面的代码
def transfer_score(score_dict):
"""
在这里实现你的算法
:param score_dict:
:return:
"""
pass
if __name__ == '__main__':
data = {
'python': '90',
'c++': '95',
'java': '90'
}
transfer_score(data)
print(data)
思路分析
字典的结构非常简单，只需要遍历字典然后修改value类型即可，但如果你写成value = int(value) 是不会起到任何作用的，因为这样并没有修改真正的value，不要忘记了，想要修改字典里的value，必须通过key来修改，只能写成score_dict[key] = int(value)
示例代码
def transfer_score(score_dict):
"""
在这里实现你的算法
:param score_dict:
:return:
"""
for key, value in score_dict.items():
score_dict[key] = int(value)
if __name__ == '__main__':
data = {
'python': '90',
'c++': '95',
'java': '90'
}
transfer_score(data)
print(data)
6.12打印菱形
题目要求
实现函数print_diamond(count)，根据参数大小在屏幕上输出菱形
*
***
*****
*******
*********
*******
*****
***
*
默认传入的参数一定是奇数，如果是7，则菱形最宽的地方有7个星号
思路分析
将菱形分为两部分，第一部分是从第一行到最宽的那一行，第二部分从最宽的那一行到最后一行
第一部分，星号的数量从1开始递增，每次增加两个，第二部分，星号的数量从count个开始递减，每次减少两个，与之对应的，第一部分，空格的数量是递减的。
count是多少，这个菱形就有多少行，使用for循环，让变量i从0变化到count-1，第一部分里，星号的数量和i之间的关系是2*i-1,空格的数量与i之间的关系是count//2-i，数学上，当i <=count//2时，都是第一部分图形。
进入第二部分后，空格与i之间的关系是i-count//2， 星号数量与i之间的关系(count-1)*2-1。
本练习题，希望能纠正你对编程的错误认知和理解，编程不是你以为的发挥个人想象力进行创造，如同搭积木一般自由自在随意操作，编程需要的是缜密的思维，严谨的逻辑思考，你看到的例子都是简单几行代码就实现了惊艳的功能，因此被忽悠的学习了python，但那些惊艳的例子不是编程的全部，甚至除了勾引你入门意外，什么都不会交给你。
本题展示出的，才是编程的本质，用程序语言表达出你对问题的思考，逻辑推理，解决一个实际问题所需要的，是扎实的算法功底，同学，努力吧。
示例代码
def print_diamond(count):
for i in range(count):
if i <= count//2:
print(" "*(count//2-i) + "*"*(2*i + 1))
else:
print(" "*(i - count//2) + "*"*((count-i)*2-1))
print_diamond(5)
6.13 打印九九乘法表
题目要求
在屏幕上输出九九乘法表
1*1 = 1
1*2 = 2 2*2 = 4
1*3 = 3 2*3 = 6 3*3 = 9
1*4 = 4 2*4 = 8 3*4 = 12 4*4 = 16
1*5 = 5 2*5 = 10 3*5 = 15 4*5 = 20 5*5 = 25
1*6 = 6 2*6 = 12 3*6 = 18 4*6 = 24 5*6 = 30 6*6 = 36
1*7 = 7 2*7 = 14 3*7 = 21 4*7 = 28 5*7 = 35 6*7 = 42 7*7 = 49
1*8 = 8 2*8 = 16 3*8 = 24 4*8 = 32 5*8 = 40 6*8 = 48 7*8 = 56 8*8 = 64
1*9 = 9 2*9 = 18 3*9 = 27 4*9 = 36 5*9 = 45 6*9 = 54 7*9 = 63 8*9 = 72 9*9 = 81
思路分析
题目乍看起来挺难的，但其实非常简单，前提是你知道如何分析。
九九乘法表一共有9行，我们先考虑如何输出一行，一行解决了，使用一个for循环，就可以把所有行都输出了，定义函数print_line(line_number)，该函数输出第line_number行。
当line_number等于9的时候，研究一下如何输出第9行。第9行有9个式子，从1到9分别乘以9，看见没，这不就是一个for循环么，使用一个for循环，让变量i从1变化到9，每次都与9相乘，并将结果组装成一个i*9 = xx 的式子，把所有的式子连接在一起，就是第9行的内容
解决了指定行的输出后，只需要一个简单的for循环，从1到9，分别去调用这个函数不就将整个乘法表打印出来了么？
示例代码
def print_line(line_number):
lst = []
for i in range(1, line_number+1):
part = "{index}*{number} = {res}".format(index=i, number=line_number, res=i*line_number)
lst.append(part)
print(" ".join(lst))
def print_table():
for i in range(1, 10):
print_line(i)
print_table()
6.14 统计字符数量
题目要求
使用input函数接收用户的输入，统计出其中英文字母、空格、数字和其它字符的个数，例如用户输入字符串"sdfijer384323js",程序最终输出信息
{'s': 2, 'd': 1, 'f': 1, 'i': 1, 'j': 2, 'e': 1, 'r': 1, '3': 3, '8': 1, '4': 1, '2': 1}
思路分析
input函数接收用户的输入，得到的是字符串，遍历字符串，统计字符串中每一个字符出现的次数，这种信息自然是用字典来存储，其他容器类型数据列表，元组，集合，都不适合存储这种key-value形式的数据
示例代码
string = input("请输入一个字符串:")
info = {}
for item in string:
info.setdefault(item, 0)
info[item] += 1
print(info)
6.15 水仙花数
输出所有的水仙花数，所谓水仙花数是指一个三位数，各个位上的数的立方相加在一起等于这个三位数，比如153，1的3次方 + 5的三次方 + 3的三次方 等于153
思路分析
水仙花数是一个3位数，数值范围是从100到999之间，写一个for循环，从100到999进行遍历，逐个判断该数是否为水仙花数即可。
对于一个三位数，获得这个数的每一位也并不难，以153为例
a = 153
while a > 0:
print(a % 10)
a //= 10
对数字的操作，永远离不开取模运算和整除运算
示例代码
for i in range(100, 1000):
res = 0
value = i
while value > 0:
res += (value%10)**3
value //= 10
if res == i:
print(res)
6.16 完全平方数
完全平方数，就是可以表示为某个整数的平方的数，例如9，是3的平方，16是4的平方，9和16都是完全平方数，请打印10000以内的完全平方数
思路分析
两个思路，一个思路是从1到10000进行遍历，对每一个数值进行判断，判断其是否为某个整数的平方。
第二个思路，从1到10000进行遍历，计算每一个数值的平方，如果这个平方小于10000，那么这个数值的平方就是完全平方数。
显然，第二个方法更容易一些，毕竟开根号这种事情，不能保证开出来的一定是整数。
示例代码
i = 1
value = 1
while value < 10000:
print(i, value)
i += 1
value = i**2
6.17求三位数组合
lst = [3, 6, 2, 7]
这四个数字能组成多少个互不相同且无重复数字的三位数？比如362算一个，326算一个，请逐个输出他们
思路分析
从4个数字里挑出来，组成一个3位数，就算法而言，最方便的做法是用一个3层嵌套循环，分别从lst取数，取出来的数值组成一个3位数，题目要求无重复数字，这就要求，取出来的3个数字互不相等
示例代码
lst = [3, 6, 2, 7]
for a in lst:
for b in lst:
for c in lst:
if a != b and b != c and a != c:
print(a*100 + b*10 + c)
如何判断3个数值互不相等，还有一个更简单的办法
if a not in (b, c) and b != c:
6.18 翻转列表
题目要求
lst = [1,2,3,4,5]
翻转后
lst = [5,4,3,2,1]
思路分析
如果是用列表自带的功能，翻转列表是非常容易的事情
lst = lst[::-1]
现在，需要你自己来实现翻转过程，思路很简单，从头开始遍历列表，但只遍历到一半，左右两边对位交换数据即可
示例代码
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
length = len(lst)
for i in range(length//2):
tmp = lst[i]
lst[i] = lst[length - 1 - i]
lst[length - 1 - i] = tmp
print(lst)
6.19 列表偏移
题目要求
lst = [1,2,3,4,5]，列表向右偏移两位后，变成lst = [5,4,1,2,3]
思路分析
先说简易思路，以向右偏移2位做例子，直接对列表进行切片操作，然后再讲切片后的列表连接在一起
lst = [1,2,3,4,5]
lst = lst[len(lst)-2:] + lst[:len(lst)-2]
print(lst)
如果是初学者这样做，是完全可以接受的，但如果想更上一层楼，则需要更加合理的解决方法
首先，偏移的位数可能会超过列表的长度，比如向右偏移47位，此时，就要考虑用47%5 = 2，向右偏移47位等价于向右偏移2位
直接对列表进行切片操作，终究还是用了列表的原生功能，既然是练习题，且偏向于算法层面，那么我们应该自己来实现偏移，不生成新的列表，只在原列表上动手脚
不论偏移多少位，在实现时，每一次，我们只偏移1位，先实现偏移1位的情况。
偏移1位，只需要将列表最后一位记录下来，然后其他所有位置上的数值向右移动一位，最后将之前记录下来的列表最后一位放置在列表的开头即可。
实现了偏移1位，剩下的仅仅是写一个for循环，就可以偏移指定的位数
示例代码
lst = [1,2,3,4,5]
count = int(input("请输入偏移位数"))
count = count % len(lst)
for i in range(count):
tmp = lst[-1]
for j in range(len(lst)-1, 0, -1):
lst[j] = lst[j-1]
lst[0] = tmp
print(lst)
6.20 比较三个数的大小
使用input函数接收用户的输入，用户输入三个整数，中间用空格分隔，程序判断这三个数的大小关系，最后用print函数输出这个三个数，从大到小
输入： 43 22 88
输出： 88 43 22
思路分析
其实，真没啥好分析的
- input函数返回的是字符串
- 我们需要的是int类型的数据，因此用split函数对字符串进行分割
- 分割后，三个部分都转换成int类型的数据
- 比较大小就是一个简单的事情了，纯粹是数学问题，小学生都会，只是你要把各种逻辑分支都考虑全，这种题目考察锻炼的是你的思维能力
示例代码
string = input("请输入三个整数,中间用空格分隔:")
lst = string.split()
a, b, c = int(lst[0]), int(lst[1]), int(lst[2])
if a >= b:
if c >= a:
print(c, a, b)
elif c >= b:
print(a, c, b)
else:
print(a, b, c)
else:
# b > a
if c >= b:
print(c, b, a)
elif c >= a:
print(b, c, a)
else:
print(b, a, c)
6.21 求学生最高分数科目和分数
题目要求
实现下面的函数
def get_max_socre(score_dic):
"""
返回学生考试成绩的最高分的科目和分数
:param score_dic:
:return:
"""
pass
传入的socre_dic 内容类似下面的数据
dic = {
'语文': 90,
'数学': 97,
'英语': 98
}
程序最终输出: 英语 98
思路分析
万变不离其中，遍历是万能的，遍历传入的字典，用一个变量保存最高分数，用另一个变量保存科目，遇到更高的分数，则修改这两个变量，就是这么的简单
示例代码
def get_max_socre(score_dic):
"""
返回学生考试成绩的最高分的科目和分数
:param score_dic:
:return:
"""
max_score = 0
max_course = ''
for key, value in score_dic.items():
if value > max_score:
max_score = value
max_course = key
print(max_course, max_score)
if __name__ == '__main__':
dic = {
'语文': 90,
'数学': 97,
'英语': 98
}
get_max_socre(dic)
6.22 水果
小明喜欢葡萄，香蕉，苹果，小红喜欢香蕉，桃子，草莓， 请写程序分析
- 他们共同喜欢的水果是什么？
- 他们两个喜欢的水果加在一起都有什么
- 什么水果是小明喜欢的却不是小红喜欢的？
- 什么水果是小红喜欢的却不是小明喜欢的
思路分析
交集，差集，并集，这些数据操作使用集合最为合适
示例代码
lst_1 = ['葡萄', '香蕉', '苹果']
lst_2 = ['香蕉', '桃子', '草莓']
set_1 = set(lst_1)
set_2 = set(lst_2)
print(set_1.intersection(set_2))
print(set_1.union(set_2))
print(set_1.difference(set_2))
print(set_2.difference(set_1))
7 中等难度算法练习题
7.1 验证回文串
题目要求
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写，例如“123A man, a plan, a canal: Panama321”
严格的讲，这个字符串并不是一个回文，但是如果只考虑字母和数字并且忽略大小写，那么它确实是一个回文
思路分析
这道题目非常简单，需要掌握字符串的两个基本方法
- isalpha() 判断字符串是否是字母
- isdigit() 判断字符串是否是数字
逐一遍历字符串，判断每一个字符是否符合字母和数字的要求，把符合要求的字符串放入到一个list中，最后用列表的join方法将列表中的字符串拼接成一个新的字符串，题目还要求忽略大小写，新的字符串转成小写即可。
经过一番处理，从原始字符串得到了一个全是小写的只包含字母和数字的字符串，那么剩下的事情就变得非常简单了。
示例代码
# coding=utf-8
def isPalindrome(string):
# 把字符串中的字母和数字挑选出来
str_lst= []
for item in string:
if item.isalpha() or item.isdigit():
str_lst.append(item)
# 组成新的字符串,并转成小写
new_string = "".join(str_lst).lower()
for i in range(len(new_string)/2):
if new_string[i] != new_string[len(new_string)-1-i]:
return False
return True
if __name__ == '__main__':
string = "123A man, a plan, a canal: Panama321"
print(isPalindrome(string))
7.2 翻转字符串里的单词
题目要求
给定一个字符串，逐个翻转字符串中的每个单
示例:
输入: " the sky is blue",
输出: "blue is sky the "
翻转后，空格不能减少，单词之间的空格数量不能发生变化
思路分析
如果只是单纯的翻转字符串，就过于简单了，因此要求翻转每一个单词，单词还是原来的样子，但是单词所在的位置却发生了翻转，第一个单词变成了倒数第一个单词。
可以先将整个字符串都翻转，这样单词的位置完成了翻转，结果如下：
"eulb si yks eht "
但这个时候，每一个单词的顺序还是颠倒的，因此需要对每一个单词进行一次翻转。
字符串是不可变对象，不能直接在字符串上进行翻转，要借助列表（list）进行翻转，翻转后在使用join方法将列表里的元素拼成字符串
示例代码
# coding=utf-8
def reverse_word(string):
# 先将整个句子翻转
word_lst = list(string)
for i in range(len(word_lst)/2):
word_lst[i], word_lst[len(word_lst)-1-i] = word_lst[len(word_lst)-1-i], word_lst[i]
print("".join(word_lst))
# 翻转里面的单词
start_index = None
end_index = None
b_word = False
for index, item in enumerate(word_lst):
if item.isalpha():
if not b_word:
start_index = index # 单词开始的位置
b_word = True
else:
if b_word:
end_index = index -1 # 单词结束的位置
b_word = False
# 已经知道单词开始和结束的位置,翻转这个单词
reverse_single_word(word_lst, start_index, end_index)
return "".join(word_lst)
def reverse_single_word(lst, start_index, end_index):
"""
将lst 中 start_index到end_index 这个区域翻转
:param lst:
:param start_index:
:param end_index:
:return:
"""
while start_index < end_index:
lst[start_index], lst[end_index] = lst[end_index], lst[start_index]
start_index += 1
end_index -= 1
if __name__ == '__main__':
print(reverse_word(" the sky is blue"))
7.3 寻找峰值
题目要求
峰值元素是指其值大于左右相邻值的元素，给定一个序列，请返回所有的峰值元素及其索引
示例1：
输入: nums = [1,2,3,1]
输出: [(2, 3)]
以列表形式输出，元素为tuple，tuple[0]表示索引，tuple[1]表示元素
思路分析
遍历序列，对于每一个元素，都要和自己左右两侧的相邻值进行比较，如果大于两侧相邻值，那么这个元素就是峰值元素。
需要注意的是序列的两端元素，他们都只有一侧有相邻元素，因此在逻辑处理上要考虑这种边界情况。
示例代码
def find_peak(lst):
if len(lst) <= 2:
return -1
peak_lst = []
for index, item in enumerate(lst):
big_than_left = False # 是否比左侧大
big_than_right = False # 是否比右侧大
# 考虑边界情况
if index == 0:
big_than_left = True
big_than_right = item > lst[index+1]
elif index== len(lst) - 1:
big_than_right = True
big_than_left = item > lst[index-1]
else:
big_than_left = item > lst[index-1]
big_than_right = item > lst[index+1]
if big_than_left and big_than_right:
peak_lst.append((index, item))
return peak_lst
if __name__ == '__main__':
lst = [1, 2, 1, 3, 5, 6, 4, 8]
print(find_peak(lst))
7.4 字符串转整数
题目要求
实现函数atoi，将字符串转为整数，具体要求如下：
- 字符串第一个非空字符如果不是数字，字符串无效，返回0
- 字符串第一个非空字符如果是 + 或者 -，则表示正负，且该字符后面的第一个非空字符必须是数字，否则视为无效字符串，返回0
- 遇到数字，将其与之后连续的数字字符组合起来形成整数
- 有效数字范围是[−231, 231 − 1],数值超过可表示的范围，则返回231 − 1 或−231 。
示例
1、 "42" 转成 42
2、 " - 42 43" 转成 -4243
3、 "4193 word" 转成4193
4、 "word 4193" 转成0
5、 "-91283472332" 转成-91283472332， 比−2^31还小，返回−2^31
思路分析
基本思路是遍历字符串，遍历过程中，关键点是找到第一个非空字符，这个非空字符决定了接下来程序的走向。
如果第一个非空字符是+或者-，就决定了数值的正负，后面的工作是提取数值
如果第一个非空字符是数字，事情变得简单了，直接提取数值。
如果第一个非空字符既不是数字，也不是+或-，就是无效字符串，返回0即可。
提取数值的过程，用一个列表保存单个数字，直到遇到一个既不是数字也不是空格的字符或者遇到字符串末尾，将列表里的数值连接起来并用int转成数值。
程序的最后，要和最大值和小值比较。
示例代码
# coding=utf-8
MAX_INT = 2**31-1
MIN_INT = -2**31
def atoi(string):
"""
将字符串转成int
:param string:
:return:
"""
if not isinstance(string, basestring):
return 0
if string == u'':
return 0
tag = 1 # 标识正负, 赋值为1表示为正
value = 0
for index, item in enumerate(string):
# 空字符不处理
if item == u' ':
continue
elif item in ('+', '-'):
if item == '-':
tag = -1
value = get_int(string, index)
break
elif item.isdigit():
value = get_int(string, index)
break
else:
return 0
value = tag * value
if value > MAX_INT:
value = MAX_INT
if value < MIN_INT:
value = MIN_INT
return value
def get_int(string, start_index):
"""
提取数值
:param string: 字符串
:param start_index: 数值开始部分
:return:
"""
lst = []
for index in range(start_index, len(string)):
if string[index] == u' ': # 空字符不用处理
continue
if string[index].isdigit(): # 遇到不是数字时结束
lst.append(string[index])
return int(''.join(lst))
if __name__ == '__main__':
print atoi("42")
print atoi(" - 42 43 ")
print atoi("4193 4 word")
print atoi("word 4193")
print atoi("-91283472332")
7.5 判断数组是山脉数组
如果一个数组k符合下面两个属性，则称之为山脉数组
- 数组的长度大于等于3
- 存在i，i >0 且 i < len(k)-1， 使得k[0] < k[1]< ... < k[i-1] < k[i] > k[i+1] ... >k[len(k)-1]， 这个i就是顶峰索引。
现在，给定一个山脉数组，求顶峰索引。
输入: [1, 3, 4, 5, 3]
输出: True
输入：[1, 2, 4, 6, 4, 5]
输出：False
思路分析
山脉数组的特点是在到达山脉峰顶前，每个元素都比右侧的元素小，过了峰顶之后，每个元素都比右侧元素大。
对数组k进行遍历，当k[index] < k[index+1] 不成立时，说明可能到达峰顶了，记录当前这个索引index, 接下来要判断index的值，如果index等于0，说明k[0]<k[1] 不成立，显然不是山脉数组，如果index 等于len(k)-1， 说明倒数第2个数元素小于倒数第1个元素，显然也不是山脉数组。
如果index的值符合要求,也只能说明在index之前，是一个爬坡的过程，过了index之后，需要再用一个循环继续遍历，如果lst[index]>lst[index+1] 不成立，则不是山脉数组，前半段，后半段的判断简单一些，不涉及到峰顶索引位置的判断。
示例代码
# coding=utf-8
def is_mountain_lst(lst):
# 如果长度小于3,不符合定义
if len(lst) < 3:
return False
# 第一个循环找到发生转折的地方
index = 0
while index < len(lst)-1:
if lst[index] < lst[index+1]:
index += 1
else:
# 当前元素比右侧元素小,说明到达峰顶了,停止循环
break
# 如果index == 0,说明lst[0] < lst[1] 不成立,显然不是山脉数组
# 如果index == len(lst) -1, 说明倒数第2个数小于倒数第一个数,显然也不是山脉数组
if index == 0 or index== len(lst) -1:
return False
# 接下来要判断从index 开始到列表末尾,是不是都满足lst[index] > lst[index+1]
while index < len(lst)-1:
if lst[index] > lst[index+1]:
index += 1
else:
return False
return True
if __name__ == '__main__':
print is_mountain_lst([1, 2])
print is_mountain_lst([1, 2, 3])
print is_mountain_lst([1, 3, 4, 5, 3])
print is_mountain_lst([1, 2, 4, 6, 4, 5])
7.6 二进制中为1的位数
题目要求
给定一个整数，请计算二进制中为1的位数
输入: 13
输出: 3
解释: 13的二进制表示是 1101，位为1的数量是3
思路分析
如果一个数是奇数，那么它的二进制的最后一位一定是1，道理很简单，其他的位都表示2n 只有最后一位表示20 。我们可以利用最后一位是否为1来统计为1的位数，这就需要最后一位是变化的，还好，我们可以用位运算符 >> (右移位运算符)
13 的 二进制表示是 1101 ，13>>1 就表示二进制的每一位都向右移动一位，移动后为 110，最右边的1舍弃。如果二进制最后一位是1，那么一定是奇数。
示例代码
# coding=utf-8
def count_one_bits(value):
count = 0
# 当value等于0时,二进制的每一位都是0
while value:
if value % 2 == 1:
count += 1
value = value >> 1
return count
if __name__ == '__main__':
print(count_one_bits(6))
print(count_one_bits(13))
小小的升级
上面的分析中，利用奇偶数来判断最后一位是否为1，除此以外，还可以利用位运算符 &（按位与）来判断最后一位是否为1。
13 的二进制是 1101 ，1的二进制是1，13&1 等价于1101 & 0001， 相同位进行与运算，得到结果为0001。
示例代码
# coding=utf-8
def count_one_bits(value):
count = 0
# 当value等于0时,二进制的每一位都是0
while value:
if value & 1 == 1:
count += 1
value = value >> 1
return count
if __name__ == '__main__':
print(count_one_bits(6))
print(count_one_bits(13))
7.7 寻找缺失数字
题目要求
有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里，请找出丢失的数字。
输入： 5 3 1 2 0
输出：4
思路分析
这道题目虽小，却有多种解法。
解法1 利用递增序列求和
把4放回序列中，那么整个序列的和就是(n*(n+1))/2 ,n = 5, 结果为 15，现在序列里没有4 ，5+3+1+2+0 = 11, 15-11恰好就是缺失的数字
示例代码：
def find_miss_number_1(lst):
n = len(lst)
sum_lst = n*(n+1)/2
sum_lst_ex = sum(lst)
miss_number = sum_lst - sum_lst_ex
return miss_number
if __name__ == '__main__':
lst = [5, 3, 1, 2, 0]
print(find_miss_number_1(lst))
解法2 利用索引
示例中的序列有5个数字，算上丢失的有6个数字，创建一个长度为6的标识列表，元素都初始化为0，遍历序列，找到每个值在标识列表里的对应位置，修改元素值为1，哪个位置没有被修改为1，那个位置的索引就是丢失的值
def find_miss_number_2(lst):
tag_lst = [0 for i in range(len(lst) + 1)]
for item in lst:
tag_lst[item] = 1
for index, item in enumerate(tag_lst):
if item == 0:
return index
if __name__ == '__main__':
lst = [5, 3, 1, 2, 0]
print(find_miss_number_2(lst))
解法3 利用亦或运算
0 与任意一个数做亦或操作还是自身，一个数与自己做亦或操作则等于0。先不考虑缺失了哪个数字，用一个变量res 存储 0^1^2...^n，然后再用res逐个与序列里的值进行亦或操作，这样，没有缺失的值会与自己进行亦或操作得到0，而缺失的那个数字则最终被留存下来
def find_miss_number_3(lst):
res = 0
for i in range(1, len(lst)+1):
res ^= i
for item in lst:
res ^= item
return res
if __name__ == '__main__':
lst = [5, 3, 1, 2, 0]
print(find_miss_number_3(lst))
7.8 二进制求和
题目要求
计算两个二进制字符串的和
输入: 111 1110
输出: 10101
思路分析
参与计算的二进制字符串长度可以不同，这样为计算带来麻烦，所以，首先要补齐那个较短的字符串。如果较短字符串长度比长字符串小3，就在较短字符串前面补3个0.
计算的过程，可以模拟手动计算的过程，从右向左逐位计算。反向遍历字符串，相同位上都是1，相加后，这一位就变成了0，而且还要向前进位，下一位的计算要把进位的数值考虑进来，计算右数第一位时，进位设置为0。
示例代码
def binary_add(str_1, str_2):
# 先补齐
str_1_length = len(str_1)
str_2_length = len(str_2)
if str_1_length < str_2_length:
str_1 = "0"*(str_2_length - str_1_length) + str_1
else:
str_2 = "0"*(str_1_length - str_2_length) + str_2
# 进行计算
index = len(str_1) - 1
pre_num = 0 # 记录进位
res_lst = [] # 记录结果
# 方向遍历
while index >= 0:
item_1 = int(str_1[index])
item_2 = int(str_2[index])
item_sum = item_1 + item_2 + pre_num
pre_num = item_sum // 2
curr_num = item_sum % 2
# 新的计算结果插入到结果的第一位
res_lst.insert(0, str(curr_num))
index -= 1
if pre_num == 1:
res_lst.insert(0, '1')
return ''.join(res_lst)
if __name__ == '__main__':
print(binary_add("111", '1110'))
print(binary_add("11", '1'))
print(binary_add("101", '1001'))
7.9 第一个只出现一次的字符
题目要求
一个只包含小写字母的字符串，请找出第一个只出现一次的字符，并返回索引，如果这样的字符不存在返回-1，不允许使用字典
输入： abcacd
输出： 1
解释： 出现一次的字符是 b 和 d，b是第一个出现的
思路分析
必须遍历字符串，统计每个字符出现的次数，然后再遍历一遍字符串，如果某个字符出现的次数是1，则返回这个字符的索引。
题目要求不允许使用字典，因此，需要换一个数据类型来存储字符串出现的次数，这里可以使用列表，创建一个长度为26的列表，元素初始化为0。小写字母一共有26个，字符a 的ascii码10进制是97，字符z的ascii码10进制是122，遍历过程中，先将字符转成ascii码十进制数值并减去97，就得到了在列表中的索引，列表索引位置元素加1，这样，就解决了字符出现次数的记录问题。
再次遍历字符串时，还是对字符进行转换，转换后的数值作为索引找到列表中的值，如果值为1，那么这个字符就是出现次数为1的字符。
示例代码
# coding=utf-8
def find_first_single_char(string):
"""
寻找字符串中第一个只出现一次的字符
:param string:
:return:
"""
# 记录每个字符出现的次数
lst = [0 for i in range(26)]
for item in string:
lst[ord(item) - 97] +=1
for index, item in enumerate(string):
if lst[ord(item) - 97] == 1:
return index
return -1
if __name__ == '__main__':
print(find_first_single_char('abcacd'))
7.10 字符串相乘
题目要求
有两个字符串，str1,str2，内容为数值，数值均大于0请编写算法计算两个字符串相乘的结果，不可以使用大数据类型，不可以把字符串直接转成整数来处理。
输入: str1='3' str2='5'
输出: '15'
输入: str1='32' str2='15'
输出: '480'
输入: str1='323434223434234242343'
str2='15492828424295835983529'
输出:
思路分析
题目要求的很明确，不可以直接把字符串转成整数然后相乘，所以int(str1)*int(str2)是不被允许的。
不止如此，第三个示例里，数值已经非常大，已经超出了264 ，在计算过程中，中间结果也非常的大，在大多数编程语言里，你找不到合适的数据类型来存储这样的数据，因此，只能用字符串来保存。
先来看第一个示例， 3 乘 5， 简单的乘法，在看第二个示例， 32 乘 15 ，小学的时候都学过如何计算乘法，32*5 + 32*10 =480。需要编写一个算法，来实现这个计算过程，但是要注意，32*5的结果必须保存成为字符串"160",为什么不能保存成数值型数据160呢？就32*15来说，保存成数值是没有问题的，可对于第三个示例，在计算中间结果时，得到的结果太大了，根本无法用数值型变量保存，因此必须保存成字符串。
最简单的乘法
我们需要先实现一个简单的字符串乘法，函数定义为
def single_str_multi(str1, single):
"""
single是一个小于10的数值, 例如 323354 * 4
:param str1: 基础数值
:param single: 单个数值
:return:
"""
pass
如果总是可以保证single是一个小于10的数值，那么计算起来就简单容易的多了，计算时，反向遍历str1，每个数值分别与single相乘，计算进位和当前位置留下的值，并存入一个列表中，遍历结束后，要注意检查最后一次进位的值，算法实现如下
def single_str_multi(str1, single):
"""
single是一个小于10的数值, 例如 323354 * 4
:param str1: 基础数值
:param single: 单个数值
:return:
"""
pre_sum = 0 # 进位
single = int(single)
res_lst = []
for item in reversed(str1):
# 每次计算都要考虑上一次计算结果的进位
item_num = int(item) * single + pre_sum
pre_sum = item_num / 10 # 计算进位
curr_num = item_num % 10 # 计算当前位置的值
res_lst.insert(0, str(curr_num))
if pre_sum > 0:
res_lst.insert(0, str(pre_sum))
return ''.join(res_lst)
有了single_str_multi函数做基础，就可以实现最终的字符串相乘算法了，定义函数
def str_multi(str1, str2):
pass
这一次，反向遍历str2，每次遍历都得到一个单一数值single，这样恰好可以调用single_str_multi 函数，但是需要注意的是每次得到的结果都要根据single的位置补0，如果single是str2的百位，那么计算结果就要乘100。
字符串相加
每次调用single_str_multi函数，得到的都是中间结果，这些结果必须加在一起才能得到乘法的结果，因此，我们还需要一个计算字符串加法的函数，前面的计算二进制加法的练习题已经有过讲解，代码稍作修改即可
def str_sum(str1, str2):
"""
计算两个字符串的加法
:param str1:
:param str2:
:return:
"""
# 先补齐
str_1_length = len(str1)
str_2_length = len(str2)
if str_1_length < str_2_length:
str1 = "0"*(str_2_length - str_1_length) + str1
else:
str2 = "0"*(str_1_length - str_2_length) + str2
# 进行计算
index = len(str1) - 1
pre_num = 0 # 记录进位
res_lst = [] # 记录结果
# 反向遍历
while index >= 0:
item_1 = int(str1[index])
item_2 = int(str2[index])
item_sum = item_1 + item_2 + pre_num
pre_num = item_sum/10
curr_num = item_sum % 10
# 新的计算结果插入到结果的第一位
res_lst.insert(0, str(curr_num))
index -= 1
if pre_num == 1:
res_lst.insert(0, '1')
return ''.join(res_lst)
字符串相乘
万事具备，之前东风，最后来实现str_multi函数
def str_multi(str1, str2):
"""
字符串相乘
:param str1:
:param str2:
:return:
"""
res = '0'
for index, item in enumerate(reversed(str2)):
if item == '0': # 为0时不用计算
continue
# 一定要补0
single_res = single_str_multi(str1, item) + '0'*index
# 每次相乘结果要相加
res = str_sum(res, single_res)
return res
全部代码
def str_sum(str1, str2):
"""
计算两个字符串的加法
:param str1:
:param str2:
:return:
"""
# 先补齐
str_1_length = len(str1)
str_2_length = len(str2)
if str_1_length < str_2_length:
str1 = "0"*(str_2_length - str_1_length) + str1
else:
str2 = "0"*(str_1_length - str_2_length) + str2
# 进行计算
index = len(str1) - 1
pre_num = 0 # 记录进位
res_lst = [] # 记录结果
# 方向遍历
while index >= 0:
item_1 = int(str1[index])
item_2 = int(str2[index])
item_sum = item_1 + item_2 + pre_num
pre_num = item_sum//10
curr_num = item_sum % 10
# 新的计算结果插入到结果的第一位
res_lst.insert(0, str(curr_num))
index -= 1
if pre_num == 1:
res_lst.insert(0, '1')
return ''.join(res_lst)
def single_str_multi(str1, single):
"""
single是一个小于10的数值, 例如 323354 * 4
:param str1: 基础数值
:param single: 单个数值
:return:
"""
pre_sum = 0 # 进位
single = int(single)
res_lst = []
for item in reversed(str1):
# 每次计算都要考虑上一次计算结果的进位
item_num = int(item) * single + pre_sum
pre_sum = item_num // 10 # 计算进位
curr_num = item_num % 10 # 计算当前位置的值
res_lst.insert(0, str(curr_num))
if pre_sum > 0:
res_lst.insert(0, str(pre_sum))
return ''.join(res_lst)
def str_multi(str1, str2):
"""
字符串相乘
:param str1:
:param str2:
:return:
"""
res = '0'
for index, item in enumerate(reversed(str2)):
if item == '0': # 为0时不用计算
continue
# 一定要补0
single_res = single_str_multi(str1, item)
if single_res != '0':
single_res += '0'*index
# 每次相乘结果要相加
res = str_sum(res, single_res)
return res
if __name__ == '__main__':
print(str_multi('323434223434234242343', '15492828424295835983529'))
7.11 整数翻转
题目要求
def reverse_int(number):
已知函数reverse_int，参数number是正整数，实现函数，将number翻转并返回,不要使用str函数将数值转成字符串
示例
输入: 12345
输出: 54321
思路分析
题目要求不能使用str函数将数值转成字符串，因为这样做实在是太简单了，下面是这样处理的示例代码
def reverse_int(number):
str_number = str(number)
lst = list(str_number)
lst = lst[::-1]
return int("".join(lst))
print(reverse_int(12345))
- 将数值转成字符串
- 将字符串转成list
- 翻转list，注意翻转方法lst[::-1]
- 使用join方法连接列表里的字符串，并最终转成int类型数据返回
既然不允许这样做，那么，我们就考虑别的方法
对于整数的操作，你一定要考虑求模运算和除法运算
- 对10求模可以得到一个整数的个位数
- 一个数除以10，可以去掉个位数
题目要求翻转，那么，我们可以先对10求模，就得到了个位数，而这个个位数就是翻转后的最高位，然后在除10，就去除了个位数。
讲过上面两步操作，我们得到了两个数，一个是个位数，一个是去除个位数后剩余的部分，对于这个剩余的部分，我们可以继续上面的两步操作，这样，我们就逆序的得到了每一位数，每次求模得到得数就可以组成题目所要求的翻转后的数
示例代码
def reverse_int(number):
reverse_number = 0
tmp = number
while tmp > 0:
end_number = tmp%10 # 得到个位数
tmp = tmp//10 # 去除个位数后剩余的部分
reverse_number = reverse_number*10 + end_number # 组建翻转后的数
return reverse_number
print(reverse_int(12345))
7.12 时间转换
题目要求
请将下列形式的字符串转换成秒数
2小时3分55秒 =》 7435
35分21秒 =》 2121
55秒 =》 55
思路分析
1小时=3600秒
1分钟=60秒
将小时的单位，分钟的单位都转成秒，然后相加，就得到了秒数。可以用"小时"，"分", "秒"作为分割符分隔字符串，得到时间单位前面的数值。不过这样操作起来，比较麻烦。
我想到一个简单的办法，先将字符串中的"小"字替换掉，然后利用正则表达式模块的split方法分割字符串。
import re
string = "1时13分15秒"
arrs = re.split('[时分秒]', string)
print(arrs)
程序输出结果为
['1', '13', '15', '']
1*3600 + 13*60 + 15 = 4395
实例代码
import re
def convert_time(time_str):
seconds = 0
if not time_str:
return seconds
time_str = time_str.replace('小', '')
arrs = re.split('[时分秒]', time_str)
arrs = arrs[:-1]
base = 1
for item in reversed(arrs):
seconds += base*int(item)
base *= 60
return seconds
if __name__ == '__main__':
print(convert_time('2小时3分55秒'))
print(convert_time('35分21秒'))
print(convert_time('55秒'))
7.13 字典里的value (2)
题目要求
有一个字典，保存的是学生各个编程语言的成绩，内容如下
data = {
'python': {'上学期': '90', '下学期': '95'},
'c++': ['95', '96', '97'],
'java': [{'月考':'90', '期中考试': '94', '期末考试': '98'}]
}
各门课程的考试成绩存储方式并不相同，有的用字典，有的用列表，但是分数都是字符串类型，请实现函数transfer_score(score_dict)，将分数修改成int类型
思路分析
不同于上一篇，本次字典的结构变得复杂了，但思路不变，仍然要遍历字典，只是在遍历时，要根据value的类型决定如何进行处理，如果value的类型是字典，那么则仍然按照上一篇的方法进行处理，如果value的类型是列表，则需要对列表里的元素类型进行判断，如果是字符串，则直接转换，如果是字典，则需要按照上一篇的方法进行处理，这次，我采用递归函数进行处理。
示例代码
import pprint
def transfer_score(data):
# 如果data是字典
if isinstance(data, dict):
for key, value in data.items():
data[key] = transfer_score(value)
return data
# 如果data 是列表
if isinstance(data, list):
data_lst = []
for item in data:
data_lst.append(transfer_score(item))
return data_lst
if isinstance(data, str):
return int(data)
if __name__ == '__main__':
data = {
'python': {'上学期': '90', '下学期': '95'},
'c++': ['95', '96', '97'],
'java': [{'月考': '90', '期中考试': '94', '期末考试': '98'}]
}
data = transfer_score(data)
pprint.pprint(data)
7.14统计代码行数
题目要求
实现函数get_py_program_count，统计指定目录下所有的python文件代码行数
def get_py_program_count(py_path):
pass
思路分析
题目要求统计代码函数，但是一个文件里代码有多少行并没有一个明确的定义，这里就可以有自由发挥的空间，我自己的定义是文件里只要不是空行，只要不是以 # 开头，就算一行有效代码，读取一个文件，逐行进行判断，如果是有效代码，代码行数加1
先实现一个函数，统计一个文件里的代码行数，题目要求的是计算指定目录下所有文件代码行数，那么只需要写一个函数，获取指定目录下所有python脚本的目录，然后用for循环逐个文件计算代码行数并累加即可
示例代码
import os
def get_file_lst(py_path, suffix):
"""
遍历指定文件目录下的所有指定类型文件
:param py_path:
:return:
"""
file_lst = []
for root, dirs, files in os.walk(py_path):
for file in files:
file_name = os.path.join(root, file)
if file_name.endswith(suffix):
file_lst.append(file_name)
return file_lst
def get_program_line_count(file_name):
"""
返回单个py脚本的代码行数
:param filename:
:return:
"""
# 存储代码行数
count = 0
with open(file_name, 'r', encoding='utf-8')as f:
for line in f:
line = line.strip()
if not line:
continue
if line.startswith("#"):
continue
count += 1
return count
def get_py_program_count(py_path):
# 获取指定目录下所有的python脚本
file_lst = get_file_lst(py_path, '.py')
count = 0
# 遍历列表,获取单个python脚本的代码行数
for file_name in file_lst:
count += get_program_line_count(file_name) # 累加代码函数
return count # 返回代码总函数
if __name__ == '__main__':
py_path = '/Users/kwsy/PycharmProjects/pythonclass'
print(get_py_program_count(py_path))
7.15 提取单词
题目要求
从字符串里提取单词，例如”this is a book“，将单词放到列表里，要求是不能使用split函数
思路分析
字符串相关的算法，往往都需要对字符串进行遍历，设置一个标识位 b_start，初始值设置为False，表示遍历过程中还没有遇到单词
遍历过程中，遇到字母后，b_start修改为True,记录单词开始的位置，遇到空格后，b_start修改为False，记录单词结束的位置，根据开始位置和结束位置进行字符串截取，即可获得单词
示例代码
string = " this is a book"
lst = []
# 记录单词开始和结束的位置
b_start = False
start = 0 # 单词开始的位置
end = 0 # 单词结束的位置
for index, item in enumerate(string):
if item != " ":
if b_start:
continue
else:
b_start = True
start = index
else:
if b_start:
b_start = False
end = index - 1
lst.append(string[start:end+1])
if b_start:
lst.append(string[start:])
print(lst)
7.16 学生成绩分析
题目要求
文件score.txt中存储了学生的考试信息，内容如下
小明,98
小刚,90
小红,91
小王,98
小刘,80
请写代码，读取文件数据，并进行如下分析
- 最高分和最低分分别是多少？
- 得最高分的学生有几个？ 得最低分的学生有几个
- 平均分是多少？
思路分析
读取文件，这没啥可说的，剩下的是简单的统计，不要被文件迷惑，你读取数据以后，转换成列表，不就是你所熟悉的事物了么，如果列表还不熟悉，那你应该好好复习一下列表了
示例代码
def read_file(filename):
"""
读取文件数据
:param filename:
:return:
"""
f = open(filename, 'r', encoding='utf-8')
datas = f.readlines()
datas = [item.strip() for item in datas]
f.close()
return datas
def analse_score():
datas = read_file('score.txt')
score_lst = []
for item in datas:
score = int(item.split(',')[1])
score_lst.append(score)
max_score = max(score_lst)
min_score = min(score_lst)
max_score_count = score_lst.count(max_score)
min_score_count = score_lst.count(min_score)
avg = sum(score_lst)/len(score_lst)
print(max_score, min_score)
print(max_score_count, min_score_count)
print(avg)
if __name__ == '__main__':
analse_score()
7.17 学生成成绩分析
题目要求
文件score.txt中存储了学生的考试信息，内容如下
小明,98,96
小刚,90,94
小红,90,94
小王,98,96
小刘,80,90
小赵,90,96
第二列是数学成绩，第三列是语文成绩
请写程序分析：
- 哪些同学语文成绩是相同的？
- 哪些同学数学成绩是相同的？
- 哪些同学语文和数学成绩都是相同的？
- 总分最高的同学是谁，分数是多少？
- 总分的平均分是多少？
### 思路分析
都是简单的数据统计分析，谈不上思路，跟着代码过一遍，相信你可以理解代码的意图和作用
### 示例代码
def read_file(filename):
"""
读取文件数据
:param filename:
:return:
"""
f = open(filename, 'r', encoding='utf-8')
datas = f.readlines()
datas = [item.strip() for item in datas]
f.close()
return datas
def analse_score():
datas = read_file('score.txt')
stu_lst = []
for data in datas:
arrs = data.split(',')
name = arrs[0]
shuxue = int(arrs[1])
yuwen = int(arrs[2])
stu_lst.append({'name': name, 'shuxue': shuxue, 'yuwen': yuwen})
yuwen_dict = {}
shuxue_dict = {}
ys_dict = {}
max_score_sum = 0
stu_score_sum = 0
for stu in stu_lst:
name = stu['name']
shuxue = stu['shuxue']
yuwen = stu['yuwen']
score_sum = shuxue + yuwen
stu_score_sum += score_sum
if score_sum > max_score_sum:
max_score_sum = score_sum
yuwen_dict.setdefault(yuwen, [])
yuwen_dict[yuwen].append(name)
shuxue_dict.setdefault(shuxue, [])
shuxue_dict[shuxue].append(name)
ys_dict.setdefault((shuxue, yuwen), [])
ys_dict[(shuxue, yuwen)].append(name)
for yuwen, name_lst in yuwen_dict.items():
if len(name_lst) > 1:
print(yuwen, name_lst)
print("*"*20)
for shuxue, name_lst in shuxue_dict.items():
if len(name_lst) > 1:
print(shuxue, name_lst)
print("*"*20)
for score, name_lst in ys_dict.items():
sum_score = sum(score)
if sum_score == max_score_sum:
print("总分最高的学生", name_lst, score)
if len(name_lst) > 1:
print(score, name_lst)
print(round(stu_score_sum/len(stu_lst), 2))
if __name__ == '__main__':
analse_score()
7.18 投票选班长
题目要求
文件data里存储了投票选班长的选票情况
小红
小刚
小明
小明
小刚
小刘
小红
小张
小王
小明
请写代码分析
- 一共有多少人参加了班长选举？
- 这些人分别得了多少选票？
### 思路分析
统计有多少人参加了班长选举，将名字存储到集合中，集合的大小就是答案
统计分别得了多少票，先创建一个空字典，以人名做key，0做value,遍历字典，增加value的值，最终就可以得到选举情况
示例代码
def read_file(filename):
"""
读取文件数据
:param filename:
:return:
"""
f = open(filename, 'r', encoding='utf-8')
datas = f.readlines()
datas = [item.strip() for item in datas]
f.close()
return datas
def toupiao():
datas = read_file('data')
info = {}
for name in datas:
if name not in info:
info[name] = 1
else:
info[name] += 1
print(len(info))
print(info)
def toupaio2():
datas = read_file('data')
info = {}
for name in datas:
if name not in info:
info[name] = 0
info[name] += 1
print(len(info))
print(info)
def toupiao3():
datas = read_file('data')
info = {}
for name in datas:
info.setdefault(name, 0)
info[name] += 1
print(len(info))
print(info)
if __name__ == '__main__':
toupiao3()
7.19 水果账单
题目要求
文件fruits_saturday.txt中保存了小明周六买水果的消费情况
苹果 30.6
香蕉 20.8
葡萄 15.5
草莓 30.2
樱桃 43.9
请写程序分析
- 这些水果一共花费了多少钱？
- 花费最多的水果是哪个
文件fruits_sunday.txt 中保存了小明周日买水果的消费情况
苹果 20.6
香蕉 16.8
樱桃 30.5
大鸭梨 10.5
火龙果 18.8
请写程序分析
- 周六，周日两天，一共买了多少水果
- 周六，周日两天都买的水果有哪些？
- 哪些水果是周日买了而周六没有买的？
- 两天一共花费了多少钱买水果
- 哪个水果花费的钱最多，花了多少？
思路分析
首先，需要写一个函数，读取账单数据，以字典形式返回消费数据，接下来，则是各种统计操作，需要数量的使用字典，集合这两种数据类型
示例代码
def read_fruits(filename):
info = {}
with open(filename, 'r', encoding='utf-8') as f:
for line in f:
arrs = line.strip().split()
name = arrs[0]
money = float(arrs[1])
info[name] = money
return info
def func1():
info = read_fruits('fruits_saturday.txt')
# 这些水果一共花费了多少钱？
values = list(info.values())
print(sum(values))
# 花费最多的水果是哪个
max_money = 0
name = ''
for key, value in info.items():
if value > max_money:
max_money = value
name = key
print(name)
def func2():
info1 = read_fruits('fruits_saturday.txt')
info2 = read_fruits('fruits_sunday.txt')
set1 = set(list(info1.keys()))
set2 = set(list(info2.keys()))
# 周六，周日两天，一共买了多少水果
print(set1.union(set2))
# 周六，周日两天都买的水果有哪些？
print(set1.intersection(set2))
# 哪些水果是周日买了而周六没有买的？
print(set2.difference(set1))
# 两天一共花费了多少钱买水果
print(sum(list(info1.values())) + sum(list(info2.values())))
# 哪个水果花费的钱最多，花了多少？
name = ''
max_money = 0
for key, value in info1.items():
if value > max_money:
max_money = value
name = key
for key, value in info2.items():
if value > max_money:
max_money = value
name = key
print(name)
if __name__ == '__main__':
func1()
func2()
7.20 文件读取解析
已知一个文件名为ip.txt的文件，里面存储了大量ip地址
192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.1
192.168.0.4
192.168.0.5
192.168.0.5
192.168.0.2
192.168.0.2
192.168.0.5
请编写函数，读取文件并分析数据，根据ip出现次数进行排序，程序最终输出ip 和 出现次数，从小到大
思路分析
读取数据，统计每一个ip出现的次数，将统计结果存储到字典中，处理文件中的数据时，时刻要记住，文件中的每一行数据最后都会有 \n 换行符，一定要用strip函数将这个换行符去掉
我们无法对字典进行排序，所以，遍历字典，将字典中的数据存储到列表中，每一项都是一个元组，元组内存储ip 和 出现次数，内容如下
[('192.168.0.1', 2), ('192.168.0.2', 3), ('192.168.0.3', 1), ('192.168.0.4', 1), ('192.168.0.5', 3)]
对列表进行排序，可以指定排序的key，这里使用lambda表达式，取列表里每一个元组内的第二个元素做为排序比较时的key
示例代码
def analyse_ip(filename):
ip_info = {}
with open(filename) as f:
for line in f:
ip = line.strip()
ip_info.setdefault(ip, 0)
ip_info[ip] += 1
lst = []
for key, value in ip_info.items():
lst.append((key, value))
lst.sort(key=lambda item:item[1])
for item in lst:
print(item)
if __name__ == '__main__':
analyse_ip('ip.txt')
7.21 有效电话号码
题目要求
给定一个包含电话号码列表（一行一个电话号码）的文本文件，假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字）
文本文件里的内容如下：
987-123-4567
123 456 7890
(123) 456-7890
(125) 902-2934
987-123 4997
请读取文件并输出符合要求的电话
思路分析
对于电话，email，身份证等信息，有着明确的格式要求，这类信息都可以用正则表达式来判断是否符合格式要求
python里正则表达式要用到re这个模块，先创建一个pattern
pattern = re.compile("\d{3}-\d{3}-\d{3}|\(\d{3}\) \d{3}-\d{3}")
对于文件里的一行内容，则使用pattern.match方法来判断该行内容是否匹配正则表达式，如果符合则返回一个_sre.SRE_Match 类型的对象，如果不匹配，则返回None
示例代码:
# coding=utf-8
import re
# 定义正则表达式
pattern = re.compile("\d{3}-\d{3}-\d{3}|\(\d{3}\) \d{3}-\d{3}")
print type(pattern.match("987-123-4567"))
with open('phones')as fileobj:
lines = fileobj.readlines()
for line in lines:
if pattern.match(line):
# strip函数去掉line末尾的换行符
print(line.strip())
7.22 旋转数组
题目要求
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数，要求使用空间复杂度为 O(1) 的原地算法
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
思路分析
思路1，多次移动
如果没有空间复杂度为O(1)的要求，这个题目非常简单，简单的做一下切片处理就可以了
lst = [1, 2, 3, 4, 5, 6, 7]
lst = lst[len(lst)-3:] + lst[0:len(lst)-3]
print(lst)
但切片的过程就是一个复制的过程，我们使用了O(n)的空间，与题目要求不符。
我们只能使用一个O(1)的空间来临时存储数据，简单说，一次只能存储一个数字，但要向右移动K个位置。如果我们能找到一种算法，这个算法执行一次，只将数组向右移动1位，移动k个位置只需要执行这个算法K次就可以了。
考虑移动1位就简单了，用一个临时变量tmp将lst[-1]保存下来，然后从后向前，逐个向后移动，最后，将lst[0]赋值为tmp
tmp = lst[-1]
for i in range(len(lst)-1, 0, -1):
lst[i] = lst[i-1]
lst[0] = tmp
经过上面的算法，数组就从[1,2,3,4,5,6,7]变成了[7,1,2,3,4,5,6],如果希望将数组向右移动K个位置，只需要执行K次就可了
def move_ele_1(lst, k):
for j in range(k):
tmp = lst[-1]
for i in range(len(lst)-1, 0, -1):
lst[i] = lst[i-1]
lst[0] = tmp
if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7]
move_ele_1(lst, 3)
print(lst)
思路2， 原地翻转
将数组分为两个区域，第一个区域是从0到len(lst)-k-1, 余下的是第二个区域，两个区域分别做一次翻转，然后将整个数组做一次翻转，算法的过程如下
[1, 2, 3, 4, 5, 6, 7] 原始数据
[4, 3, 2, 1, 5, 6, 7] 第一个区域翻转
[4, 3, 2, 1, 7, 6, 5] 第二个区域翻转
[5, 6, 7, 1, 2, 3, 4] 整体翻转
一旦有了思路，算法就很容易写出来，但要注意处理边界条件
def reverse_lst(lst, start, end):
for i in range(0, (end-start)//2 + 1):
tmp = lst[start+i]
lst[start+i] = lst[end-i]
lst[end-i] = tmp
def move_ele_2(lst, k):
split_index = len(lst) - k - 1
reverse_lst(lst, 0, split_index)
print(lst)
reverse_lst(lst, split_index+1, len(lst)-1)
print(lst)
reverse_lst(lst, 0, len(lst)-1)
if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7]
move_ele_2(lst, 3)
print(lst)
7.23 合并文件
题目要求
已知一个列表里存储了若干个文件的名字
lst = ['1.txt', '2.txt', '3.txt']
请写程序，将列表里的文件内容合并到一个文件中，文件命名为'all.txt'
思路分析
写一个for循环，遍历列表lst，逐个打开文件，逐行读取文件里的信息，将读取的每一行数据写入到all.txt文件中，就是这么简单
示例代码
lst = ['1.txt', '2.txt', '3.txt']
f = open('all.txt', 'w')
for filename in lst:
r_file = open(filename)
for line in r_file:
f.write(line.strip() + '\n')
r_file.close()
f.close()
7.24 拆分文件
题目要求
已知一个文件名为"all.txt",其内容为
2222
111
111
444
3333
6666
8888
请写程序拆分这个文件，文件里的内容，以1开头的，就写入到1.txt文件中，以2开头的内容，写入到2.txt文件中，依次类推
思路分析
打开文件，逐行读取文件内容，解析出一行内容的第一个字符，用第一个字符串拼接处要写入的文件名字，然后以a+方式打开文件，将这一行文件写入到文件中
示例代码
f = open('all.txt', 'r')
for line in f:
start = line[0]
filename = start + ".txt"
with open(filename, 'a+') as w_file:
w_file.write(line.strip()+"\n")
f.close()
8 地狱难度算法练习题
8.1 删除有序序列中的重复项
题目要求
已知一个有序序列,请原地删除序列中重复出现的元素,返回删除重复元素后的序列长度。
只能使用 O(1) 额外空间来完成这个任务，例如 [0,0,1,1,1,2,2,3,3,4,4,4,5]，最终返回的长度是6, 序列前6个元素是 0 1 2 3 4 5
思路分析
已知条件如下：
- 序列有序
- 只能使用O(1)额外空间，必须原地删除
- 需要返回删除重复元素后的长度，如果长度为N，那么序列前N个元素没有重复元素
设置一个哨兵index，初始值赋为0。用一个for循环从索引1开始遍历lst，i做迭代变量， 如果lst[i]!=lst[index]，就说明lst[i]是一个比lst[index]大的元素，它应该被放置在index+1的位置上
将lst[i] 放置在index+1位置上以后，要向右移动哨兵的位置，执行index += 1，这样，即便lst[i]这个值在后面重复出现了，可此时lst[index]=lst[i]，所以重复出现的值会被忽略掉，直到遇到一个与lst[index]不相等的元素，再次移动哨兵
示例代码
def remove_duplicate(lst):
index = 0
for i in range(1, len(lst)):
if lst[index] != lst[i]:
lst[index + 1] = lst[i]
index += 1
return index + 1
if __name__ == '__main__':
lst = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5]
index = remove_duplicate(lst)
print index
print lst[:index]
8.2 组合总数
题目要求
已知一个无重复元素的序列,给定一个目标数,找出序列中所有可以使数字和未目标数的组合。
序列中的元素可以被多次选用,不能出现重复的组合, 序列中的元素和目标数都是正整数。
例如序列 [2, 3, 5]， 目标值为8， 最终的组合有
(2, 3, 3)
(3, 5)
(2, 2, 2, 2)
思路分析
编程不是拿着画笔随心所欲的在画板上涂抹，也不存在固定的方法帮你完成具体的问题，做练习题的目的是通过这些练习题锻炼你的思维，当你建立起编程的思维以后，你也就不在乎什么具体方法和套路，面对具体问题时，你将有能力进行分析。
当问题复杂无从下手时，你可以从问题的边界处入手，题目没有对组合里的元素个数做限制，那么你就先考虑组合里只有一个元素的情况，题目就变成了从序列中找到1个元素，这个元素的值等于目标元素，这样，问题不就变得简单了么
接下来考虑两个元素的情况，从序列中找到两个数，这两个数的和等于目标数target，先随便从序列中选定一个数，假设这个数是i, 那么接下来要做的就是从序列中找到1个元素且这个元素等于target - i
接下来思考三个元素的情况，从序列中找到三个数，这三个数的和等于目标数target，你可以先随便从序列中选定一个数，假设这个数是i，那么接下来要做的就是从序列中找到两个元素且这两个元素的和等于target - i
新的问题，总是转化为老的问题，而最老的那个问题，从序列中找到一个元素且这个元素的值等于目标值是非常容易解决的。
示例代码
# coding=utf-8
def combination_sum(lst, target):
combination_lst = []
for item in lst:
if item == target:
combination_lst.append([item])
elif item > target:
continue # 单个元素都大于target,这个元素放在哪个组合里,组合之和都必然比target大
else:
other = target - item
res_lst = combination_sum(lst, other) # 新问题转化成老问题
# res_lst 是list, 里面的元素还是list,且和等于other
for tmp_lst in res_lst:
tmp_lst.append(item) # 加上item后,组合之和等于target
combination_lst.extend(res_lst) # 所有组合都放在combination_lst
return combination_lst
def remove_duplicate(lst):
combination_set = set()
for item in lst:
item.sort() # 先排序
combination_set.add(tuple(item)) # list 没有hash值,不能放到set中
return combination_set
if __name__ == '__main__':
lst = [2, 3, 5]
res_lst = remove_duplicate(combination_sum(lst, 8))
for item in res_lst:
print(item)