1最大二叉树 —————————— def func(nums,result):

if nums != [] and len(nums) > 1:
    t = max(nums)
    i = nums.index(t)
    result.append(t)
    Lnums = nums[:i]
    Rnums = nums[i+1:]

    func(Lnums,result)
    func(Rnums,result)
elif nums != [] and len(nums) == 1:
    result.append(nums[0])
else:
    result.append('null')

return result

nums = list(map(int, input().split())) result = [] func(nums,result) print(" ".join(map(str,result)))

2寻找多数 ———————————— def findmajor(n,arr):

major = None
count = 0
for i in arr:
    if count == 0:
        major = i
        count += 1
    else:
        if i == major:
            count += 1
        else:
            count -= 1
return major

n = int(input()) nums = list(map(int,input().split()))

print(findmajor(n,nums))

3找到最大子序和 ———————————— def func(nums,n):

cur_sum = 0
max_sum = -1000
for i in range(n):
    if nums[i] + cur_sum > nums[i]:
        cur_sum = nums[i] + cur_sum
        max_sum = max(max_sum,cur_sum)
    else:
        cur_sum = nums[i]
        max_sum = max(max_sum, cur_sum)

return max_sum

n = int(input()) nums = list(map(int, input().split())) print(func(nums,n))

6换硬币 ———————————— def func(N):

dp = []
if N>7:
    for _ in range(N+1):
        dp.append(999)
else:
    for _ in range(8):
        dp.append(999)

dp[0] = 0
dp[1] = -1
dp[2] = 1
dp[3] = -1
dp[4] = 2
dp[5] = 1
dp[6] = 3
dp[7] = 1

for i in range(8,N+1):
    if dp[i] > dp[i - 2] != -1:
        dp[i] = dp[i-2]+1
    if dp[i] > dp[i - 5] != -1:
        dp[i] = dp[i-5]+1
    if dp[i] > dp[i - 7] != -1:
        dp[i] = dp[i-7]+1
    if dp[i-2] == dp[i-5] == dp[i-7] == -1:
        dp[i] == -1

return dp[N]

print(func(int(input())))

7走网格 ———————————— def func(m,n):

dp = []
for _ in range(m):
    row = [0] * n
    dp.append(row)

for _ in range(m):
    dp[_][0] = 1
for _ in range(n):
    dp[0][_] = 1

for i in range(1,m):
    for j in range(1,n):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

return dp[m-1][n-1]

m,n = map(int,input().split()) print(func(m,n))

8爬楼梯 ———————————— def func(n):

dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    dp[i] = dp[i-2] + dp[i-1]

return dp[n]

print(func(int(input())))

9背包问题 —————————————— def func(N,c,Wnums,Vnums): #c背包承重 N物品数量 Wnums物品重量列表 Vnums物品价值列表

things = N
contain = c
dp = []
for _ in range(things+1):
    row = [0] * (contain+1)
    dp.append(row)   #当容量为0时，所容纳的最大价值也为0

for i in range(1,things+1): #物品编号从1开始，前0个物品表示没有物品，即dp数组第一行和第一列都为0
    for j in range(1,contain+1):
            if j < Wnums[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-Wnums[i-1]]+Vnums[i-1])

return dp[-1][-1]

N,c = map(int,input().split()) Wnums = list(map(int,input().split())) Vnums = list(map(int,input().split())) print(func(N,c,Wnums,Vnums))

10最长回文子串 ———————————— def func(Str):

n = len(Str)    #创建dp空数组（原因是递归过程中不用重复计算）
dp = []
for _ in range(n):
    dp.append([False] * n)

max_length = 1
max_Str = Str[0]
for i in range(n):  #dp二维数组里长度为1的子串都是回文串;i表示起始点加上len就是终止点
    dp[i][i] = True

for i in range(0,n-1):  #特殊情况2
    if Str[i] == Str[i+1]:
        dp[i][i+1] = True
        max_length = 2
        max_Str = Str[i:i+max_length]

for length in range(3,n+1):
    for i in range(0,n-length+1):
        if Str[i] == Str[i+length-1] and dp[i+1][i+length-2]:
            dp[i][i+length-1] = True
            max_length = length
            max_Str = Str[i:i+length]

return max_Str

Str = input() print(func(Str))

14目标和 —————————————— def check(sum, citation, nums, target, sigh):

n = len(nums)
if sigh == 1:
    sum += nums[citation]
elif sigh == -1:
    sum -= nums[citation]

