以下是20个常见的算法竞赛题目及其解答示例： 

1.最大子序列和问题

题目：给定一个整数数组，找到一个具有最大和的连续子数组。 示例解答：

def max_subarray_sum(nums):
    max_sum = float('-inf')
    curr_sum = 0
    for num in nums:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)
    return max_sum

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(nums))  # 输出：6

2.最长递增子序列问题

题目：给定一个整数数组，找到其中最长的递增子序列的长度。 示例解答：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums))  # 输出：4

3.最小生成树问题

题目：给定一个带权重的无向图，找到一个最小生成树，使得所有边的权重之和最小。 示例解答：

from collections import defaultdict
from heapq import *

def minimum_spanning_tree(graph):
    mst = []
    visited = set()
    start_node = list(graph.keys())[0]
    visited.add(start_node)
    edges = [(cost, start_node, to) for to, cost in graph[start_node]]
    heapify(edges)
    
    while edges:
        cost, frm, to = heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            for next_to, next_cost in graph[to]:
                if next_to not in visited:
                    heappush(edges, (next_cost, to, next_to))
    
    return mst

graph = defaultdict(list)
graph['A'] = [('B', 2), ('C', 3)]
graph['B'] = [('A', 2), ('C', 1), ('D', 1)]
graph['C'] = [('A', 3), ('B', 1), ('D', 2)]
graph['D'] = [('B', 1), ('C', 2)]
print(minimum_spanning_tree(graph))  # 输出：[('A', 'B', 2), ('B', 'C', 1), ('C', 'D', 2)]

4.最短路径问题

题目：给定一个带权重的有向图，找到从起点到终点的最短路径。 示例解答：

from collections import defaultdict
from heapq import *

def shortest_path(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        curr_dist, curr_node = heappop(heap)
        if curr_dist > distances[curr_node]:
            continue
        if curr_node == end:
            break
        for neighbor, weight in graph[curr_node]:
            distance = curr_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heappush(heap, (distance, neighbor))
    
    return distances[end]

graph = defaultdict(list)
graph['A'] = [('B', 2), ('C', 3)]
graph['B'] = [('C', 1), ('D', 1)]
graph['C'] = [('D', 2)]
graph['D'] = []
print(shortest_path(graph, 'A', 'D'))  # 输出：3

5.背包问题

题目：给定一组物品的重量和价值，以及一个背包的容量，找到能够装入背包的物品的最大总价值。 示例解答：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
            else:
                dp[i][j] = dp[i - 1][j]
    
    return dp[n][capacity]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))  # 输出：9

6.图的拓扑排序问题

题目：给定一个有向无环图，对其进行拓扑排序。 示例解答：

from collections import defaultdict

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]

graph = defaultdict(list)
graph['A'] = ['B', 'C']
graph['B'] = ['D']
graph['C'] = ['D']
graph['D'] = []
print(topological_sort(graph))  # 输出：['A', 'C', 'B', 'D']

7.两数之和问题

 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。示例解答：

def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return []

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))  # 输出 [0, 1]

8.最小编辑距离问题

题目：给定两个字符串，找到将一个字符串转换为另一个字符串所需的最小编辑次数（插入、删除、替换）。 示例解答：

def min_edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
    
    return dp[m][n]

word1 = "horse"
word2 = "ros"
print(min_edit_distance(word1, word2))  # 输出：3

9.最长公共子序列问题

题目：给定两个字符串，找到它们的最长公共子序列的长度。 示例解答：

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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]

text1 = "abcde"
text2 = "ace"
print(longest_common_subsequence(text1, text2))  # 输出：3

10.无重复字符的最长子串问题

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例解答：

def lengthOfLongestSubstring(s):
    max_len = 0
    start = 0
    char_map = {}
    for i, char in enumerate(s):
        if char in char_map and start <= char_map[char]:
            start = char_map[char] + 1
        else:
            max_len = max(max_len, i - start + 1)
        char_map[char] = i
    return max_len

s = "abcabcbb"
print(lengthOfLongestSubstring(s))  # 输出 3

11.最长回文子串问题

题目：给定一个字符串，找到其中最长的回文子串。 示例解答：

def longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    for i in range(n):
        dp[i][i] = True
    
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                if j - i == 1 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if j - i + 1 > max_len:
                        start = i
                        max_len = j - i + 1
    
    return s[start:start + max_len]

