当前位置： 首页 > news >正文

算法题遇到的技巧和心得

news 2026/5/25 2:02:13

IO，IO，IO

记录算法题遇到的技巧

（可以在评论区补充你的看法和技巧💕）

1.有效括号

1.左括号的数量 == 右括号的数量

2.从头开始的任意一个子串，左括号的数量 >= 右括号的数量

题目：22. 括号生成 - 力扣（LeetCode）

2.对字符处理的常用函数

C/C++中对字符处理的常用函数_c++关于字符的常用函数-CSDN博客

3.同余定理

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

4.常见位运算

  • 基础位运算

<< &&(有0就是0)

>> || (有1就是1)

~ ^ (相同为0，相异为1)（无进位相加）

  • 给一个数n，确定n的二进制表示中 x 位是 0 还是 1

操作： n & (1 << x)

x位是0，就返回0，是1，就返回1

  • 将一个数n的二进制表示中 x 位改成1

操作：n |= (1 << x)

  • 提取一个数n二进制最右侧的1

操作：n & -n

-n的本质：将最右侧的1的左边的区域全部变成相反

n: 0110101000

~n: 1001010111

+1:1001011000

-n :1001011000

对比n和-n可以发现-n的本质

所以可以把n二进制最右侧的1提取出来

  • 干掉一个数n二进制中最右侧的1

操作：n & (n - 1)

(n - 1)的本质：将最右侧的1右边的区域（包含1）全部变成相反

n：011010100

n - 1：011010011

&：011010000

  • 异或(^)运算

a ^ 0 = a

a ^ a = 0 (消消乐)

a ^ b ^ c = a ^ (b ^ c) （用无进位相加来理解）

5.向上取整

int ret = (count + k - 1) / k; // 计算用多少个k可以把count消除完

6.差分

  • 1.作用：快速解决“将某一个区间所有的元素统一加上一个数”的操作
  • 2.差分数组：f[i]表示：当前元素与前一个元素的差值
  • 3.性质：原数组[L，R]区间全部加上k这个操作，
  • 相当于在差分数组中，f[L] += k，f[R + 1] -= k(根据定义可证明)
  • 4.在初始化差分数组的时候可以直接用定义来初始化，因为相当于在a[i]这个位置上加上一个 数(k)，所以就可以用性质：f[L] += k，f[R + 1] -= k来初始化
  • 5.最后对差分数组用前缀和运算来还原（证明看下图）

7.二维差分

8.使用unordered_map的细节问题

https://www.doubao.com/thread/w9beaaab35d134907

9.lower_bound 和 upper_bound的使用：

【STL中的⼆分查找】

1. lower_bound ：大于等于x的最小元素，返回的是迭代器；时间复杂度： O(logN)。

2. upper_bound ：大于x的最小元素，返回的是迭代器。时间复杂度： O(logN) 。

二者均采用二分实现。但是STL中的二分查找只能适用于"在有序的数组中查找"，如果是二分答案就不能使用。

10.哈夫曼编码

11.正方形，已知相邻两点求下面两点

// 已知x1,y1 x2,y2两点 int x3 = x1 - (y2 - y1); int y3 = y1 + (x2 - x1); int x4 = x2 - (y2 - y1); int y4 = y2 + (x2 - x1);

https://www.doubao.com/thread/w070944115d11e5b1https://www.doubao.com/thread/w070944115d11e5b1

12.离散化

用sort排序，unique去重，lower_bound()查找下标，即可。

性质：升序。

情况：虽然区间长度很大，但是「区间 的个数」是很少的

对于区间问题，离散化会把区间缩短，为了避免出现这种情况，我们可以在离散化的区间[x,y]时，不仅考虑x,y这两个值，也把「x+1,y+1」也考虑进去。此时「单个区间内部」就出现空隙，「区间与区间之间」也会出现空隙。就可以避免这种情况出现。（此时的disc[N*4]）因为有两套（x,y,x + 1, y + 1）

13.8个方向

int dx[8] = {0, 0, 1, -1, 1, -1, -1, 1}; int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}; int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};

14.最短路问题

单源最短路

P3371 【模板】单源最短路径（弱化版） - 洛谷

迪杰斯特拉

时间复杂度：O(n^2 + m)

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e4 + 10; const int M = 5e5 + 10; const int INF = 2147483647; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; vector<PII> edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 for(int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; for(int i = 1; i < n; i++) { int u = 0; for(int j = 1; j <= n; j++) if(!st[j] && dist[j] < dist[u]) u = j; st[u] = true; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void solve() { cin >> n >> m >> s; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); } dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }

