衡水做网站电话,域名大全查询,网站整站出售,重庆网站建设公司 十年位运算 (Bit Manipulation)
位运算直接操作二进制位#xff0c;效率极高#xff0c;常用于实现哈希、状态压缩和整数的特殊计算。 核心思想: 异或 ^: 核心性质是 a ^ a 0 和 a ^ 0 a。这个“消消乐”的特性在寻找只出现一次或两次的数字时非常有效。与 : 常用于检查某…
位运算 (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 iostreamclass 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 vectorclass Solution {
public:std::string convert(std::string s, int numRows) {if (numRows 1) return s;std::vectorstd::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 ctimeclass Solution {
private:// 荷兰国旗问题三路快排的分割操作void qsort(std::vectorint 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::vectorint sortArray(std::vectorint nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}
};// int main() {
// Solution sol;
// std::vectorint nums {5, 1, 1, 2, 0, 0};
// std::vectorint 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 vectorclass Solution {
private:int mergeSort(std::vectorint nums, std::vectorint 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::vectorint nums) {if (nums.empty()) return 0;std::vectorint tmp(nums.size());return mergeSort(nums, tmp, 0, nums.size() - 1);}
};// int main() {
// Solution sol;
// std::vectorint 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 queueclass Solution {
public:int numIslands(std::vectorstd::vectorchar 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::vectorstd::vectorchar grid, int r, int c) {int m grid.size();int n grid[0].size();std::queuestd::pairint, int q;q.push({r, c});grid[r][c] 0; // Mark as visitedint 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::vectorstd::vectorchar 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_mapclass Solution {
public:std::vectorint twoSum(std::vectorint nums, int target) {std::unordered_mapint, int hash; // number, indexfor (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::vectorint nums {2, 7, 11, 15};
// std::vectorint result sol.twoSum(nums, 9);
// for (int i : result) {
// std::cout i ; // 输出: 0 1
// }
// std::cout std::endl;
// return 0;
// }
