位运算 (Bit Manipulation)
位运算直接操作二进制位，效率极高，常用于实现哈希、状态压缩和整数的特殊计算。
核心思想:
- 异或
^: 核心性质是a ^ a = 0和a ^ 0 = a。这个“消消乐”的特性在寻找只出现一次或两次的数字时非常有效。 - 与
&: 常用于检查某一位是否为1。例如，x & 1可以判断x的最低位。 - 位图: 用一个整数的每一位来表示一个元素是否存在。例如，一个
int(32位) 可以表示32个不同元素的存在状态，极大地节省了空间。
- 异或
经典应用场景:
-
判断字符唯一性
- 利用位图，将每个字符映射到一个比特位，如果某位已被设置，则说明字符重复。
-
寻找缺失数字
- 将
[0, n]的完整序列和残缺数组的所有数字进行异或操作，最终结果即为缺失的数字。
-
无加减法求和
- 使用
a ^ b计算无进位和，
(a & b) << 1计算进位，循环直至进位为0。
-
寻找出现特定次数的数字
- 统计所有数字在每一位上出现的总次数，对次数取模 (例如，出现3次的数字，我们就对3取模)，根据结果构建出那个特殊的数字。
经典例题：两整数之和 (LeetCode 371)
不使用 + 和 - 运算符，计算两个整数 a 和 b 的和。
C++
#include <iostream>
class Solution {
public:
int getSum(int a, int b) {
// 当进位为0时，循环终止
while (b != 0) {
// 无符号整型用于处理负数左移时可能产生的未定义行为
unsigned int carry = (unsigned int)(a & b) << 1;
// 计算无进位和
a = a ^ b;
// 更新进位
b = carry;
}
return a;
}
};
// int main() {
// Solution sol;
// std::cout << sol.getSum(2, 3) << std::endl; // 输出: 5
// return 0;
// }
模拟 (Simulation)
模拟题要求根据题意，将现实或抽象的过程用代码实现。这类问题通常不涉及复杂的算法，但对代码的实现能力和细节处理要求很高。
核心思想: 准确理解题目描述的每一个规则和约束，将过程分解为清晰的步骤，并用代码逻辑一一对应。
关键点
:
-
边界条件
- 充分考虑输入为空、长度为1等特殊情况。
状态变量: 使用合适的变量来跟踪过程中的状态变化（例如，行号、方向、计数器等）。
-
规律发现
- 对于看似复杂的模拟，尝试从小规模的例子入手，画图分析，寻找其中的周期性或数学规律，可以极大简化代码。
经典例题：N 字形变换 (LeetCode 6)
将一个字符串 s 按给定的行数 numRows 进行 Z 字形排列，然后按行读取输出。
C++
#include <iostream>
#include <string>
#include <vector>
class Solution {
public:
std::string convert(std::string s, int numRows) {
if (numRows == 1) return s;
std::vector<std::string> rows(std::min((int)s.length(), numRows));
int currentRow = 0;
bool goingDown = false;
for (char c : s) {
rows[currentRow] += c;
if (currentRow == 0 || currentRow == numRows - 1) {
goingDown = !goingDown;
}
currentRow += goingDown ? 1 : -1;
}
std::string result;
for (const std::string& row : rows) {
result += row;
}
return result;
}
};
// int main() {
// Solution sol;
// std::cout << sol.convert("PAYPALISHIRING", 3) << std::endl; // 输出: "PAHNAPLSIIGYIR"
// return 0;
// }
分治 (Divide and Conquer)
分治是一种将大问题分解为若干个规模更小但结构相同的子问题，递归地解决这些子问题，然后将子问题的解合并以得到原问题的解的策略。快速排序和归并排序是其经典应用。
1. 快速排序 (Quick Sort)
核心思想 (三路快排)
:
- Partition (分割): 选取一个基准元 (pivot)，通常随机选取以避免最坏情况。 将数组分为三部分：小于pivot、等于pivot、大于pivot。
- Recursion (递归): 对小于pivot和大于pivot的两部分递归地进行快速排序。
优点: 平均时间复杂度为 O(NlogN)，通常是实际应用中最快的内排序算法。
应用
:
- 排序数组: 完整的快排流程。
- 快速选择 (Quick Select): 查找第K大/小的元素。通过Partition操作后，可以判断第K个元素在哪一个分区，然后只对该分区进行递归，将平均时间复杂度降至 O(N)。
经典例题：排序数组 (LeetCode 912)
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
class Solution {
private:
// 荷兰国旗问题（三路快排）的分割操作
void qsort(std::vector<int>& nums, int l, int r) {
if (l >= r) return;
// 随机选择基准，避免最坏情况
int pivot = nums[l + rand() % (r - l + 1)];
int i = l, lt = l - 1, gt = r + 1;
while (i < gt) {
if (nums[i] < pivot) {
std::swap(nums[++lt], nums[i++]);
} else if (nums[i] > pivot) {
std::swap(nums[--gt], nums[i]);
} else {
i++;
}
}
qsort(nums, l, lt);
qsort(nums, gt, r);
}
public:
std::vector<int> sortArray(std::vector<int>& nums) {
srand(time(NULL));
qsort(nums, 0, nums.size() - 1);
return nums;
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {5, 1, 1, 2, 0, 0};
// std::vector<int> sorted = sol.sortArray(nums);
// for (int num : sorted) {
// std::cout << num << " "; // 输出: 0 0 1 1 2 5
// }
// std::cout << std::endl;
// return 0;
// }
2. 归并排序 (Merge Sort)
核心思想
:
-
Divide (分)
- 总是从中间将数组分成两半，直到每个子数组只有一个元素。
-
Conquer (治)
- 将两个已排序的子数组合并 (Merge) 成一个更大的有序数组。
优点: 时间复杂度稳定为 O(NlogN)，是一种稳定的排序算法。
应用
:
-
求逆序对
- 在合并两个有序子数组时，可以高效地统计逆序对的数量。当左子数组的元素
nums[i]大于右子数组的元素
nums[j]时，
nums[i]与右子数组中从
j到末尾的所有元素都构成逆序对。
经典例题：数组中的逆序对 (剑指 Offer 51)
C++
#include <iostream>
#include <vector>
class Solution {
private:
int mergeSort(std::vector<int>& nums, std::vector<int>& tmp, int l, int r) {
if (l >= r) {
return 0;
}
int mid = l + (r - l) / 2;
int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
int i = l, j = mid + 1, pos = l;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[pos++] = nums[i++];
} else {
tmp[pos++] = nums[j++];
inv_count += (mid - i + 1);
}
}
while (i <= mid) tmp[pos++] = nums[i++];
while (j <= r) tmp[pos++] = nums[j++];
std::copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
return inv_count;
}
public:
int reversePairs(std::vector<int>& nums) {
if (nums.empty()) return 0;
std::vector<int> tmp(nums.size());
return mergeSort(nums, tmp, 0, nums.size() - 1);
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {7, 5, 6, 4};
// std::cout << sol.reversePairs(nums) << std::endl; // 输出: 5
// return 0;
// }
广度优先搜索 (BFS)
BFS 是一种图遍历算法，从一个起点开始，逐层向外探索。它非常适合解决最短路径问题（在边权为1的图中）。
核心数据结构: 队列 (Queue)。
算法流程
:
- 将起点加入队列，并标记为已访问。
- 当队列不为空时，取出队头节点。
- 将其所有未被访问的邻居节点加入队列，并标记为已访问。
- 重复此过程，直到队列为空。
应用
:
-
层序遍历
- 按层遍历树或图。
-
最短路径
- 在无权图中，第一次到达目标节点时所经过的层数即为最短路径长度。
-
多源BFS
- 将所有源点同时入队，可以同时开始搜索，常用于求解所有点到最近源点的距离。
-
拓扑排序
- 用于检测有向无环图 (DAG) 中的依赖关系。首先将所有入度为0的节点入队，然后不断取出节点，并将其邻居节点的入度减1，若邻居入度变为0则入队。
经典例题：岛屿数量 (LeetCode 200)
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。
C++
#include <iostream>
#include <vector>
#include <queue>
class Solution {
public:
int numIslands(std::vector<std::vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) {
return 0;
}
int m = grid.size();
int n = grid[0].size();
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
count++;
bfs(grid, i, j);
}
}
}
return count;
}
private:
void bfs(std::vector<std::vector<char>>& grid, int r, int c) {
int m = grid.size();
int n = grid[0].size();
std::queue<std::pair<int, int>> q;
q.push({r, c});
grid[r][c] = '0'; // Mark as visited
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [currentRow, currentCol] = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int newRow = currentRow + dr[i];
int newCol = currentCol + dc[i];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == '1') {
q.push({newRow, newCol});
grid[newRow][newCol] = '0'; // Mark as visited
}
}
}
}
};
// int main() {
// Solution sol;
// std::vector<std::vector<char>> grid = {
// {'1','1','0','0','0'},
// {'1','1','0','0','0'},
// {'0','0','1','0','0'},
// {'0','0','0','1','1'}
// };
// std::cout << sol.numIslands(grid) << std::endl; // 输出: 3
// return 0;
// }
栈 (Stack) 与 哈希表 (Hash Table)
-
栈 (Stack)
- 一种后进先出 (LIFO) 的数据结构，非常适合处理具有递归结构或需要“撤销”操作的问题，如括号匹配、退格符处理等。
-
哈希表 (Hash Table)
- 提供平均
O(1)
时间复杂度的插入和查找操作，是“用空间换时间”策略的典范。
适用于需要快速查找元素是否存在或映射关系的场景。
-
组合使用
- 两者结合可以解决更复杂的问题。例如，在处理嵌套结构（如字符串解码）时，可以用栈来保存外层的状态（数字和字符串），在内层解码完成后再恢复。
经典例题：两数之和 (LeetCode 1)
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
C++
#include <iostream>
#include <vector>
#include <unordered_map>
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> hash; // <number, index>
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
if (hash.count(complement)) {
return {hash[complement], i};
}
hash[nums[i]] = i;
}
return {}; // No solution found
}
};
// int main() {
// Solution sol;
// std::vector<int> nums = {2, 7, 11, 15};
// std::vector<int> result = sol.twoSum(nums, 9);
// for (int i : result) {
// std::cout << i << " "; // 输出: 0 1
// }
// std::cout << std::endl;
// return 0;
// }