适用人群：所有开发者、面试准备
学习时长：约2-4周（每天2小时）
重要程度：★★★★☆（面试必考、提升编程能力）
一、为什么要学算法？
| 场景 | 作用 |
|---|
| 面试 | 大厂必考算法题 |
| 编程能力 | 提升代码质量和效率 |
| 问题解决 | 培养逻辑思维 |
| 性能优化 | 理解时间/空间复杂度 |
二、复杂度分析
2.1 时间复杂度
# O(1) - 常数时间
def get_first(arr):
return arr[0]
# O(log n) - 对数时间
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# O(n) - 线性时间
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# O(n²) - 平方时间
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# O(2^n) - 指数时间
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
2.2 常见复杂度对比
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
1. 常数时间：哈希表查找
2. 对数时间：二分查找
3. 线性时间：遍历数组
4. 线性对数：快速排序
5. 平方时间：冒泡排序
6. 指数时间：递归斐波那契
三、基本数据结构
3.1 数组（Array）
# 特点：连续内存、随机访问O(1)、插入删除O(n)
class MyArray:
def __init__(self):
self.data = []
def get(self, index):
return self.data[index] # O(1)
def append(self, val):
self.data.append(val) # O(1) 均摊
def insert(self, index, val):
self.data.insert(index, val) # O(n)
def delete(self, index):
self.data.pop(index) # O(n)
3.2 链表（Linked List）
# 特点：非连续内存、插入删除O(1)、查找O(n)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete(self, val):
if not self.head:
return
if self.head.val == val:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.val == val:
current.next = current.next.next
return
current = current.next
def to_list(self):
result = []
current = self.head
while current:
result.append(current.val)
current = current.next
return result
3.3 栈（Stack）
# 特点：后进先出（LIFO）
class Stack:
def __init__(self):
self.data = []
def push(self, val):
self.data.append(val) # O(1)
def pop(self):
return self.data.pop() # O(1)
def peek(self):
return self.data[-1] # O(1)
def is_empty(self):
return len(self.data) == 0
# 应用：括号匹配、表达式求值、浏览器历史
3.4 队列（Queue）
# 特点：先进先出（FIFO）
from collections import deque
class Queue:
def __init__(self):
self.data = deque()
def enqueue(self, val):
self.data.append(val) # O(1)
def dequeue(self):
return self.data.popleft() # O(1)
def front(self):
return self.data[0]
def is_empty(self):
return len(self.data) == 0
# 应用：BFS、任务队列、消息队列
3.5 哈希表（Hash Table）
# 特点：查找O(1)、插入O(1)、删除O(1)
class HashTable:
def __init__(self, size=16):
self.size = size
self.data = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, val):
index = self._hash(key)
bucket = self.data[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
index = self._hash(key)
bucket = self.data[index]
for k, v in bucket:
if k == key:
return v
return None
def delete(self, key):
index = self._hash(key)
bucket = self.data[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
return True
return False
# 应用：缓存、去重、计数
3.6 树（Tree）
# 二叉树
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前序遍历（根-左-右）
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# 中序遍历（左-根-右）- BST有序
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
# 后序遍历（左-右-根）
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
# 层序遍历（BFS）
from collections import deque
def levelorder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
四、常见算法
4.1 排序算法
# 冒泡排序 - O(n²)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 选择排序 - O(n²)
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 插入排序 - O(n²)
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
# 快速排序 - O(n log n)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 归并排序 - O(n log n)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
4.2 搜索算法
# 二分查找 - O(log n)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# BFS广度优先搜索
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# DFS深度优先搜索
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
4.3 动态规划
# 斐波那契数列
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 爬楼梯
def climb_stairs(n):
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]
# 最大子序和
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# 0-1背包问题
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w-weights[i-1]] + values[i-1]
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
五、LeetCode 题目精选
5.1 数组
# #1 两数之和
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# #15 三数之和
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return result
5.2 链表
# #206 反转链表
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# #21 合并两个有序链表
def merge_two_lists(l1, l2):
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
5.3 字符串
# #20 有效的括号
def is_valid(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
# #5 最长回文子串
def longest_palindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
if length == 2 or dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start + max_len]
学习建议
- 先理解基本数据结构：数组、链表、栈、队列、哈希表
- 学习排序和搜索算法：这是基础中的基础
- 每天刷1-2道LeetCode，坚持比数量更重要
- 理解算法思想：分治、贪心、动态规划、回溯
- 总结模板，遇到类似题目套用
学习资源