算法思想¶

在计算机科学中，算法是解决问题的方法和步骤的有序集合。不同的问题需要采用不同的算法思想来解决。本文将详细介绍常见的算法思想，包括贪心算法、分治法、动态规划、回溯法、深度优先搜索和广度优先搜索，并给出相应的力扣题目和题解代码。、

贪心（Greedy Algorithm）¶

概念：贪心算法是一种在每一步选择中都选择当前最优解的算法思想。它通过贪心的选择策略，希望最终能够达到全局最优解。贪心算法通常不保证能够得到最优解，但在一些特定问题中，贪心算法可以得到近似最优解。

用途：贪心算法常用于优化问题，如最短路径问题、背包问题、任务调度等。它的优势在于简单、高效，适用于一些具有贪心选择性质的问题。

力扣题目： 455. Assign Cookies：分发饼干，通过贪心算法分配饼干满足尽可能多的孩子。

参考题解：

from typing import List

# 分发饼干
def findContentChildren(g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    i = 0
    j = 0
    count = 0
    while i < len(g) and j < len(s):
        if g[i] <= s[j]:
            count += 1
            i += 1
        j += 1
    return count

Best Time to Buy and Sell Stock II：股票买卖，通过贪心算法获取最大利润。

参考题解：

from typing import List

# 股票买卖
def maxProfit(prices: List[int]) -> int:
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            max_profit += prices[i] - prices[i-1]
    return max_profit

分治法（Divide and Conquer）¶

概念：分治法是一种将问题划分为若干个独立的子问题，分别求解子问题，然后将子问题的解组合起来得到原问题的解的算法思想。

用途：分治法常用于解决规模较大且具有重叠子问题性质的问题，如快速排序、归并排序、最大子数组和等问题。

力扣题目： 53. Maximum Subarray：最大子数组和，通过分治法求解最大子数组的和。

参考题解：

from typing import List

# 最大子数组和
def maxSubArray(nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    mid = len(nums) // 2
    left_max = maxSubArray(nums[:mid])
    right_max = maxSubArray(nums[mid:])
    cross_max = crossSum(nums, mid)
    return max(left_max, right_max, cross_max)

def crossSum(nums: List[int], mid: int) -> int:
    left_sum = float('-inf')
    curr_sum = 0
    for i in range(mid - 1, -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, len(nums)):
        curr_sum += nums[i]
        right_sum = max(right_sum, curr_sum)
    return left_sum + right_sum - nums[mid]

回溯法（Backtracking）¶

概念：回溯法是一种通过不断地尝试各种可能的解，当发现当前尝试的解不满足要求时，回退到上一步继续尝试其他可能的解的算法思想。

用途：回溯法常用于求解组合问题、排列问题、图的遍历等，它可以穷尽所有可能的解空间。

力扣题目： 39. Combination Sum：组合总和，通过回溯法求解所有满足条件的数字组合。

参考题解：

from typing import List

# 组合总和
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    def backtrack(start: int, path: List[int], target: int):
        if target == 0:
            result.append(path)
            return
        if target < 0:
            return
        for i in range(start, len(candidates)):
            backtrack(i, path + [candidates[i]], target - candidates[i])

    result = []
    backtrack(0, [], target)
    return result

动态规划（Dynamic Programming）¶

概念：动态规划是一种将问题分解为更简单的子问题，并利用子问题的解来求解原问题的算法思想。动态规划通常采用自底向上的方式，通过保存已经求解过的子问题的解，避免重复计算。

用途：动态规划常用于求解具有重叠子问题和最优子结构性质的问题，如背包问题、最长递增子序列、最短路径等。

力扣题目： 70. Climbing Stairs：爬楼梯，通过动态规划计算爬楼梯的方法数。

参考题解：

# 爬楼梯
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Longest Increasing Subsequence：最长递增子序列，通过动态规划求解最长递增子序列的长度。

from typing import List

# 最长递增子序列
def lengthOfLIS(nums: List[int]) -> int:
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

深搜（DFS）¶

概念：深度优先搜索(Depth-First Search)是一种从起始节点开始，不断向深处搜索，直到无法继续搜索为止，然后回溯到上一个节点，继续搜索其他分支的算法思想。

用途：深度优先搜索常用于解决图的遍历问题，如连通性、路径查找等。它通常通过递归或栈来实现。

力扣题目： 200. Number of Islands：岛屿数量，通过深度优先搜索计算矩阵中岛屿的数量。

参考题解：

from typing import List

# 岛屿数量
def numIslands(grid: List[List[str]]) -> int:
    def dfs(grid: List[List[str]], i: int, j: int):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(grid, i-1, j)
        dfs(grid, i+1, j)
        dfs(grid, i, j-1)
        dfs(grid, i, j+1)

    if not grid:
        return 0
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count += 1
                dfs(grid, i, j)
    return count

广搜（BFS）¶

概念：广度优先搜索(Breadth-First Search)是一种从起始节点开始，逐层扩展搜索的算法思想。它先搜索当前层的所有节点，再搜索下一层的节点，直到找到目标节点或遍历完整个图。

用途：广度优先搜索常用于解决最短路径、连通性等问题。它通常通过队列来实现。

力扣题目： 127. Word Ladder：单词接龙，通过广度优先搜索找到从起始单词转换到目标单词的最短转换序列。

参考题解：

from collections import deque
from typing import List

# 单词接龙
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    queue = deque()
    queue.append((beginWord, 1))

    while queue:
        curr_word, level = queue.popleft()
        if curr_word == endWord:
            return level

        for i in range(len(curr_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = curr_word[:i] + c + curr_word[i+1:]
                if new_word in wordSet:
                    wordSet.remove(new_word)
                    queue.append((new_word, level + 1))

    return 0

本文详细介绍了常见的算法思想，包括贪心算法、分治法、动态规划、回溯法、深度优先搜索和广度优先搜索，并给出了相应的力扣题目和题解代码。

这些算法思想在解决各种复杂问题时具有重要的作用，希望能为读者提供帮助。在实际应用中，根据具体问题选择合适的算法思想，并结合优化技巧和数据结构，可以更高效地解决问题。