if citation == n - 1:  # 如果到了最后一个数字，就开始检查sum是否等于目标数字
    if sum == target:
        return 1  # 如果符合目标返回1，否则返回0
    return 0
else:
    # 递归尝试 + 和 - 的两种情况
    return check(sum, citation + 1, nums, target, 1) + check(sum, citation + 1, nums, target, -1)

nums = list(map(int, input().split())) target = int(input())

从第一个数字开始，可以选择 + 或 -，所以调用两次递归分别尝试

result = check(0, 0, nums, target, 1) + check(0, 0, nums, target, -1) print(result)

15电话号码的字母组合 ——————————————— def func(digits):

letter_list = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]  # 下标对应数字,0和1对应None
answer_list = []  # 解集

n = len(digits)
def backtrack(index,cur):
    if len(cur) == n:  # 满了就把当前结果算上
        answer_list.append(cur)
    if index < n:
        for i in letter_list[int(digits[index])]:
            backtrack(index+1,cur+i)#这里是重点！把cur更新在下一个递归函数里，而不要修改本层函数的cur

backtrack(0,"")

return answer_list

digits = input() answer_list = func(digits) print("["+", ".join(answer_list)+"]")

16优美的排列 —————————————— def find_permitted_nums(n): # 找到每个位置可以放的数字

result = [[] for _ in range(n + 1)]  # 使用列表存储整数
for i in range(1, n + 1):  # 遍历位置
    for j in range(1, n + 1):  # 遍历数字
        if j % i == 0 or i % j == 0:
            result[i].append(j)  # 添加整数
return result

def func(n):

result = find_permitted_nums(n)

answer = []

def recursive_func(index, cur):
    if len(cur) == n:  # 找到一个符合条件的排列
        answer.append(cur)
        return
    if index < n:
        for num in result[index + 1]:  # 获取每一位置可以使用的数字
            if num not in cur:  # 确保没有重复数字
                recursive_func(index + 1, cur + [num])  # 添加数字并递归

recursive_func(0, [])  # 从索引0开始递归

return len(answer)

print(func(int(input()))) # 输入n并输出符合条件的排列数量

17组合 —————————————— def func(n,k):

result = []

def backtrack(i,cur):
    if len(cur) == k:
        result.append(cur[:])#cur是列表，每个答案都是一个列表
        return

    for j in range(i,n+1):
        cur.append(j)
        backtrack(j+1,cur)
        cur.pop()#把当前函数的j pop出去，进入以下一个数字为开头的递归循环

backtrack(1,[])

return result

n,k = map(int,input().split()) for i in func(n,k):

print(" ".join(map(str, i)))

21整数拆分 —————————————— def func(n):

if n > 9:
    dp = [1] * (n+1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 1
    dp[3] = 2
    dp[4] = 4
    dp[5] = 6
    dp[6] = 9
    dp[7] = 12
    dp[8] = 18
    dp[9] = 27
else:
    dp = [1] * 10
    dp[0] = 0
    dp[1] = 1
    dp[2] = 1
    dp[3] = 2
    dp[4] = 4
    dp[5] = 6
    dp[6] = 9
    dp[7] = 12
    dp[8] = 18
    dp[9] = 27

for i in range(10,n+1):
    if not i%2 :
        dp[i] = max((dp[i//2])**2,dp[i//2-1]*dp[i//2+1])
    else:
        dp[i] = max(dp[i//2]*dp[i//2+1],dp[i//2-1]*dp[i//2+2])

return dp[n]

print(func(int(input())))

25找假币 —————————————— def func(n,nums):

standard = nums[0]
for i in range(n):
    if nums[i] < standard:
        return i+1
    standard = nums[i]
else:
    return 1

n = int(input()) nums = list(map(int,input().split())) print(func(n,nums))

29分割等和子集 —————————————— def func(nums,k):

n = len(nums)
result = []

def backtrack(i,cur):
    if len(cur) == k:
        result.append(cur[:])
        return

    for j in range(i,n):
        cur.append(nums[j])
        backtrack(j+1,cur)
        cur.pop()

backtrack(0,[])

return result

def func29(nums):

n = len(nums)

32三角形的最大周长 —————————————— def func(nums):

n = len(nums)
nums.sort(reverse = True)
i = 0
while not cycle_check_tri(nums[i:i+3]):
    i += 1
    if len(nums[i:i+3]) < 3:
        break
else:
    C = 0
    for j in nums[i:i+3]:
        C += j
    return C

return 0

def cycle_check_tri(edges):

if edges[2] + edges[1] > edges[0]:
    return True
else:
    return False

nums = list(map(int,input().split())) print(func(nums))