1Problem P01. [算法课分治] 最大二叉树

class TreeNode:

def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

def construct_maximum_binary_tree(nums):

if not nums:
    return None
max_val = max(nums)
max_idx = nums.index(max_val)
root = TreeNode(max_val)
root.left = construct_maximum_binary_tree(nums[:max_idx])
root.right = construct_maximum_binary_tree(nums[max_idx + 1:])
return root

def preorder_traversal(root):

if root is None:
    return []

# 如果是叶子节点，只返回自身，不输出 null
if root.left is None and root.right is None:
    return [str(root.val)]

result = [str(root.val)]

# 处理左孩子
if root.left:
    result.extend(preorder_traversal(root.left))
else:
    result.append("null")

# 处理右孩子
if root.right:
    result.extend(preorder_traversal(root.right))
else:
    result.append("null")

return result

import sys

for line in sys.stdin:

line = line.strip()
if not line:
    continue
nums = list(map(int, line.split()))
tree = construct_maximum_binary_tree(nums)
result = preorder_traversal(tree)
print(" ".join(result))

2Problem P02. [算法课分治] 寻找多数 def find_majority_element(nums):

def divide_and_conquer(left, right):
    # 基础情况：只有一个元素
    if left == right:
        return nums[left]
    
    # 分解：找中点，分成左右两半
    mid = (left + right) // 2
    left_majority = divide_and_conquer(left, mid)
    right_majority = divide_and_conquer(mid + 1, right)
    
    # 合并：如果左右多数相同，直接返回
    if left_majority == right_majority:
        return left_majority
    
    # 否则，分别统计左右候选在完整区间中出现的次数
    left_count = sum(1 for i in range(left, right + 1) if nums[i] == left_majority)
    right_count = sum(1 for i in range(left, right + 1) if nums[i] == right_majority)
    
    # 返回出现次数更多的那个（题目保证有解，所以必有一个超过一半）
    return left_majority if left_count > right_count else right_majority

return divide_and_conquer(0, len(nums) - 1)

主程序：读入数据

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

result = find_majority_element(a) print(result)

3Problem P03. [算法课分治] 找到最大子序和 def max_subarray_divide_conquer(nums):

"""
使用分治法求最大子数组和
"""

def cross_sum(left, right, mid):
    """
    计算跨越中点的最大子数组和
    """
    # 从中点向左扫描，找出最大和
    left_sum = float('-inf')
    curr_sum = 0
    for i in range(mid, left - 1, -1):
        curr_sum += nums[i]
        left_sum = max(left_sum, curr_sum)
    
    # 从中点向右扫描，找出最大和
    right_sum = float('-inf')
    curr_sum = 0
    for i in range(mid + 1, right + 1):
        curr_sum += nums[i]
        right_sum = max(right_sum, curr_sum)
    
    # 返回跨越中点的最大和
    return left_sum + right_sum

def divide_and_conquer(left, right):
    # 基本情况：只有一个元素
    if left == right:
        return nums[left]
    
    # 计算中点
    mid = (left + right) // 2
    
    # 递归求解左半部分和右半部分
    left_max = divide_and_conquer(left, mid)
    right_max = divide_and_conquer(mid + 1, right)
    
    # 计算跨越中点的最大和
    cross_max = cross_sum(left, right, mid)
    
    # 返回三者中的最大值
    return max(left_max, right_max, cross_max)

# 调用递归函数
return divide_and_conquer(0, len(nums) - 1)

主程序：读取输入并输出结果

if __name__ == "__main__":

n = int(input())  # 数组长度
nums = list(map(int, input().split()))  # 数组元素

result = max_subarray_divide_conquer(nums)
print(result)

4Problem P04. [算法课分治] 找到 k 个最小数 import random

def Quickselect(arr, k):

if k < 1 or k >len(arr):
    return None
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k <= len(left):
    return Quickselect(left, k)
elif k > len(left) + len(mid):
    return Quickselect(right, k - len(left) - len(mid))
else:
    return mid[0]

def solve():

