递归、二维数组顺时针旋转90°、正则表达式
1、 递归算法是一种直接或间接调用自身算法的过程。
特点:
- 递归就是在过程或函数里调用自身
- 明确的递归结束条件,即递归出口
- 简洁,但是不提倡
- 递归次数多容易造成栈溢出
要求:
- 每次调用递归规模上有所减小
- 前一次为后一次做准备
- 规模较小时必须直接给出解答而不再进行递归调用
例子:递归实现二分法
def searchMyData(mydate,a1):
mid = int(len(mydate)/2)
if mid >= 1:
if mydate[mid]>a1:
print("目标数据在%s左侧"% mydate[mid])
searchMyData(mydate[:mid],a1)
elif mydate[mid]<a1:
print("目标数据在%s右侧"%mydate[mid])
searchMyData(mydate[mid:],a1)
else:
print("We get it!")
else:
print("We can't find it!")
if __name__ == '__main__':
data = list(range(1,600,3))
print(data)
searchMyData(data,397)
结果:
[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154, 157, 160, 163, 166, 169, 172, 175, 178, 181, 184, 187, 190, 193, 196, 199, 202, 205, 208, 211, 214, 217, 220, 223, 226, 229, 232, 235, 238, 241, 244, 247, 250, 253, 256, 259, 262, 265, 268, 271, 274, 277, 280, 283, 286, 289, 292, 295, 298, 301, 304, 307, 310, 313, 316, 319, 322, 325, 328, 331, 334, 337, 340, 343, 346, 349, 352, 355, 358, 361, 364, 367, 370, 373, 376, 379, 382, 385, 388, 391, 394, 397, 400, 403, 406, 409, 412, 415, 418, 421, 424, 427, 430, 433, 436, 439, 442, 445, 448, 451, 454, 457, 460, 463, 466, 469, 472, 475, 478, 481, 484, 487, 490, 493, 496, 499, 502, 505, 508, 511, 514, 517, 520, 523, 526, 529, 532, 535, 538, 541, 544, 547, 550, 553, 556, 559, 562, 565, 568, 571, 574, 577, 580, 583, 586, 589, 592, 595, 598]
目标数据在301右侧
目标数据在451左侧
目标数据在376右侧
目标数据在412左侧
目标数据在394右侧
目标数据在403左侧
We get it!
2、 二维数组90°顺时针旋转
a = [[col for col in range(4)] for row in range(4)]
for i in a:
print(i)
print('-'*20)
for row_2 in range(4):
for col_2 in range(row_2,4):
tmp = a[row_2][col_2]
a[row_2][col_2] = a[col_2][row_2]
a[col_2][row_2] = tmp for i in a:
print(i)
结果:
[0, 1, 2, 3]
[0, 1, 2, 3]
[0, 1, 2, 3]
[0, 1, 2, 3]
--------------------
[0, 0, 0, 0]
[1, 1, 1, 1]
[2, 2, 2, 2]
[3, 3, 3, 3]
注:a[r][c] 表示二维列表的第2行第c列的元素,和数组表示方法类似
3、 正则表达式
import re
ret = re.match("abc","abcdef")
print(ret)
print(ret.group())
ret = re.match("[0-9]","abc6fak")# 必须是字符串
#match 是从开头匹配,如果开头不是数字,那么不可匹配
ret = re.match("[0-9]{0,10}","abc6fak")# 匹配0~10次
ret = re.match("[0-9]{10}","abc6fak")# 匹配10次
if ret:
print(ret.group())
ret = re.findall("[0-9]{1,10}","213abc6fak")# 匹配所有数字
ret = re.findall("[0-9]{1,10}","213abc6fak")# 匹配所有字符
ret = re.findall(".*","1234aggh") # 匹配所有,最后有''
ret = re.findall(".","1234aggh") # 匹配单个字符
ret = re.findall(".+","1234aggh") # 匹配所有
ret = re.sub("\d+","|","1234aggh",count=2) # 替换前两个
if ret:
print(ret)