力扣刷题之旅：进阶篇（三）

        力扣（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

        这些代码示例展示了动态规划、回溯算法和堆在解决实际问题中的应用。通过不断学习和实践，我们可以逐渐掌握这些算法的核心思想和应用技巧，为解决更复杂的问题打下坚实的基础。