n , k = map(int, input().split())
arr = list(map(int,input().split()))
kth =Quickselect(arr, k)
outlist = [x for x in arr if x <= kth]
outlist.sort()
result = outlist[:k]
print(' '.join(map(str, result)))

solve()

6Problem P06. [算法课分治] 找到 k 个最长重复字符串 def longestSubstring(s, k):

"""
递归分治解法：找最长子串，使得每个字符出现次数 ≥ k
"""
n = len(s)
if n < k:
    return 0

from collections import Counter
freq = Counter(s)

# 找第一个频次 < k 的字符
for i, ch in enumerate(s):
    if freq[ch] < k:
        # 以 ch 为分割点，左右递归
        left = longestSubstring(s[:i], k)
        right = longestSubstring(s[i+1:], k)
        return max(left, right)

# 如果所有字符频次都 >= k，说明整个字符串合法
return n

读取输入

line = input().split() s = line[0] k = int(line[1])

输出结果

print(longestSubstring(s, k))

7Problem P07. [算法课动态规划]最长回文子串 def longestPalindrome(s):

n = len(s)
if n == 0:
    return ""

# dp[i][j] 表示 s[i:j+1] 是否是回文
dp = [[False] * n for _ in range(n)]

start = 0  # 最长回文子串起始位置
max_len = 1  # 最长回文子串长度

# 所有长度为 1 的子串都是回文
for i in range(n):
    dp[i][i] = True

# 检查长度为 2 的子串
for i in range(n - 1):
    if s[i] == s[i + 1]:
        dp[i][i + 1] = True
        start = i
        max_len = 2

# 检查长度 >= 3 的子串
for length in range(3, n + 1):  # 子串长度
    for i in range(n - length + 1):
        j = i + length - 1  # 子串结尾索引
        if s[i] == s[j] and dp[i + 1][j - 1]:
            dp[i][j] = True
            if length > max_len:
                start = i
                max_len = length

return s[start:start + max_len]

读取输入

s = input().strip()

输出结果

print(longestPalindrome(s))

Problem P08. [算法课动态规划]连续数组最大和 def solve(nums):

if not nums:
    return 0
n = len(nums)
dp = [0] * n  # 初始化dp数组，每个元素至少是长度
if n ==1:
    return nums[0]
else:
    for i in range(n):
        if i == 0:
            dp[i] = nums[i]
        else:
            dp[i] = max(dp[i-1]+nums[i], nums[i])
return max(dp)

读取输入

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

输出结果

print(solve(nums))

#状态转移方程 i为当前元素索引，dp[i]为以i结尾的最长连续子序列长度
#dp[i] i=1时，dp[i-1]不存在，所以需要特殊处理
#dp[i] = max(dp[i-1]+dp[i],dp[i]) i > 1时

Problem P09. [算法课动态规划]最长公共子序列 def solve(str1, str2):

arr1 = list(str1)
arr2 = list(str2)
m, n = len(arr1), len(arr2)
dp = [[0] * (n + 1) for _ in range(m + 1)]  # 初始化dp数组，大小为(m+1) x (n+1)
if m == 0 or n == 0:
    return "error"
else:
    for i in range(1 , m + 1):
        for j in range(1,n + 1):
            if arr1[i - 1] == arr2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

读取输入

a,b= input().split()

输出结果

print(solve(a, b))

#划分阶段：s1的第i个字符匹配s2第j个字符
#状态定义：dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度
#状态转移方程：
#如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；
# 否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Problem P12. [算法课贪婪]6和9组成的最大数字

def solve(num):

#把6转换为9
#将str变成nums，遍历，遇到6就变成9，没有就不变
nums = list(str(num))
for i in range(len(nums)):
    if nums[i] == '6':
        nums[i] = '9'
        break
return int(''.join(nums))

读取输入

num = int(input())

输出结果

print(solve(num))

Problem P15. [算法课贪婪]移掉 K 位数字

import sys

def remove_k_digits(num, k):

stack = []

