2、 recursive / fibonacci
2.1 蛙跳
mem = {}
def fun(n):
global mem
if n in mem:
return mem[n]
else:
if n==1:
mem[n] = 1
return 1
elif n==2:
mem[n] = 2
return 2
else:
t = fun(n-1)+fun(n-2)
mem[n] = t
return t
class Solution:
def jumpFloor(self, number):
if number==1:
return 1
elif number==2:
return 2
elif number>2:
f1 = 1
f2 = 2
for i in range(3,number+1):
f3 = f1+f2
f1 = f2
f2 = f3
return f3
2.2 猴子登山
mem = {}
def f(n):
if n in mem:
return mem[n]
else:
if n==1:
mem[1] = 1
return 1
elif n==2:
mem[2] = 1
return 1
elif n==3:
mem[3] = 2
return 2
else:
t = f(n-1)+f(n-3)
mem[n] = t
return t
print(f(m))
#---------------------------------
f1 = 1
f2 = 1
f3 = 2
for i in range(3,m):
f4 = f1+f3
f1 = f2
f2 = f3
f3 = f4
print(f4)
2.3 汉诺塔
把n个盘子从Left 借助 Mid，移动到Right柱子上，可以分为以下三步：
1、把n-1个盘子从Left 借助 Right，移动到Mid柱子上
2、把剩下最大的那一个盘子从Left移动到 Right柱子上
3、把n-1个盘子从Mid 借助 Left，移动到,Right柱子上
out = []
def hanoi(n, left, mid, right):
if n==0:
return
if n==1:
t = 'move from ' + left + ' to ' + right
out.append(t)
return
hanoi(n-1, left, right, mid)
hanoi(1, left, mid, right)
hanoi(n-1, mid, left, right)
2.4 放苹果
f(m,n)表示将m个苹果放入n个盘子中的摆放方法总数，
放苹果分为两种情况，一种是有1个盘子为空 f(m,n-1)，另一种是每个盘子上至少有1个苹果f(m-n,n)，
递推关系：f(m,n) = f(m,n-1) + f(m-n,n)
边界条件：当m==1 or n==1时，f(m,n) =1
def f(m,n):
if m<0 or n<0:
return 0
elif m==1 or n==1:
return 1
else:
return f(m,n-1) + f(m-n,n)
while 1:
try:
m,n = map(int,input().strip().split())
print(f(m,n))
except:
break
3、 dfs / bfs / back
3.1 组合
def dfs(iStart,res):
s = sum(res) # 路径和
if s>target:
return
if s==target:
if res not in out: # 这里也可以去重
out.append(res) # 保存路径
return # 返回空回溯
for i in range(iStart,n):
dfs(i+1,res+[num[i]]) # i+1,增加路径
dfs(iStart,res)
3.2 排列
def dfs(num,res):
if not num:
if res not in out:
out.append(res)
for i in range(len(num)):
dfs(num[:i]+num[i+1:],res+[num[i]])
dfs(num,res)
3.3 数独
def dfs(k, res):
if k==n: # 如达到最后一个节点
#print(res)
return res # 返回第一个合法解，如无返回可打印所有合法解
if 0<=k<=n-1: # 限定搜索范围保证访问不越界
i = I[k] # 取行值
j = J[k] # 取列值
for v in value: # 遍历当前节点每个候选解
if check(S,i,j,v): # 检查当前节点当前候选解合法性
S[i][j] = v # 如合法赋值
solve_opt = dfs(k+1, res+[v]) # 递归进入下一个节点，第二个参数加入当前节点合法解。dfs()的返回值solve只有两种情况，
if solve_opt: # 1、为空，说明下一个节点几个候选解check()都返回false，即本节点当前候选解不对，
return solve_opt # 本节点要回溯执行下一个候选解，因此要恢复S[i][j]=0，对一下个候选解执行check()
S[i][j] = 0 # 2、不为空时，说明到达终点k==n，solve返回所有路径点res
solve_opt = dfs(0, res)
3.4 迷宫
xy0 = [0,0]
xy1 = [r-1,c-1]
MOV = [[1,0],[0,1],[-1,0],[0,-1]] # 四个方向移动一格
#---------------------------------------------------------------------------------
# 递归调用dfs(xy_new, res+[xy_new])时， res+[xy_new]实际保存了不断增长的路径
res = [xy0]
def dfs(xy0, res): # xy0为当前搜索点，res保存了当前点历史路径
maze[xy0[0]][xy0[1]] = 9
if xy0[0] == xy1[0] and xy0[1] == xy1[1]:
shortest_path = res
return shortest_path # 到达终点时读取res返回最路径
for mov in MOV: # 四个方向移动
xy_new = [xy0[0]+mov[0], xy0[1]+mov[1]] # 移动后的新坐标
if 0<=xy_new[0]<=r-1 and 0<=xy_new[1]<=c-1 and maze[xy_new[0]][xy_new[1]] == 0: # 坐标有效且没有被访问过
shortest_path = dfs(xy_new, res+[xy_new]) # 调用下一个节点，第二个参数传递路径
if shortest_path: # 只有dfs返回不为空时，才能返回，空时不能返回，程序会提前结束
return shortest_path
#=============================================================================================================================
xy0 = [0,0,-1]
xy1 = [r-1,c-1,-1]
MOV = [[1,0],[0,1],[-1,0],[0,-1]] # 四个方向移动一格
#---------------------------------------------------------------------------------
# Path中的每一行存有路径坐标点，第三个值保存上一个节点的list索引，从0开始
def road(visited):
shortest_path = []
shortest_path.append(visited[-1][:-1])
t = visited[-1][-1]
while t!=-1:
shortest_path.append(visited[t][:-1])
t = visited[t][-1]
return shortest_path[::-1]
#---------------------------------------------------------------------------------
# BFS（宽度优先搜索）解迷宫问题
def bfs(xy0):
queue = [xy0] # 开始点进入队列
visited = [] # 记录所有访问过的点，以及每一个点前一个节点索引
k = 0
while queue: # 队列不为空即运行
xy = queue.pop() # 队列中取出一个新坐标点
maze[xy[0]][xy[1]] = 9 # 开始点标记为已访问值9
visited.insert(k, xy) # 相当于path.append(xy),这样写更清楚
if xy[0] == xy1[0] and xy[1] == xy1[1]:
shortest_path = road(visited) # 到达终点时，反向寻找来时路径
return shortest_path
for mov in MOV: # 四个方向移动
xy_new = [xy[0]+mov[0], xy[1]+mov[1]] # 移动后的新坐标
if 0<=xy_new[0]<=r-1 and 0<=xy_new[1]<=c-1 and maze[xy_new[0]][xy_new[1]] == 0: # 坐标有效且没有被访问过
xy_new = [xy_new[0],xy_new[1],k] # 将前一个点的索引加入坐标之后（用于反向寻找路径）
queue.insert(0, xy_new) # 新坐标不为终点，新坐标入队列,
k += 1
3.5 单源最短路
1、对于节点距离，建立一个字典dict_t，以字符形式存储key，距离以数字形式保存在value中，重边取最小
2、定义一个函数dis(i,j)：第i节点到第j个节点的距离，访问距离字典，有值返回，无通路返回None
3、dfs搜索，第二个参数传递走过的距离，到达终点时取最小输出，nonlocal关键字的使用
class Solution:
def findShortestPath(self , n , m , graph ):
# write code here
dict_t = {}
for ijdis in graph:
key = str(ijdis[0])+'-'+str(ijdis[1])
if key not in dict_t:
dict_t[key] = ijdis[2]
else:
dict_t[key] = min(ijdis[2],dict_t[key])
#print(dic)
def dis(i,j):
key = str(i)+'-'+str(j)
if key not in dict_t:
return None
else:
return dict_t[key]
#print(dis(1,2))
#print(dis(2,3))
#print(dis(3,4))
res = 0
minpath = float('inf')
def dfs(i,res):
nonlocal minpath
if i==n:
if res<minpath:
minpath = res
for j in range(1,n+1):
if dis(i,j):
dfs(j,res+dis(i,j))
dfs(1,res)
print(minpath)
return minpath
4、 stack / queue
4.1 火车进站
目隐藏条件是N趟火车的进站始终按照原本的火车列表顺序，就是假如有两列火车A，B，B不可能在A之前进站
关键的几个变量说明：
1、cur_idx，当前需要进站处理的火车
2、in_trains、已经进站的火车列表
3、out_trains、已经出站的火车列表
4、res、火车所有可能的出站列表
#--------------------------------------------------------------------
# 两点注意：
# 1、train, station, out在计算过程中不要有赋值操作
# 2、压栈操作[1,2,3]+[4] = [1,2,3,4]，这里4如果是单独一个数要加[]
def fun(train, station, out):
#print('train=',train)
#print('station=',station)
#print('out=',out)
if train and station == []: # 车站为空，仅火车进站
#print('1')
t = train[-1]
fun(train[:-1], station + [t], out)
elif train == [] and station: # 火车为空，车站火车出站
#print('2')
rec.append(out + station[::-1])
return
else: # 车站和火车都不为空，有两种选择
#print('3')
t = train[-1]
fun(train[:-1], station + [t], out) # 火车进站
t = station[-1]
fun(train, station[:-1], out + [t]) # 车站火车出站
4.2 表达式求值
解题思路：
1、中缀表达式转为后缀表达式
2、为后缀表达式计算规则：从左到右遍历表达式的每个数字和符号，遇到的是数字就进栈，
遇到的时符号就将栈顶的两个数字出栈进行计算，然后将计算结果入栈，最终栈里的值即为计算的结果。
3、预处理：将字符串按实际物理意义，转成字符列表（含多位数和负数、空格、[]、{}）
'''
#----------------------------------------
# 输出num1 + operator + num2结果
def getvalue(num1,num2,operator):
if operator == '+':
return num1 + num2
elif operator == '-':
return num1 - num2
elif operator == '*':
return num1 * num2
elif operator == '/':
return num1 / num2
else:
return []
#----------------------------------------
# 优先级 operator1 >= operator2,输出真
def compare(operator1,operator2):
if operator1 in '*/' and operator1 in '*/':
return True
elif operator1 in '+-' and operator1 in '+-':
return True
elif operator1 in '*/' and operator1 in '+-':
return True
elif operator1 in '+-' and operator1 in '*/':
return False
else:
return []
#----------------------------------------
# 中缀表达式转为后缀表达式
# 输入L = ['0','-','1','*','(','0','-','1','-','1',')','-','3','*','(','1','-','2',')','-','3','*','4']
# 输出express= ['0',1','0','1','-','1','-','*','-','3','1','2','-','*','-','3','4','*','-']
def suffix_express(L):
express = [] # 后缀表达式
stack = [] # 存中间符号的栈
for i in L:
if i.isnumeric(): # 数字直接入表达式
express.append(i)
elif i in '+-': # 遇到+—号，如果符号栈空，入符号栈
if len(stack) == 0:
stack.append(i)
else: # 如果符号栈不为空，符号栈优先级大于等于当前符号的，弹出入表达式
while stack and compare(stack[-1],i):
express.append(stack.pop())
stack.append(i) # 当前符号入符号栈
elif i in '*/(': # */(直接入符号栈
stack.append(i)
elif i in ')': # 遇到),(之前的符号弹出入表达式
while stack and stack[-1] != '(':
express.append(stack.pop())
if stack: # 删除(
stack.pop()
while stack: # 最后栈中所有符号弹出入表达式
express.append(stack.pop())
return express
#----------------------------------------
# 为后缀表达式计算规则：
# 从左到右遍历表达式的每个数字和符号，遇到的是数字就进栈，遇到的时符号就将栈顶的两个数字出栈进行计算，
# 然后将计算结果入栈，最终栈里的值即为计算的结果。
# 输入express= ['0',1','0','1','-','1','-','*','-','3','1','2','-','*','-','3','4','*','-']
# 输出计算结果 = result
def compute(suffix_express):
stack = []
for i in suffix_express:
if i.isnumeric():
stack.append(i)
elif i in '+-*/':
n2 = stack.pop()
n1 = stack.pop()
stack.append(getvalue(int(n1),int(n2),i))
if stack:
return stack.pop()
return []
#----------------------------------------
# 预处理：将字符串按实际物理意义，转成字符列表（含多位数和负数、空格、[]、{}）
# 输入：-1*(-1-1)-3*(1-2)-3*4
# 输出：['0','-','1','*','(','0','-','1','-','1',')','-','3','*','(','1','-','2',')','-','3','*','4']
def preprocess(L):
B = ''
for i in L:
if i in '0123456789+-*/()[]{}': # 去空格
B += i
B = B.replace('[','(') # 统一括号
B = B.replace(']',')')
B = B.replace('{','(')
B = B.replace('}',')')
L = '('+ B +')' # 左右加括号用于判断负号
A = []
tmp = ''
for i in range(1,len(L)-1):
if L[i] == '-' and L[i-1]=='(': # 负号前必有括号,前加0将负号变减号
A.append('0')
A.append('-')
elif L[i].isnumeric() and L[i+1].isnumeric():
tmp += L[i]
elif L[i].isnumeric() and not L[i+1].isnumeric():
tmp += L[i]
A.append(tmp)
tmp = ''
else:
A.append(L[i])
return A
#String = input()
String = '-1*(-1-1)-3*(1-2)-3*4'
#print(String)
List = preprocess(String)
#print(List)
express = suffix_express(List)
#print(express)
result = compute(express)
print(String+' = '+str(result))
4.3 矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b?tab=note
# 多个矩阵连乘的总计算量，输入为多个矩阵的size组成的list二维数组
def times(size):
n = len(size)
tmp = 0
for t in range(n-1):
tmp += size[0][0] * size[t][1] * size[t+1][1]
return tmp
while 1:
try:
n = int(input())
size = []
for i in range(n):
size.append(list(map(int,input().strip().split())))
L = input()
L= '(' + L + ')' # 左右加()
stack = []
tmp = []
result = 0
k = 0
for i in range(1,len(L)-1): # 不考虑左右加的()
if L[i] == '(': # 遇到(,(压栈
stack.append('(')
elif L[i].isalpha(): # 遇到矩阵,size压栈
stack.append(size[k])
k += 1
elif L[i] == ')': # 遇到),之前所有矩阵size出栈，并反序
while stack and stack[-1] != '(':
tmp.append(stack.pop())
if stack:
stack.pop()
tmp = tmp[::-1]
stack.append([tmp[0][0],tmp[-1][-1]]) # 新矩阵size压栈
result += times(tmp) # 计算乘法计算量并累加
tmp = []
print(result)
except:
break
4.4 最长无重复子数组
方法一：用一个队列，把元素不停的加入到队列中，如果队列中有相同的元素，就把队首的相同元素及之前的元素都移除
方法二：使用两个指针，一个i一个j，最开始的时候i和j指向第一个元素，然后i往后移，把扫描过的元素都放到map中，如果i扫描过的元素没有重复的就一直往后移，顺便记录一下最大值max，如果i扫描过的元素有重复的，就改变j的位置
class Solution:
def maxLength(self , arr ):
queue = []
maxLen = 0
for i in arr:
if i not in queue:
queue.insert(0,i)
else:
while queue[-1] != i:
queue.pop()
queue.pop()
queue.insert(0,i)
if len(queue)>maxLen:
maxLen = len(queue)
return maxLen
京公网安备 11010502036488号