算法思想¶
在计算机科学中,算法是解决问题的方法和步骤的有序集合。不同的问题需要采用不同的算法思想来解决。本文将详细介绍常见的算法思想,包括贪心算法、分治法、动态规划、回溯法、深度优先搜索和广度优先搜索,并给出相应的力扣题目和题解代码。、
贪心(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
本文详细介绍了常见的算法思想,包括贪心算法、分治法、动态规划、回溯法、深度优先搜索和广度优先搜索,并给出了相应的力扣题目和题解代码。
这些算法思想在解决各种复杂问题时具有重要的作用,希望能为读者提供帮助。在实际应用中,根据具体问题选择合适的算法思想,并结合优化技巧和数据结构,可以更高效地解决问题。