# 1. 遍历每个数字
for digit in num:
    # 当还可以删除 (k>0) 且栈不为空 且 栈顶数字比当前数字大
    # 说明栈顶数字在高位且更大，删掉它能让结果更小
    while k > 0 and stack and stack[-1] > digit:
        stack.pop()
        k -= 1
    stack.append(digit)

# 2. 如果 k 还没用完，说明剩下的数字已经是递增的，从末尾删掉
while k > 0:
    stack.pop()
    k -= 1

# 3. 组合结果并处理前导零
result = "".join(stack).lstrip('0')

# 4. 如果结果为空，返回 "0"
return result if result else "0"

读取输入

try:

line = sys.stdin.readline().strip()
if line:
    parts = line.split()
    num_str = parts[0]
    k = int(parts[1])
    print(remove_k_digits(num_str, k))
else:
    print("0")

except:

print("0")

Problem P17. [算法课回溯]括号生成 def generate_parenthesis(n):

result = []
def backtrack(s, left, right):
    if len(s) == 2 * n:
        result.append(s)
        return
    if left < n:
        backtrack(s + '(', left + 1, right)
    if right < left:
        backtrack(s + ')', left, right + 1)
backtrack('', 0, 0)
return result

if __name__ == "__main__":

n = int(input().strip())
output = generate_parenthesis(n)
# 按照题目要求的格式输出，不带引号
print("[" + ", ".join(output) + "]")

Problem P18. [算法课回溯]组合问题

def combine(n, k):

result = []

def backtrack(start, path):
    # 已经选了 k 个数，保存结果
    if len(path) == k:
        result.append(path[:])
        return
    # 从 start 到 n 依次选择
    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1, path)
        path.pop()

backtrack(1, [])
return result

if __name__ == "__main__":

import sys
# 读取输入，例如 "4 2" 或 "5 3"
data = sys.stdin.read().strip().split()
if not data:
    exit()
n, k = map(int, data[:2])
# 输出结果，格式与样例完全一致
print(combine(n, k))

Problem P19. [算法课回溯]找出所有子集的异或总和再求和 def subsetXORSum(nums):

total = 0
n = len(nums)

def dfs(index, current_xor):
    nonlocal total
    if index == n:
        total += current_xor
        return
    # 选当前元素
    dfs(index + 1, current_xor ^ nums[index])
    # 不选当前元素
    dfs(index + 1, current_xor)

dfs(0, 0)
return total

读取输入，格式：一行空格分隔的整数

if __name__ == "__main__":

import sys
data = sys.stdin.read().strip().split()
if not data:
    print(0)
else:
    nums = list(map(int, data))
    print(subsetXORSum(nums))

Problem P20. [算法课回溯]分割回文串 def partition(s):

result = []
path = []

def backtrack(start):
    # 递归出口：切完整个字符串
    if start == len(s):
        result.append(path[:])   # 复制当前路径
        return

    # 尝试每一个可能的切割结束位置 i
    for i in range(start, len(s)):
        sub = s[start:i+1]
        # 约束条件：sub 必须是回文
        if sub == sub[::-1]:
            path.append(sub)      # 做选择
            backtrack(i + 1)      # 递归剩余部分
            path.pop()            # 撤销选择（回溯）

backtrack(0)
return result

格式化输出为无引号的列表形式，以匹配样例输出

def format_output(res):

parts = []
for lst in res:
    parts.append('[' + ', '.join(lst) + ']')
return '[' + ', '.join(parts) + ']'

主程序

if __name__ == "__main__":

s = input().strip()
res = partition(s)
print(format_output(res))

Problem P23. [算法课分支限界法]分割等和子集 import sys

def canPartition(nums):

total = sum(nums)
# 如果总和为奇数，不可能平分
if total % 2 != 0:
    return False

target = total // 2
nums.sort(reverse=True)          # 降序排序，利于剪枝

# 计算后缀和，suffix_sum[i] 表示从 i 到末尾的元素和
n = len(nums)
suffix_sum = [0] * (n + 1)
for i in range(n-1, -1, -1):
    suffix_sum[i] = suffix_sum[i+1] + nums[i]