迪杰斯特拉（堆优化）

P4779 【模板】单源最短路径（标准版） - 洛谷

时间复杂度：O(m*logm)

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e5 + 10; const int M = 5e5 + 10; const int INF = 2147483647; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; vector<PII> edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 priority_queue<PII, vector<PII>, greater<PII>> heap; for(int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; heap.push({0, s}); while(heap.size()) { auto t = heap.top(); heap.pop(); int u = t.second; if(st[u]) continue; st[u] = true; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; heap.push({dist[v], v}); } } } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void solve() { cin >> n >> m >> s; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); } dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }

bellman-ford算法

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e4 + 10; const int M = 5e5 + 10; const int INF = 2147483647; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; int n, m, s; int dist[N]; bool st[N]; vector<PII> edges[M]; void dijkstra() { for(int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; for(int i = 1; i < n; i++) { int u = 0; for(int i = 1; i <= n; i++) if(!st[i] && dist[i] < dist[u]) u = i; st[u] = true; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } for(int i = 1; i <= n; i++) { cout << dist[i] << " "; } } void bf() { for(int i = 1; i <= n; i++) dist[i] = INF; dist[s] = 0; for(int i = 1; i < n; i++) { bool flag = 1; for(int u = 1; u <= n; u++) { if(dist[u] == INF) continue; for(auto e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { flag = 0; dist[v] = dist[u] + w; } } } if(flag) break; } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void solve() { cin >> n >> m >> s; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); } bf(); // dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }

spfa算法

0

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e4 + 10; const int M = 5e5 + 10; const int INF = 2147483647; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; vector<PII> edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 priority_queue<PII, vector<PII>, greater<PII>> heap; for(int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; heap.push({0, s}); while(heap.size()) { auto t = heap.top(); heap.pop(); int u = t.second; if(st[u]) continue; st[u] = true; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; heap.push({dist[v], v}); } } } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void bf() { for(int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; for(int i = 1; i < n; i++) { bool flag = 0; for(int u = 1; u <= n; u++) { if(dist[u] == INF) continue; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { flag = 1; dist[v] = dist[u] + w; } } } if(flag == 0) break; } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void spfa() { for(int i = 1; i <= n; i++) dist[i] = INF; dist[s] = 0; queue<int> q; q.push(s); st[s] = true; while(q.size()) { int u = q.front(); q.pop(); st[u] = false; for(auto e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if(!st[v]) { q.push(v); st[v] = true; } } } } for(int i = 1; i <= n; i++) cout << dist[i] << " "; } void solve() { cin >> n >> m >> s; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); } // dijkstra(); // bf(); spfa(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }

负环

P3385 【模板】负环 - 洛谷

BF算法判断负环：

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 2e3 + 10; const int M = 3e3 + 10; const int INF = 0x3f3f3f3f; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; vector<PII> edges[M]; int dist[N]; int st[N]; int n, m; //void bf() //{ // for(int i = 0; i <= n; i++) dist[i] = INF; // dist[s] = 0; // // for(int i = 1; i < n; i++) // { // bool flag = 0; // for(int u = 1; u <= n; u++) // { // if(dist[u] == INF) continue; // for(auto& e : edges[u]) // { // int v = e.first; // int w = e.second; // if(dist[u] + w < dist[v]) // { // flag = 1; // dist[v] = dist[u] + w; // } // } // } // if(flag == 0) break; // } // for(int i = 1; i <= n; i++) cout << dist[i] << " "; //} int s; bool bf() { // memset(dist, 0x3f, sizeof dist); for(int i = 0; i <= n; i++) dist[i] = INF; dist[1] = 0; bool flag; for(int i = 1; i <= n; i++) // 执行到n次，看第n次是否会松弛操作 { flag = false; for(int u = 1; u <= n; u++) { if(dist[u] == INF) continue; for(auto e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { flag = true; dist[v] = dist[u] + w; } } } if(flag == false) return flag; } return flag; } void solve() { for(int i = 1; i < M; i++) edges[i].clear(); cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); if(w >= 0) edges[v].push_back({u, w}); } // dijkstra(); // bf(); // spfa(); if(bf()) cout << "YES" << endl; else cout << "NO" << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; cin >> _; while(_--) { solve(); } return 0; }