s = "babad"
print(longest_palindrome(s))  # 输出："bab"

12.最小覆盖子串问题

给你一个字符串 s 、一个字符串 t ，请在字符串 s 里面找出包含 t 所有字符的最小子串。示例解答：

def minWindow(s, t):
    if len(s) < len(t):
        return ""
    target_map = {}
    for char in t:
        target_map[char] = target_map.get(char, 0) + 1
    required = len(target_map)
    formed = 0
    window_map = {}
    ans = float('inf'), None, None
    left, right = 0, 0
    while right < len(s):
        char = s[right]
        window_map[char] = window_map.get(char, 0) + 1
        if char in target_map and window_map[char] == target_map[char]:
            formed += 1
        while left <= right and formed == required:
            char = s[left]
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            window_map[char] -= 1
            if char in target_map and window_map[char] < target_map[char]:
                formed -= 1
            left += 1
        right += 1
    return "" if ans[0] == float('inf') else s[ans[1]: ans[2] + 1]

s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t))  # 输出 "BANC"

13.单词拆分问题

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。示例解答：

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[-1]

s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # 输出 True

14.最小基因变化问题

给定两个字符串 start 和 end，以及一个字符串列表 bank，每次可以将一个字母替换为另一个字母。只有在 bank 中的有效变化才算作一次基因变化。返回从 start 到 end 的最小基因变化次数，如果无法实现，则返回 -1。示例解答：

from collections import deque

def minMutation(start, end, bank):
    bank_set = set(bank)
    if end not in bank_set:
        return -1
    queue = deque([(start, 0)])
    while queue:
        gene, level = queue.popleft()
        if gene == end:
            return level
        for i in range(len(gene)):
            for char in 'ACGT':
                new_gene = gene[:i] + char + gene[i+1:]
                if new_gene in bank_set:
                    bank_set.remove(new_gene)
                    queue.append((new_gene, level + 1))
    return -1

start = "AACCGGTT"
end = "AACCGGTA"
bank = ["AACCGGTA"]
print(minMutation(start, end, bank))  # 输出 1

15.任务调度器问题

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。示例解答：

from collections import Counter

def leastInterval(tasks, n):
    counter = Counter(tasks)
    max_freq = max(counter.values())
    max_count = sum(1 for count in counter.values() if count == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

tasks = ["A", "A", "A", "B", "B", "B"]
n = 2
print(leastInterval(tasks, n))  # 输出 8

16.单词接龙问题

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：每次转换只能改变一个字母；转换过程中的中间单词必须是字典中的单词。示例解答：

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    queue = deque([(beginWord, 1)])
    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length
        for i in range(len(word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + char + word[i+1:]
                if new_word in word_set:
                    word_set.remove(new_word)
                    queue.append((new_word, length + 1))
    return 0

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladderLength(beginWord, endWord, wordList))  # 输出 5

17.课程表问题

现在你总共有 n 门课需要选，记为 0 到 n-1。给定一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须选修课程 bi 。例如，先修课程 1 后才能选修课程 0 ，表示为 [0,1] 。请你判断是否可能完成所有课程的学习？示例解答：

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    visited = [0] * numCourses
    for pair in prerequisites:
        x, y = pair
        graph[x].append(y)

    def dfs(i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True
        visited[i] = -1
        for j in graph[i]:
            if not dfs(j):
                return False
        visited[i] = 1
        return True

    for i in range(numCourses):
        if not dfs(i):
            return False
    return True

numCourses = 2
prerequisites = [[1, 0]]
print(canFinish(numCourses, prerequisites))  # 输出 True

18.二叉树的最近公共祖先问题

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。示例解答：

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

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
p = root.left
q = root.right
print(lowestCommonAncestor(root, p, q).val)  # 输出 3

19.二叉树的层序遍历问题

给定一个二叉树，返回其按层序遍历得到的节点值（从左到右，逐层访问）。示例解答：

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

def levelOrder(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(levelOrder(root))  # 输出 [[3], [9, 20], [15, 7]]

20.二叉树的最大深度问题

给定一个二叉树，找出其最大深度。示例解答：

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

def maxDepth(root):
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(maxDepth(root))  # 输出 3