# 递归分支限界
def dfs(index, cur_sum):
    # 已经达到目标
    if cur_sum == target:
        return True
    # 超出索引范围
    if index >= n:
        return False
    
    # 上限剪枝：如果当前和加上本元素 > target，只能不选
    # 下限剪枝：当前和加上剩余所有 < target，直接返回 False
    if cur_sum + suffix_sum[index] < target:
        return False
    
    # 尝试 选 当前元素
    if cur_sum + nums[index] <= target:
        if dfs(index + 1, cur_sum + nums[index]):
            return True
    
    # 尝试 不选 当前元素（如果还有可能达到 target）
    # 下限剪枝已经判断过 cur_sum + suffix_sum[index+1] >= target
    if cur_sum + suffix_sum[index+1] >= target:
        if dfs(index + 1, cur_sum):
            return True
            
    return False

return dfs(0, 0)

if __name__ == "__main__":

# 读取输入，例如 "1 5 11 5"
line = sys.stdin.readline().strip()
if line:
    nums = list(map(int, line.split()))
    print(str(canPartition(nums)).lower())

Problem P24. [算法课分支限界法]硬币问题 def coin_combinations(amount, coins):

# 面额排序，保证非递减选择
coins.sort()
n = len(coins)
count = 0

def dfs(remain, start_idx):
    nonlocal count
    # 界限条件1：剩余金额为0，找到一种组合
    if remain == 0:
        count += 1
        return
    # 界限条件2：剩余金额小于最小面额，无法继续
    # 因为硬币已排序，coins[start_idx]就是当前可选的最小面额
    if remain < coins[start_idx]:
        return

    for i in range(start_idx, n):
        coin = coins[i]
        if coin > remain:
            break   # 后面的面额更大，不可能满足
        dfs(remain - coin, i)   # i 保证非递减顺序

# 根节点：剩余总额 amount，可选硬币从索引0开始
dfs(amount, 0)
return count

---------- 输入输出 ----------

if __name__ == "__main__":

import sys
data = sys.stdin.read().strip().split()
if not data:
    amount = 5
    coins = [1,2,5]
else:
    amount = int(data[0])
    coins = list(map(int, data[1:]))
print(coin_combinations(amount, coins))

Problem P27. [算法课动态规划] 摆动序列 import sys

def main():

# 读取一整行，分割并转换成整数列表
line = sys.stdin.readline().strip()
if not line:
    return
nums = list(map(int, line.split()))

# 如果数组为空，按要求返回0（题目保证长度>=1，此处仅为防御性编程）
if not nums:
    print(0)
    return

up = down = 1

for i in range(1, len(nums)):
    if nums[i] > nums[i - 1]:
        up = down + 1
    elif nums[i] < nums[i - 1]:
        down = up + 1
    # 相等时什么都不做

print(max(up, down))

if __name__ == "__main__":

main()

Problem P32. [算法课指针] 颜色分类 def sortColors(nums):

p0, cur, p2 = 0, 0, len(nums) - 1
while cur <= p2:
    if nums[cur] == 0:
        nums[p0], nums[cur] = nums[cur], nums[p0]
        p0 += 1
        cur += 1
    elif nums[cur] == 1:
        cur += 1
    else:  # nums[cur] == 2
        nums[cur], nums[p2] = nums[p2], nums[cur]
        p2 -= 1

按照题目格式读取输入并输出

n = int(input()) arr = list(map(int, input().split())) sortColors(arr)

输出格式：[0,0,1,1,2,2]

print("[" + ",".join(map(str, arr)) + "]")

Problem P33. [算法课分治] 找假币 def find_fake_coin(coins):

n = len(coins)
# 前缀和，pref[i] = sum(coins[0:i])
pref = [0] * (n + 1)
for i in range(n):
    pref[i + 1] = pref[i] + coins[i]

