力扣刷题之旅：进阶篇（三）
力扣（LeetCode）是一个在线编程平台，主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目，以及它们的解题代码。
--点击进入刷题地址
一、动态规划（DP）
-
首先，让我们来看一个使用动态规划解决“最长回文子串”问题的代码示例：
def longestPalindrome(s: str) -> str: n = len(s) if n < 2: return s # dp[i][j] 表示从索引 i 到 j 的子串是否为回文串 dp = [[False] * n for _ in range(n)] start, max_len = 0, 1 # 记录最长回文子串的起始位置和长度 # 单个字符一定是回文串 for i in range(n): dp[i][i] = True if n > 1 and s[i] == s[i + 1]: dp[i][i + 1] = True start = i max_len = 2 # 检查长度大于 2 的子串 for l in range(3, n + 1): for i in range(n - l + 1): j = i + l - 1 if s[i] == s[j] and dp[i + 1][j - 1]: dp[i][j] = True if l > max_len: start = i max_len = l return s[start:start + max_len] # 示例用法
print(longestPalindrome("babad")) # 输出: "bab"二、回溯算法
-
接下来，我们来看一个使用回溯算法解决“组合总和”问题的代码示例：
def combinationSum(candidates: List[int], target: int) -> List[List[int]]: def backtrack(start, path, target): if target == 0: result.append(path) return for i in range(start, len(candidates)): # 剪枝：如果当前数字大于目标值，则后续的数字一定也大于目标值，可以提前退出循环 if candidates[i] > target: break # 选择当前数字 backtrack(i, path + [candidates[i]], target - candidates[i]) candidates.sort() # 对数组进行排序，有助于提前退出循环进行剪枝 result = [] backtrack(0, [], target) return result # 示例用法
print(combinationSum([2, 3, 6, 7], 7)) # 输出: [[2, 2, 3], [7]]三、堆（Heap）
- 最后，我们来看一个使用堆（特别是最小堆）解决“K个最小数”问题的代码示例：
import heapq def getKthSmallest(nums: List[int], k: int) -> int: return heapq.nsmallest(k, nums)[-1] # 示例用法
print(getKthSmallest([3,2,1,5,6,4], 2)) # 输出: 5这些代码示例展示了动态规划、回溯算法和堆在解决实际问题中的应用。通过不断学习和实践，我们可以逐渐掌握这些算法的核心思想和应用技巧，为解决更复杂的问题打下坚实的基础。