spfa判断负环

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 2e3 + 10; const int M = 3e3 + 10; const int INF = 0x3f3f3f3f; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; vector<PII> edges[M]; int dist[N]; int st[N]; int n, m; int cnt[N]; bool spfa() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); memset(cnt, 0, sizeof cnt); dist[1] = 0; st[1] = true; queue<int> q; q.push(1); while(q.size()) { int u = q.front(); q.pop(); st[u] = false; for(auto& e : edges[u]) { int v = e.first; int w = e.second; if(dist[u] + w < dist[v]) { cnt[v] = cnt[u] + 1; if(cnt[v] > n) return true; dist[v] = dist[u] + w; if(!st[v]) { q.push(v); st[v] = true; } } } } return false; } void solve() { cin >> n >> m; for(int i = 1; i <= n; i++) edges[i].clear(); for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); if(w >= 0) edges[v].push_back({u, w}); } if(spfa()) cout << "YES" << endl; else cout << "NO" << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; cin >> _; while(_--) { solve(); } return 0; }

小总结：

多源最短路

模板题：

B3647 【模板】Floyd - 洛谷

代码：

#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 110; const int M = 4600; const int INF = 0x3f3f3f3f; using PII = pair<int, int>; using ull = unsigned long long; #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1}; ull base = 131; int f[N][N]; int n, m; void floyd() { for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cout << f[i][j] << " "; } cout << endl; } } void solve() { cin >> n >> m; memset(f, 0x3f, sizeof f); for(int i = 1; i <= n; i++) f[i][i] = 0; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; f[u][v] = f[v][u] = min(f[u][v], w); } floyd(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }

生成全排列


https://www.doubao.com/thread/w1445475a5d70c00e

https://www.doubao.com/thread/w4606a86ee3941e00

等差数量求和公式

http://www.jsqmd.com/news/857095/

相关文章：

  • 数据血缘是什么？一数据血缘、数据质量和数据地图的区别是什么？
  • 别再只仿真了！Simulink步进电机模型如何关联真实Arduino驱动器？
  • 《Windows Sysinternals实战指南》VMMap 学习笔记（8.8）：恢复默认视图、清理环境与分析后“归零”技巧
  • Thorium浏览器：基于Chromium的极致性能优化与隐私保护技术深度解析
  • 2026宜宾市叙州区黄金回收铂金回收白银回收深度实测 五大正规门店横屏 报价透明 免费上门才是真靠谱 - 亦辰小黄鸭
  • ARM GIC与Zynq中断架构详解：从通用原理到PL/PS实战配置
  • 避坑指南：ESP32-S3驱动ILI9488+LVGL时，GT911触摸屏方向与镜像问题的终极解决
  • ShizuTools LookBack功能剖析：无需卸载即可降级应用的原理与实现
  • 如何深度优化Wand应用体验：Wand-Enhancer配置增强实践指南
  • LVGL按钮(lv_btn)与开关(lv_switch)事件处理全解析：从点击检测到实现‘智能家居面板’
  • Omnizart完整功能清单：从人声旋律到鼓点节奏的一站式解决方案
  • Legacy iOS Kit：让旧iPhone重获新生的终极降级工具
  • FPGA驱动RGB屏幕时序详解：从VGA原理到480x272实战调试笔记
  • 词达人自动化助手终极指南：如何让英语学习效率提升10倍
  • 终极碧蓝航线自动化脚本：一键解放双手的完整解决方案
  • Show-o2 3D Causal VAE空间：为文本、图像和视频模态提供可扩展解决方案
  • PyTorch-FCN多数据集支持：NYUD深度信息与HHA特征融合技术
  • 如何高效管理百度网盘：BaiduPanFilesTransfers让你的文件批量操作变得简单
  • 抖音批量下载终极指南：5分钟搞定100个视频的完整教程
  • 2026 成都最新别墅装修推荐！优质公司榜单发布，靠谱 - 十大品牌榜
  • GetQzonehistory免费工具终极指南：5分钟备份你的QQ空间历史记录
  • cann/asc-devkit多核矩阵乘缓冲区计算
  • ScrollMonitor与React集成：如何快速构建响应式滚动交互的终极指南
  • 为什么顶尖实验室已禁用传统关键词搜索？——Perplexity生物知识图谱推理机制首次公开（含3个未公开API调用逻辑）
  • Python-json-logger错误排查指南：10个常见问题及解决方案
  • Java-多线程
  • 记录学习时光
  • 2026年5月国内云服务器选型实战指南：从2G建站到32G业务系统，100款配置横向对比
  • LinkSwift网盘直链下载助手：9大主流网盘高速下载终极解决方案
  • 从传感器噪声到清晰趋势：手把手教你用Python重现经典信号预处理案例（含代码避坑）