datetime:2024/1/29 16:50
author:nzb
暴力递归
- 暴力递归就是尝试
- 1，把问题转化为规模缩小了的同类问题的子问题
- 2，有明确的不需要继续进行递归的条件(base case)
- 3，有当得到了子问题的结果之后的决策过程
- 4，不记录每一个子问题的解
一定要学会怎么去尝试，因为这是动态规划的基础，这一内容我们将在提升班讲述
汉诺塔问题
打印n层汉诺塔从最左边移动到最右边的全部过程(大的不能在小的上面)
2
1 | 3
| | |
--- | |
| | |
----- | |
| | |
------- | |
- 假设
1~i的圆盘，要从from杆->to杆，还有一个other的杆- 假设函数
fn(i, from, to, other)分以下步骤1~i-1从from->other：调用fn(i-1, from, other, to)i从from->to：因为1~i-1都移到other，所以可以把i移到to了，直接打印1~i-1从other->to：移回去，调用fn(i-1, other, to, from)
- 假设函数
def hanoi(n: int):
if n > 0:
move_tower_of_hanoi(n, "左", "右", "中")
def move_tower_of_hanoi(i: int, start: str, end: str, other: str):
if i == 1: # base case, 就是那个杆就剩一个的时候，直接移到 end 上
print(f"Move 1 from {start} to {end}")
else:
move_tower_of_hanoi(i - 1, start, other, end)
# i-1 都移到 other 了，i 移到 end, 打印
print(f"Move {i} from {start} to {end}")
move_tower_of_hanoi(i - 1, other, end, start)
hanoi(3)
打印一个字符串的全部子序列，包括空字符串
def print_subsets(word: str, i=0, current_subset=""):
if i == len(word): # base case 到最后一个字符下一个索引，到底了
print("Subset:", current_subset)
return
# 包含当前字符的情况
print_subsets(word, i + 1, current_subset + word[i])
# 不包含当前字符的情况
print_subsets(word, i + 1, current_subset)
# 示例
print_subsets('abc')
打印一个字符串的全部排列
def print_permutations(word: str, current: str = ""):
if not word: # base case 不剩字符了，打印
print(current)
return
for i in range(len(word)):
remaining_chars = word[:i] + word[i + 1:] # 去掉当前字符，还剩哪些字符
print_permutations(remaining_chars, current + word[i])
# 示例
print_permutations('abc')
打印一个字符串的全部排列，要求不要出现重复的排列
def print_unique_permutations(s, current=""):
if not s:
print(current)
return
for i in range(len(s)):
if i > 0 and s[i] == s[i - 1]:
continue
remaining_chars = s[:i] + s[i + 1:]
print_unique_permutations(remaining_chars, current + s[i])
# 示例
input_string = "aab"
sorted_input = ''.join(sorted(input_string)) # 对输入字符串排序
print_unique_permutations(sorted_input)
拿牌问题
给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
- 【举例】
arr=[1,2,100,4] - 开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为
[2,100,4]，接下来玩家 B可以拿走2或4，然后继续轮到玩家A... 如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A... 玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。 arr=[1,100,2]开始时，玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。
- 【举例】
解题思路：
- 先手函数：先手拿在
L到R上返回最大分数，first(arr, L, R)base case：L==R,return arr[L]- 拿左：
arr[L] + second(arr, L+1, R) - 拿右：
arr[R] + second(arr, L, R-1) - 作为聪明人：
max(拿左分数，拿右分数)
- 后手函数：
sec(arr,L, R)base case：L==R,return 0，只有一个数了，但是被别人拿走了，就没了，返回0- 别人拿走了
L，first(arr, L+1, R) - 别人拿走了
R，first(arr, L, R-1) - 但是这是对方决定的，别人会给最差的情况，所以
min(拿左分数，拿右分数)
- 先手函数：先手拿在
def win(arr):
if not arr:
return 0
return max(first(arr, 0, len(arr) - 1), second(arr, 0, len(arr) - 1))
def first(arr, left, right):
if left == right:
return arr[left]
return max(arr[left] + second(arr, left + 1, right), arr[right] + second(arr, left, right - 1))
def second(arr, left, right):
if left == right:
return 0
return min(first(arr, left + 1, right), first(arr, left, right - 1))
print(win([1, 2, 100, 4]))
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现?
def reverse_stack(stack):
"""
逆序栈
bottom = get_stack_bottom() = 3, reverse_stack
bottom = get_stack_bottom() = 2, reverse_stack
bottom = get_stack_bottom() = 1, reverse_stack
stack为空, return
bottom = 1 压回去
bottom = 2 压回去
bottom = 3 压回去
:param stack:
:return:
"""
if not stack:
return
bottom = get_stack_bottom(stack)
reverse_stack(stack)
stack.append(bottom)
def get_stack_bottom(stack):
"""
获取栈底元素
[3, 2, 1]
fn(1) result=1, last = fn(2)
fn(2) result=2, last = fn(3)
fn(3) result=3, 栈为空，返回
回到 fn(2) 的 last=fn(3)=3, 把result=2, 压回栈，返回 last = 3
回到fn(1) 的 last=fn(2)=3, 把result=1, 压回栈，返回 last = 3
最后结果 3
:param stack:
:return:
"""
result = stack.pop()
if not stack:
return result
last = get_stack_bottom(stack)
stack.append(result)
return last
data = [3, 2, 1]
reverse_stack(data)
print(data)
数字字符串转换
规定1和A对应、2和B对应、3和C对应... 那么一个数字字符串比如"111"，就可以转化为"AAA"、"KA"和"AK"。给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
0~i-1位置是确定下来，在i往后有多少种i==0：如果是0那接下来有0种，比如0111，0字符没有对应的字母，所以往后都没对应的01、011、0111字母字符1<= i <= 93 <= i <= 9：单独i位置做转换，一定没法做的转换是i和i+1一起做转换i == 1：- 单独
i位置做转换 i和i+1一起做转换，i+2之后做转换
- 单独
i == 2- 单独
i位置做转换 i+i+1< 26：i和i+1一起做转换，i+2之后做转换
- 单独
def transform(word, i=0):
if i == len(word): # base case 走到底了
return 1
if word[i] == "0":
return 0
elif word[i] == "1":
cnt = transform(word, i + 1) # 单独 i 作转换，后续还有多少种
if i + 1 < len(word):
cnt += transform(word, i + 2) # i 和 i+1 一起做转换，后续还有多少种
return cnt
elif word[i] == "2":
cnt = transform(word, i + 1) # 单独 i 做转换，后续还有多少种
if i + 1 < len(word) and '0' <= word[i + 1] <= "6": # i + i + 1 小于等于 26，一起转换，后续还有多少种
cnt += transform(word, i + 2)
return cnt
return transform(word, i + 1)
print(transform("0123")) # 0
print(transform("1201")) # 1
print(transform("110111")) # 3
背包价值问题
给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。 返回你能装下最多的价值是多少？
def bag_value(weights, values, bag, i=0, already_weight=0):
if already_weight > bag: # 超重，因为加上了i位置货物导致超重，所以需要减去i上一个的i-1位置的货物价值
return -values[i - 1]
if i == len(weights): # 没货了，比如weight为空
return 0
i_no_need = bag_value(weights, values, bag, i + 1, already_weight) # i货不要
# i货要，这里加了价值，但是加了以后，超重了，所以上面需要减掉
i_need = values[i] + bag_value(weights, values, bag, i + 1, already_weight + weights[i])
return max(i_need, i_no_need)
weights_data = [1, 2, 3]
values_data = [1, 2, 3]
print(bag_value(weights_data, values_data, 3))