算法与数据结构题集
大约 17 分钟约 5171 字
算法与数据结构题集
简介
算法与数据结构是编程面试的核心基础，也是构建高效软件系统的基石。本文系统整理常见算法模式，包括双指针、滑动窗口、二分查找、BFS/DFS、动态规划、贪心等，配合 C# 实现与复杂度分析。每种模式提供模板代码和经典题目解析，帮助建立系统化的解题思维。
特点
双指针模式
模板与经典题
/// <summary>
/// 双指针模式
/// 适用场景：有序数组、字符串翻转、去重、配对
/// </summary>
public class TwoPointerPattern
{
/// <summary>
/// 模板：对撞指针（从两端向中间）
/// 经典题：两数之和 II（有序数组）
/// LeetCode 167
/// </summary>
public int[] TwoSum(int[] numbers, int target)
{
int left = 0, right = numbers.Length - 1;
while (left < right)
{
int sum = numbers[left] + numbers[right];
if (sum == target)
return [left + 1, right + 1]; // 1-indexed
else if (sum < target)
left++;
else
right--;
}
return []; // 未找到
}
/// <summary>
/// 经典题：盛最多水的容器
/// LeetCode 11
/// 时间 O(n)，空间 O(1)
/// </summary>
public int MaxArea(int[] height)
{
int left = 0, right = height.Length - 1;
int maxArea = 0;
while (left < right)
{
// 计算当前面积
int width = right - left;
int h = Math.Min(height[left], height[right]);
maxArea = Math.Max(maxArea, width * h);
// 移动较短的边（贪心策略）
if (height[left] < height[right])
left++;
else
right--;
}
return maxArea;
}
/// <summary>
/// 经典题：三数之和
/// LeetCode 15
/// 时间 O(n^2)，空间 O(1)
/// </summary>
public IList<IList<int>> ThreeSum(int[] nums)
{
var result = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length - 2; i++)
{
// 跳过重复的第一个数
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 第一个数已经大于 0，不可能有解
if (nums[i] > 0) break;
int left = i + 1, right = nums.Length - 1;
while (left < right)
{
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0)
{
result.Add(new List<int> { nums[i], nums[left], nums[right] });
// 跳过重复
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
else if (sum < 0)
left++;
else
right--;
}
}
return result;
}
/// <summary>
/// 快慢指针（同向双指针）
/// 经典题：删除有序数组中的重复项
/// LeetCode 26
/// </summary>
public int RemoveDuplicates(int[] nums)
{
if (nums.Length == 0) return 0;
int slow = 0; // 慢指针：指向不重复元素的末尾
for (int fast = 1; fast < nums.Length; fast++)
{
if (nums[fast] != nums[slow])
{
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
/// <summary>
/// 快慢指针应用：判断链表是否有环
/// LeetCode 141
/// </summary>
public bool HasCycle(ListNode? head)
{
var slow = head;
var fast = head;
while (fast != null && fast.next != null)
{
slow = slow!.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}
public class ListNode
{
public int val;
public ListNode? next;
public ListNode(int val = 0, ListNode? next = null)
{
this.val = val;
this.next = next;
}
}滑动窗口模式
模板与经典题
/// <summary>
/// 滑动窗口模式
/// 适用场景：子串/子数组问题，连续区间上的统计
/// </summary>
public class SlidingWindowPattern
{
/// <summary>
/// 模板：可变大小滑动窗口
/// 经典题：无重复字符的最长子串
/// LeetCode 3
/// 时间 O(n)，空间 O(min(m, n))，m 为字符集大小
/// </summary>
public int LengthOfLongestSubstring(string s)
{
var charIndex = new Dictionary<char, int>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.Length; right++)
{
char c = s[right];
// 如果字符已出现在窗口内，移动左边界
if (charIndex.TryGetValue(c, out int prevIndex) && prevIndex >= left)
{
left = prevIndex + 1;
}
charIndex[c] = right;
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}
/// <summary>
/// 固定大小滑动窗口
/// 经典题：找到字符串中所有字母异位词
/// LeetCode 438
/// 时间 O(n)，空间 O(1)
/// </summary>
public IList<int> FindAnagrams(string s, string p)
{
var result = new List<int>();
if (s.Length < p.Length) return result;
int[] pCount = new int[26];
int[] sCount = new int[26];
// 初始化窗口
for (int i = 0; i < p.Length; i++)
{
pCount[p[i] - 'a']++;
sCount[s[i] - 'a']++;
}
if (AreEqual(pCount, sCount))
result.Add(0);
// 滑动窗口
for (int i = p.Length; i < s.Length; i++)
{
// 添加新字符
sCount[s[i] - 'a']++;
// 移除旧字符
sCount[s[i - p.Length] - 'a']--;
if (AreEqual(pCount, sCount))
result.Add(i - p.Length + 1);
}
return result;
}
private static bool AreEqual(int[] a, int[] b)
{
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i]) return false;
}
return true;
}
/// <summary>
/// 最小覆盖子串
/// LeetCode 76
/// </summary>
public string MinWindow(string s, string t)
{
if (s.Length < t.Length) return "";
var need = new Dictionary<char, int>();
foreach (char c in t)
need[c] = need.GetValueOrDefault(c) + 1;
var have = new Dictionary<char, int>();
int needCount = need.Count;
int haveCount = 0;
int left = 0;
int minLen = int.MaxValue;
int minStart = 0;
for (int right = 0; right < s.Length; right++)
{
char c = s[right];
have[c] = have.GetValueOrDefault(c) + 1;
if (need.ContainsKey(c) && have[c] == need[c])
haveCount++;
// 收缩窗口
while (haveCount == needCount)
{
if (right - left + 1 < minLen)
{
minLen = right - left + 1;
minStart = left;
}
char leftChar = s[left];
have[leftChar]--;
if (need.ContainsKey(leftChar) && have[leftChar] < need[leftChar])
haveCount--;
left++;
}
}
return minLen == int.MaxValue ? "" : s.Substring(minStart, minLen);
}
}二分查找模式
模板与经典题
/// <summary>
/// 二分查找模式
/// 适用场景：有序数据搜索、答案二分、旋转数组
/// </summary>
public class BinarySearchPattern
{
/// <summary>
/// 模板1：标准二分（找精确值）
/// </summary>
public int Search(int[] nums, int target)
{
int left = 0, right = nums.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
/// <summary>
/// 模板2：找左边界（lower bound）
/// 经典题：在排序数组中查找元素的第一个和最后一个位置
/// LeetCode 34
/// </summary>
public int[] SearchRange(int[] nums, int target)
{
return [FindBound(nums, target, true), FindBound(nums, target, false)];
}
private int FindBound(int[] nums, int target, bool isLeft)
{
int left = 0, right = nums.Length - 1;
int result = -1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
result = mid;
if (isLeft) right = mid - 1; // 继续向左找
else left = mid + 1; // 继续向右找
}
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return result;
}
/// <summary>
/// 经典题：搜索旋转排序数组
/// LeetCode 33
/// 时间 O(log n)
/// </summary>
public int SearchRotated(int[] nums, int target)
{
int left = 0, right = nums.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 判断哪半边是有序的
if (nums[left] <= nums[mid])
{
// 左半边有序
if (target >= nums[left] && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else
{
// 右半边有序
if (target > nums[mid] && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
/// <summary>
/// 答案二分：珂珂吃香蕉
/// LeetCode 875
/// </summary>
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
while (left < right)
{
int mid = left + (right - left) / 2;
if (CanFinish(piles, mid, h))
right = mid;
else
left = mid + 1;
}
return left;
}
private bool CanFinish(int[] piles, int speed, int h)
{
int hours = 0;
foreach (int pile in piles)
{
hours += (pile + speed - 1) / speed; // 向上取整
}
return hours <= h;
}
}BFS/DFS 模式
树的遍历
/// <summary>
/// BFS/DFS 模式
/// 适用场景：树的遍历、图的搜索、网格问题
/// </summary>
public class BfsDfsPattern
{
/// <summary>
/// BFS 模板：层序遍历
/// LeetCode 102
/// </summary>
public IList<IList<int>> LevelOrder(TreeNode? root)
{
var result = new List<IList<int>>();
if (root == null) return result;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
int levelSize = queue.Count;
var level = new List<int>();
for (int i = 0; i < levelSize; i++)
{
var node = queue.Dequeue();
level.Add(node.val);
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
result.Add(level);
}
return result;
}
/// <summary>
/// DFS 模板：递归遍历
/// 经典题：二叉树的最大深度
/// LeetCode 104
/// </summary>
public int MaxDepth(TreeNode? root)
{
if (root == null) return 0;
return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
}
/// <summary>
/// DFS 应用：路径总和
/// LeetCode 112
/// </summary>
public bool HasPathSum(TreeNode? root, int targetSum)
{
if (root == null) return false;
// 叶子节点
if (root.left == null && root.right == null)
return root.val == targetSum;
int remaining = targetSum - root.val;
return HasPathSum(root.left, remaining) || HasPathSum(root.right, remaining);
}
/// <summary>
/// BFS 应用：岛屿数量
/// LeetCode 200
/// 时间 O(m*n)，空间 O(m*n)
/// </summary>
public int NumIslands(char[][] grid)
{
if (grid.Length == 0) return 0;
int count = 0;
int rows = grid.Length;
int cols = grid[0].Length;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (grid[i][j] == '1')
{
count++;
BfsFill(grid, i, j, rows, cols);
}
}
}
return count;
}
private void BfsFill(char[][] grid, int startRow, int startCol, int rows, int cols)
{
var queue = new Queue<(int r, int c)>();
queue.Enqueue((startRow, startCol));
grid[startRow][startCol] = '0';
int[][] directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
while (queue.Count > 0)
{
var (r, c) = queue.Dequeue();
foreach (var dir in directions)
{
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1')
{
grid[nr][nc] = '0';
queue.Enqueue((nr, nc));
}
}
}
}
/// <summary>
/// DFS 应用：单词搜索
/// LeetCode 79
/// </summary>
public bool Exist(char[][] board, string word)
{
int rows = board.Length;
int cols = board[0].Length;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (DfsSearch(board, word, i, j, 0))
return true;
}
}
return false;
}
private bool DfsSearch(char[][] board, string word, int r, int c, int index)
{
if (index == word.Length) return true;
if (r < 0 || r >= board.Length || c < 0 || c >= board[0].Length) return false;
if (board[r][c] != word[index]) return false;
// 标记已访问
char temp = board[r][c];
board[r][c] = '#';
// 四个方向搜索
bool found = DfsSearch(board, word, r + 1, c, index + 1)
|| DfsSearch(board, word, r - 1, c, index + 1)
|| DfsSearch(board, word, r, c + 1, index + 1)
|| DfsSearch(board, word, r, c - 1, index + 1);
// 恢复
board[r][c] = temp;
return found;
}
}
public class TreeNode
{
public int val;
public TreeNode? left;
public TreeNode? right;
public TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
{
this.val = val;
this.left = left;
this.right = right;
}
}动态规划模式
经典题目
/// <summary>
/// 动态规划模式
/// 适用场景：最优子结构 + 重叠子问题
/// </summary>
public class DynamicProgrammingPattern
{
/// <summary>
/// 模板：爬楼梯（最简 DP）
/// LeetCode 70
/// dp[i] = dp[i-1] + dp[i-2]
/// </summary>
public int ClimbStairs(int n)
{
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++)
{
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/// <summary>
/// 经典题：最长递增子序列
/// LeetCode 300
/// 方法1：DP O(n^2)
/// 方法2：二分查找 O(n log n)
/// </summary>
public int LengthOfLIS(int[] nums)
{
// 方法2：贪心 + 二分
var tails = new List<int>();
foreach (int num in nums)
{
int left = 0, right = tails.Count;
while (left < right)
{
int mid = left + (right - left) / 2;
if (tails[mid] < num)
left = mid + 1;
else
right = mid;
}
if (left == tails.Count)
tails.Add(num);
else
tails[left] = num;
}
return tails.Count;
}
/// <summary>
/// 经典题：0-1 背包问题
/// dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
/// </summary>
public int Knapsack(int[] weights, int[] values, int capacity)
{
int n = weights.Length;
var dp = new int[capacity + 1];
for (int i = 0; i < n; i++)
{
// 从后向前遍历（0-1 背包，每件只能选一次）
for (int j = capacity; j >= weights[i]; j--)
{
dp[j] = Math.Max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
/// <summary>
/// 经典题：编辑距离
/// LeetCode 72
/// 时间 O(m*n)，空间 O(m*n)
/// </summary>
public int MinDistance(string word1, string word2)
{
int m = word1.Length, n = word2.Length;
var dp = new int[m + 1, n + 1];
// 初始化
for (int i = 0; i <= m; i++) dp[i, 0] = i;
for (int j = 0; j <= n; j++) dp[0, j] = j;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (word1[i - 1] == word2[j - 1])
{
dp[i, j] = dp[i - 1, j - 1]; // 字符相同，无需操作
}
else
{
dp[i, j] = 1 + Math.Min(
dp[i - 1, j - 1], // 替换
Math.Min(
dp[i - 1, j], // 删除
dp[i, j - 1] // 插入
)
);
}
}
}
return dp[m, n];
}
/// <summary>
/// 经典题：最长公共子序列
/// LeetCode 1143
/// </summary>
public int LongestCommonSubsequence(string text1, string text2)
{
int m = text1.Length, n = text2.Length;
var dp = new int[m + 1, n + 1];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (text1[i - 1] == text2[j - 1])
dp[i, j] = dp[i - 1, j - 1] + 1;
else
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}
}
return dp[m, n];
}
/// <summary>
/// 经典题：打家劫舍
/// LeetCode 198
/// </summary>
public int Rob(int[] nums)
{
if (nums.Length == 0) return 0;
if (nums.Length == 1) return nums[0];
int prev2 = 0, prev1 = nums[0];
for (int i = 1; i < nums.Length; i++)
{
int current = Math.Max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}链表操作
经典题目
/// <summary>
/// 链表经典操作
/// </summary>
public class LinkedListPattern
{
/// <summary>
/// 反转链表
/// LeetCode 206
/// </summary>
public ListNode? ReverseList(ListNode? head)
{
ListNode? prev = null;
var current = head;
while (current != null)
{
var next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
/// <summary>
/// 合并两个有序链表
/// LeetCode 21
/// </summary>
public ListNode? MergeTwoLists(ListNode? list1, ListNode? list2)
{
var dummy = new ListNode();
var current = dummy;
while (list1 != null && list2 != null)
{
if (list1.val <= list2.val)
{
current.next = list1;
list1 = list1.next;
}
else
{
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = list1 ?? list2;
return dummy.next;
}
/// <summary>
/// 合并 K 个有序链表
/// LeetCode 23
/// 时间 O(N log k)，N 为总节点数，k 为链表数
/// </summary>
public ListNode? MergeKLists(ListNode[] lists)
{
if (lists.Length == 0) return null;
var pq = new PriorityQueue<ListNode, int>();
foreach (var list in lists)
{
if (list != null)
pq.Enqueue(list, list.val);
}
var dummy = new ListNode();
var current = dummy;
while (pq.Count > 0)
{
var node = pq.Dequeue();
current.next = node;
current = current.next;
if (node.next != null)
pq.Enqueue(node.next, node.next.val);
}
return dummy.next;
}
/// <summary>
/// LRU 缓存
/// LeetCode 146
/// 时间 O(1)，空间 O(capacity)
/// </summary>
public class LRUCache
{
private readonly int _capacity;
private readonly Dictionary<int, LinkedListNode<CacheItem>> _cache;
private readonly LinkedList<CacheItem> _lruList;
public LRUCache(int capacity)
{
_capacity = capacity;
_cache = new Dictionary<int, LinkedListNode<CacheItem>>();
_lruList = new LinkedList<CacheItem>();
}
public int Get(int key)
{
if (!_cache.TryGetValue(key, out var node))
return -1;
// 移到最前面（最近使用）
_lruList.Remove(node);
_lruList.AddFirst(node);
return node.Value.Value;
}
public void Put(int key, int value)
{
if (_cache.TryGetValue(key, out var node))
{
node.Value.Value = value;
_lruList.Remove(node);
_lruList.AddFirst(node);
}
else
{
if (_cache.Count >= _capacity)
{
// 移除最久未使用
var last = _lruList.Last!;
_cache.Remove(last.Value.Key);
_lruList.RemoveLast();
}
var newNode = _lruList.AddFirst(new CacheItem(key, value));
_cache[key] = newNode;
}
}
}
private record CacheItem(int Key, int Value);
}图算法
经典题目
/// <summary>
/// 图算法经典题
/// </summary>
public class GraphPattern
{
/// <summary>
/// Dijkstra 最短路径
/// </summary>
public int[] Dijkstra(int[][] graph, int start)
{
int n = graph.Length;
var dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[start] = 0;
var pq = new PriorityQueue<int, int>();
pq.Enqueue(start, 0);
while (pq.Count > 0)
{
int u = pq.Dequeue();
for (int v = 0; v < n; v++)
{
if (graph[u][v] > 0)
{
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v])
{
dist[v] = newDist;
pq.Enqueue(v, newDist);
}
}
}
}
return dist;
}
/// <summary>
/// 课程表（拓扑排序）
/// LeetCode 207
/// </summary>
public bool CanFinish(int numCourses, int[][] prerequisites)
{
// 构建邻接表和入度数组
var graph = new List<int>[numCourses];
var inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++)
graph[i] = new List<int>();
foreach (var prereq in prerequisites)
{
graph[prereq[1]].Add(prereq[0]);
inDegree[prereq[0]]++;
}
// BFS 拓扑排序
var queue = new Queue<int>();
for (int i = 0; i < numCourses; i++)
{
if (inDegree[i] == 0)
queue.Enqueue(i);
}
int completed = 0;
while (queue.Count > 0)
{
int course = queue.Dequeue();
completed++;
foreach (int next in graph[course])
{
inDegree[next]--;
if (inDegree[next] == 0)
queue.Enqueue(next);
}
}
return completed == numCourses;
}
/// <summary>
/// 岛屿的最大面积
/// LeetCode 695
/// </summary>
public int MaxAreaOfIsland(int[][] grid)
{
int maxArea = 0;
int rows = grid.Length;
int cols = grid[0].Length;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (grid[i][j] == 1)
{
maxArea = Math.Max(maxArea, DfsArea(grid, i, j, rows, cols));
}
}
}
return maxArea;
}
private int DfsArea(int[][] grid, int r, int c, int rows, int cols)
{
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1)
return 0;
grid[r][c] = 0; // 标记已访问
return 1 + DfsArea(grid, r + 1, c, rows, cols)
+ DfsArea(grid, r - 1, c, rows, cols)
+ DfsArea(grid, r, c + 1, rows, cols)
+ DfsArea(grid, r, c - 1, rows, cols);
}
}字符串算法
经典题目
/// <summary>
/// 字符串算法
/// </summary>
public class StringPattern
{
/// <summary>
/// KMP 字符串匹配
/// LeetCode 28
/// 时间 O(n + m)
/// </summary>
public int StrStr(string haystack, string needle)
{
if (needle.Length == 0) return 0;
// 构建 next 数组（最长前缀后缀）
int[] next = BuildNext(needle);
int j = 0;
for (int i = 0; i < haystack.Length; i++)
{
while (j > 0 && haystack[i] != needle[j])
j = next[j - 1];
if (haystack[i] == needle[j])
j++;
if (j == needle.Length)
return i - j + 1;
}
return -1;
}
private int[] BuildNext(string pattern)
{
int[] next = new int[pattern.Length];
int j = 0;
for (int i = 1; i < pattern.Length; i++)
{
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];
if (pattern[i] == pattern[j])
j++;
next[i] = j;
}
return next;
}
/// <summary>
/// 最长回文子串
/// LeetCode 5
/// 中心扩展法：时间 O(n^2)，空间 O(1)
/// </summary>
public string LongestPalindrome(string s)
{
if (s.Length < 2) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < s.Length; i++)
{
// 奇数长度回文
Expand(s, i, i, ref start, ref maxLen);
// 偶数长度回文
Expand(s, i, i + 1, ref start, ref maxLen);
}
return s.Substring(start, maxLen);
}
private void Expand(string s, int left, int right, ref int start, ref int maxLen)
{
while (left >= 0 && right < s.Length && s[left] == s[right])
{
if (right - left + 1 > maxLen)
{
start = left;
maxLen = right - left + 1;
}
left--;
right++;
}
}
/// <summary>
/// 有效的括号
/// LeetCode 20
/// </summary>
public bool IsValid(string s)
{
var stack = new Stack<char>();
var pairs = new Dictionary<char, char>
{
{ ')', '(' }, { ']', '[' }, { '}', '{' }
};
foreach (char c in s)
{
if (pairs.ContainsValue(c))
{
stack.Push(c);
}
else if (pairs.ContainsKey(c))
{
if (stack.Count == 0 || stack.Pop() != pairs[c])
return false;
}
}
return stack.Count == 0;
}
}排序与复杂度分析
常见排序算法
/// <summary>
/// 常见排序算法实现
/// </summary>
public class SortingAlgorithms
{
/// <summary>
/// 快速排序
/// 平均 O(n log n)，最坏 O(n^2)，空间 O(log n)
/// </summary>
public static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
private static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] <= pivot)
{
i++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
}
/// <summary>
/// 归并排序
/// 稳定排序，时间 O(n log n)，空间 O(n)
/// </summary>
public static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
private static void Merge(int[] arr, int left, int mid, int right)
{
var temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
Array.Copy(temp, 0, arr, left, temp.Length);
}
/// <summary>
/// 堆排序
/// 时间 O(n log n)，空间 O(1)
/// </summary>
public static void HeapSort(int[] arr)
{
int n = arr.Length;
// 建堆
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
// 逐个提取最大值
for (int i = n - 1; i > 0; i--)
{
(arr[0], arr[i]) = (arr[i], arr[0]);
Heapify(arr, i, 0);
}
}
private static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i)
{
(arr[i], arr[largest]) = (arr[largest], arr[i]);
Heapify(arr, n, largest);
}
}
}
/// <summary>
/// 排序算法复杂度总结
/// </summary>
public class SortingComplexity
{
/// 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性
/// -----------|-------------|-------------|-----------|--------
/// 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定
/// 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定
/// 插入排序 | O(n^2) | O(n^2) | O(1) | 稳定
/// 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定
/// 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定
/// 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定
/// 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定
/// 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(n + k) | 稳定
}贪心算法
经典题目
/// <summary>
/// 贪心算法模式
/// 适用场景：局部最优推导全局最优
/// </summary>
public class GreedyPattern
{
/// <summary>
/// 跳跃游戏 II（最少跳跃次数）
/// LeetCode 45
/// </summary>
public int Jump(int[] nums)
{
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.Length - 1; i++)
{
farthest = Math.Max(farthest, i + nums[i]);
if (i == currentEnd)
{
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
/// <summary>
/// 区间调度（无重叠区间）
/// LeetCode 435
/// </summary>
public int EraseOverlapIntervals(int[][] intervals)
{
Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++)
{
if (intervals[i][0] >= end)
{
end = intervals[i][1];
}
else
{
count++; // 移除重叠区间
}
}
return count;
}
/// <summary>
/// 分发糖果
/// LeetCode 135
/// </summary>
public int Candy(int[] ratings)
{
int n = ratings.Length;
int[] candies = new int[n];
Array.Fill(candies, 1);
// 从左到右：右边比左边大，+1
for (int i = 1; i < n; i++)
{
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
}
// 从右到左：左边比右边大，取 max
for (int i = n - 2; i >= 0; i--)
{
if (ratings[i] > ratings[i + 1])
candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
}
return candies.Sum();
}
}解题策略总结
如何选择算法模式
1. 有序数组 + 查找/配对 → 双指针
2. 子串/子数组 + 连续区间 → 滑动窗口
3. 有序数据 + 搜索/答案 → 二分查找
4. 树/图 + 遍历/搜索 → BFS/DFS
5. 最优解 + 子问题重叠 → 动态规划
6. 局部最优 → 全局最优 → 贪心
7. 最近相关性/顺序 → 栈/队列
8. 字符串匹配 → KMP/Rabin-Karp关键知识点
- 双指针可以将 O(n^2) 降为 O(n)
- 滑动窗口的关键是维护窗口内状态的增减
- 二分查找的关键是确定搜索空间和收缩条件
- BFS 适合找最短路径，DFS 适合找所有解
- DP 的关键是定义状态和转移方程
- 排序算法的选择取决于数据特征和稳定性需求
- 贪心需要证明局部最优能推导全局最优
常见误区
| 误区 | 正确理解 |
|---|---|
| 背下代码就能解决所有题 | 理解模式原理，灵活变通 |
| DP 一定比暴力好 | 小规模数据暴力更简单 |
| 每道题都用最优解法 | 面试中先给出可工作的解法 |
| 复杂度分析不重要 | 复杂度分析展示你的工程素养 |
| 只刷高频题就够了 | 理解模式比刷题数量更重要 |
进阶路线
- 入门阶段：掌握基本数据结构和排序算法
- 进阶阶段：理解双指针、滑动窗口、二分查找模式
- 高级阶段：熟练运用 BFS/DFS、DP、图算法
- 专家阶段：能识别新题属于哪种模式，灵活组合
适用场景
- 技术面试准备
- 算法竞赛入门
- 数据结构课程复习
- 日常编码能力提升
落地建议
- 每天练习 1-2 题，按模式分类练习
- 先独立思考 20 分钟，再参考解法
- 对每道题分析时间和空间复杂度
- 使用 LeetCode 或牛客网在线练习
排错清单
复盘问题
- 你能快速识别一道新题属于哪种模式吗？
- 哪些算法模式是你最不熟悉的？如何加强？
- 面试中如何在有限时间内展示最佳解法？