def solve(left, right, known_weight):
    """
    在区间 [left, right] 内寻找假币。
    known_weight: 已知的真币单枚重量，若为 None 表示尚未获得。
    返回假币在 coins 中的下标（0-based）。
    """
    # 如果已经知道真币重量，直接扫描找出轻的那一枚
    if known_weight is not None:
        for i in range(left, right + 1):
            if coins[i] < known_weight:
                return i

    length = right - left + 1
    if length == 1:
        return left
    if length == 2:
        # 此时 known_weight 一定已知（由上层不等分支传入）
        return left if coins[left] < known_weight else right

    # 将当前区间分成 AB 两等份，以及可能的剩余 C（0个或1个）
    half = length // 2
    # A: [left, left+half-1]
    # B: [left+half, left+2*half-1]
    # C: [left+2*half, right]
    l1, r1 = left, left + half - 1
    l2, r2 = left + half, left + 2 * half - 1

    sum1 = pref[r1 + 1] - pref[l1]
    sum2 = pref[r2 + 1] - pref[l2]

    if sum1 == sum2:
        # AB 等重 → 全为真币，假币在 C 中
        w = coins[l1]                # 真币重量
        return solve(left + 2 * half, right, w)
    elif sum1 < sum2:
        # A 更轻 → 假币在 A 中，B 全是真币
        w = coins[l2]                # 真币重量
        return solve(l1, r1, w)
    else:
        # B 更轻 → 假币在 B 中，A 全是真币
        w = coins[l1]
        return solve(l2, r2, w)

fake_idx = solve(0, n - 1, None)
return fake_idx + 1   # 题目要求从 1 开始计数

读取输入并输出结果

if __name__ == "__main__":

n = int(input())
coins = list(map(int, input().split()))
print(find_fake_coin(coins))

Problem P34. [算法课贪婪] 最少操作使数组递增 import sys

def min_operations(nums):

if not nums:
    return 0
prev = nums[0]
ans = 0
for i in range(1, len(nums)):
    if nums[i] <= prev:
        ans += (prev + 1 - nums[i])
        prev += 1
    else:
        prev = nums[i]
return ans

def main():

data = sys.stdin.read().strip().split()
if not data:
    return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(min_operations(nums))

if __name__ == "__main__":

main()

Problem P35. [算法课回溯] 组合求和 def combination_sum(k, n):

result = []
path = []

def dfs(start, remaining):
    # 已经选了 k 个数
    if len(path) == k:
        if remaining == 0:
            result.append(path.copy())
        return

    # 还需要选的个数
    need = k - len(path)
    # 剪枝1：剩余可选数字不够
    if 9 - start + 1 < need:
        return
    # 剪枝2：剩余和太小（即使选最小的几个数也达不到）
    min_sum = sum(range(start, start + need))
    if remaining < min_sum:
        return
    # 剪枝3：剩余和太大（即使选最大的几个数也凑不够）
    max_sum = sum(range(9, 9 - need, -1))
    if remaining > max_sum:
        return

    for i in range(start, 10):      # 1 ~ 9
        if i > remaining:           # 后面的数只会更大，直接剪掉
            break
        path.append(i)
        dfs(i + 1, remaining - i)
        path.pop()                  # 回溯

dfs(1, n)

# 按字典序从大到小排序
result.sort(reverse=True)

if not result:
    print(0)
else:
    for comb in result:
        print(' '.join(map(str, comb)))

输入

k, n = map(int, input().split()) combination_sum(k, n)

Problem P36. [算法课动态规划] 完全平方数 import sys import math

def numSquares(n: int) -> int:

# dp[i] 表示和为 i 时所需的最少完全平方数数量
dp = [float('inf')] * (n + 1)
dp[0] = 0

# 预先计算所有不超过 n 的完全平方数
max_root = int(math.isqrt(n))
squares = [k * k for k in range(1, max_root + 1)]

for i in range(1, n + 1):
    for sq in squares:
        if sq > i:
            break
        dp[i] = min(dp[i], dp[i - sq] + 1)

return dp[n]

if __name__ == "__main__":

line = sys.stdin.readline().strip()
if line:
    n = int(line)
    print(numSquares(n))