当前位置：首页 > article >正文

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

article 2024/11/14 21:34:02

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