习题汇总
每天一练好棒棒~~~~~~~~~~~
转置矩阵(方阵)
给定一个3*3方阵，求其转置矩阵，如
1 2 3 1 4 7
4 5 6 ==>> 2 5 8
7 8 9 3 6 9
规律：对角线不动，a[i][j] <==> a[j][i]，而且到了对角线，就停止，去做下一行，对角线上的元素不变
方法1
matrix = [[1,2,3], [4,5,6], [7,8,9]] # 构造方阵
print(*matrix, sep='\n')
count = 0
for i, row in enumerate(matrix): # i代表方阵元素的横坐标
for j, col in enumerate(matrix[i]): # j代表方阵的纵坐标
if j < i:
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
count += 1
print(count)
print(*matrix, sep='\n')
#以上代码的运行结果：
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
9
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]
方法2：
基于方法一改进，内层循环的范围可以缩小；因为j == i的时候就是到达对角线元素的时候，所以需要操作的范围为j < i；方法一中只有j < i我们才有动作，j >= i的区间白白遍历了，什么都没做。
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(*matrix, sep='\n')
count = 0
for i in range(len(matrix)):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
count += 1
print(count)
print(*matrix, sep='\n')
#以上代码的运行结果：
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
3 # 次数明显下降，这是真正需要交换元素位置的操作所需的次数
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]
转置矩阵(任意矩阵)
给定一个任意矩阵，求其转置矩阵，如
1 2 3 1 4
4 5 6 <==> 2 5
3 6
这里着重强调不是方阵。解决此问题，我们要用到：
enumerate(iterable[, start]) -> iteraator for index, value of iterable
返回一个可迭代对象，将原有可迭代对象的元素和从start开始的数字进行配对。
算法1：
原理就是，扫描原矩阵的第一行，作为转置后的矩阵第一列。
# 定义一个矩阵，不考虑稀疏矩阵
# 不是稀疏矩阵的意思就是
matrix = [[1,2,3], [4,5,6]]
print(*matrix, sep='\n')
tm = []
for row in matrix: # 迭代matrix每一行
for j, col in enumerate(row): # 迭代matrix每一行的每个元素
if len(tm) < j+1: # matrix有几列就要为tm增加多少行
tm.append([])
tm[j].append(col) # tm的每一行分别append了row的元素
print(*tm, sep='\n')
算法2：基于算法1改进
是否可以一次性开辟tm所需内存空间。
如果开辟好了之后，那么原矩阵的元素直接移动到tm上就行了。
matrix = [[1,2,3], [4,5,6]]
print(*matrix, sep='\n')
tm = [[0 for col in range(len(matrix))] for j in range(len(matrix[0]))]
for i in range(len(tm)):
for j in range(len(tm[0])):
tm[i][j] = matrix[j][i]
print(*tm, sep='\n')
效率测试
import timeit
def solution01():
matrix = [[1, 2, 3], [4, 5, 6]]
# print(*matrix, sep='\n')
tm = []
for row in matrix:
for j, col in enumerate(row):
if len(tm) < j + 1:
tm.append([])
tm[j].append(col)
# print(*tm, sep='\n')
print(timeit.timeit(stmt='solution01()', setup='from __main__ import solution01', number=10000))
# 以上代码的运行结果：
0.029389293999999996
import timeit
def solution02():
matrix = [[1,2,3], [4,5,6]]
# print(*matrix, sep='\n')
tm = [[0 for col in range(len(matrix))] for j in range(len(matrix[0]))]
for i in range(len(tm)):
for j in range(len(tm[0])):
tm[i][j] = matrix[j][i]
# print(*tm, sep='\n')
print(timeit.timeit(stmt='solution02()', setup='from __main__ import solution02', number=10000))
# 以上代码的运行结果：
0.04870926800000001
可以看出，算法1的效率更高。可是事实真的如此吗？我们再看看一面的测试。
构造一个大矩阵，再测试看看
matrix = [
[1, 2, 3], [4, 5, 6], [1, 2, 3], [4, 5, 6],
[1, 2, 3], [4, 5, 6], [1, 2, 3], [4, 5, 6],
[1, 2, 3], [4, 5, 6], [1, 2, 3], [4, 5, 6],
[1, 2, 3], [4, 5, 6], [1, 2, 3], [4, 5, 6]
]
0.15288557400000002
0.10139942099999999
测试发现，当矩阵规模增加到4*4之后，方法二的优势就开始显现了
矩阵规模越大，先开辟空间的效率比一次次的append要高。4*4之前的不高是因为，开辟空间多用遍历来生成矩阵，这里多消耗了一点时间。
进一步改善代码
随机生成矩阵，而非手动定义
import random
matrix = [[random.randint(1,9) for j in range(4)] for i in range(4)]
格式输出
编写一个函数，接受一个参数n，n为正整数，上下三角两种打印方式。要求数字必须对齐。
# 上三角
1
2 1
3 2 1
4 3 2 1
5 4 3 2 1
6 5 4 3 2 1
7 6 5 4 3 2 1
8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
11 10 9 8 7 6 5 4 3 2 1
12 11 10 9 8 7 6 5 4 3 2 1
思路1：
一行行打印，前面追加空格。每一个空格的宽度等于数字字符串的宽度。
- 先得到一个方阵
def triangle_print(n=12):
for x in range(n):
for y in range(n, 0, -1):
print(y, end=' ')
print()
- 再把每一行不需要的数字替换成空格
def triangle_print(n=12):
for x in range(n):
for y in range(n, 0, -1):
if y > x + 1:
print(' ' * len(y), end=' ') # ' ' * len(y): 两位数和1位数所需占位空格不一样
else:
print(y, end=' ')
print()
思路2：
使用format的右对齐打印，关键是要先算出最后一行的长度，才能做右对齐；最后因为最后一行已经提前算好，就没有必要在循环体内计算最后一行了，结束循环后直接打印最后一行就好。
为什么，计算每一行的宽度，要使用生成最后一行，然后使用len () 才能得出？
根据n，数学公式也可以算出宽度；不过太麻烦了，数字类字符串在不同位数上拥有不同的宽度，所以还要分类去计算，太麻烦。
def triangle_print(n):
tail = " ".join((str(i) for i in range(n, 0, -1))) # 生成最后一行
width = len(tail)
for i in range(1, n):
# 右对齐打印
print("{:>{}}".format(" ".join((str(i) for i in range(i, 0, -1))), width))
print(tail)
triangle_print(12)
def triangle_print(n):
g = [str(x) for x in range(n, 0, -1)] # 使用列表生成式代替生成器表达式
tail = " ".join(g)
width = len(tail)
for i in range(1, n):
print("{:>{}}".format(" ".join(g[n-i:]), width)) # 借用列表的切片来取代生成器表达式
print(tail)
triangle_print(12)
思路3：
基于思路2，能够每一行不用重新计算，基于tail切片
def triangle_print(n):
g = [str(x) for x in range(n, 0, -1)]
tail = " ".join(g)
width = len(tail)
# 确定起始位置、步长、还有位数发生变化的数字
points = {10 ** x for x in range(1, 3)}
step = 2
start = -1
for i in range(1, n):
# 基于tail切片
print("{:>{}}".format(tail[start:], width))
if i + 1 in points:
step += 1 # 位数一增加，start移动的步长就要跟着增加
start -= step # start使用负索引，步长是为了把start定位到下一行的起始点，步长包括位数+空格
print(tail)
triangle_print(12)
那么打印下三角呢？
# 下三角
12 11 10 9 8 7 6 5 4 3 2 1
11 10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
8 7 6 5 4 3 2 1
7 6 5 4 3 2 1
6 5 4 3 2 1
5 4 3 2 1
4 3 2 1
3 2 1
2 1
1
核心思想：遇到一个空格，就将前面全部补成空格，后面的数字和空格全部打印
def triangle_print(n):
g = [str(i) for i in range(n, 0, -1)]
tail = " ".join(g)
print(tail) # 计算得到第一行
for i, c in enumerate(tail):
if c == " ": # 遍历第一行的空格
print(" "*i, tail[i+1:]) # 空格前面都打印成空格，sep有个空格，遍历到的空格后面的字符全部打印（基于tail切片，并补充空格）
triangle_print(12)
基于此想法可以得到上三角的新解法：
def triangle_print(n):
tail = " ".join(str(i) for i in range(n, 0, -1))
width = len(tail)
for i in range(-1, -width-1, -1): # 负索引
if tail[i] == " ": # 遍历最后一行的空格
print(" " * (width + i), tail[(i + 1):]) # 空格前面都打印成空格，sep有个空格，遍历到的空格后面的字符全部打印（基于tail切片，并补充空格）
print(tail)
triangle_print(15)
扁平化字典
例如，源字典：{'a': {'b': 1, 'c': 2}, {'d': {'e': 3, 'f': {'g': 4}}}}，目标字典：{'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
递归：
层级结构，需要一直往下操作，可用递归
source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}}
target = {}
def flatmap(src: dict, prefix=''):
for k,v in src.items():
if isinstance(v, dict):
flatmap(v, prefix=prefix+k+'.')
else:
target[prefix+k] = v
return target
flatmap(source)
print(target)
一般这种函数都会生成一个新的字典，因此改造一下，dest字典可以又内部构建，也可以由外部提供。
source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}}
def flatmap(src: dict, dest=None, prefix=''):
if dest == None:
dest = {}
for k,v in src.items():
if isinstance(v, dict):
flatmap(v, dest, prefix=prefix+k+'.')
else:
dest[prefix+k] = v
return dest
print(flatmap(source))
上面这种函数还是不太好，因为他把dest这个内部字典暴露了出来，用户使用这个dest形参是没有意义的，我们更希望用户调用函数的时候，只提供一个源字典实参就够了，也就是说定义函数的时候，函数只有src一个形参。
def flatmap(src: dict):
dest = {}
prefix = ''
for k,v in src.items():
if isinstance(v, dict):
flatmap(v, dest, prefix=prefix+k+'.')
else:
dest[prefix+k] = v
return dest
print(flatmap(source))
前三行是我们想要的，即额外的参数只存在于内部，用户无需理会这些参数只需提供源字典就能获得处理。
但是函数能运行成功吗？不能！因为下面使用了递归调用，每次在递归调用的时候，2、3行的dest，prefix都会被重置，而不是保持状态往下传递。那怎么办呢？
这时可以使用函数嵌套的形式，内层函数自己递归自己，不会影响到到外层函数的变量，再把dest，prefix传入内层函数。
source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}}
def flatmap(src: dict):
dest = {}
def _flatmap(src, prefix=''):
for k, v in src.items():
if isinstance(v, dict):
_flatmap(v, prefix=prefix + k + '.')
else:
dest[prefix + k] = v
_flatmap(src)
return dest
print(flatmap(source))
dest这个参数不用在递归中传递，当作做外层变量，每次修改是变量引用的字典里面的键值而已，所以不会报错。
prefix必须在内层传递，因为 prefix=prefix + k + '.'，这句话的右半边会默认prefix是内部变量，如果prefix只是外部变量绝对报错。所以prefix要被传递进来，且要往下传递，接受修改，而不是像dest那样。
综上，最终的flatmap()函数，用户只需要直到flatmap(src)的用法就行，只提供src源字典就可以得到想要的结果。
