Terminus

原题链接 在算法题目中通常使用数组模拟链表，不使用 new 来初始化 Node 节点，因为数组模拟的速度非常快，new 操作很慢。 使用 e[i] ne[i] head idx 模拟的链表叫做静态链表。 使用 1234struct Node { int val; Node* next;}; 这样的结构体和 new 关键字创建的链表叫做动态链表。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>using namespace std;const int N = 100010;// e[i] 表示节点 i 的值// ne[i] 表示节点 i 的下一个节点标号是多少// head 表示头结点标号// idx 用于维护当前用到哪个了节点标号int e[N], ne[N], head, idx;void init() { head = -1; ...

原题链接 两个序列，使用两个指针，i j 指针都在两个序列开头。只要 a[i] 和 b[j] 不一样，就 j++，在 b 序列中找到第一个和 a[i] 一样的元素，找到后 i++，j++，考虑 a 序列中下一个元素是否在 b 序列中存在。 1234567891011121314151617181920212223242526272829#include <iostream>using namespace std;const int N = 1e5 + 10;int a[N], b[N];int n, m;int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } int ok = 1; for (int i = 0, j = 0; i < n; i++, j++ ...

原题链接 使用两个指针，i 指针放在 A 数组开头，j 指针放在 B 数组末尾，每次比较 A[i] + B[j] 与目标值的大小，如果大，就 j–，如果小就 i++。 1234567891011121314151617181920212223242526272829#include <iostream>using namespace std;const int N = 100010;int a[N];int b[N];int n,m,x;int main() { cin >> n >> m >> x; for(int i=0;i<n;i++) { cin >> a[i]; } for(int i=0;i<m;i++) { cin >> b[i]; } int i,j; for(i=0,j=m-1;i<n&&j>=0;) { if(a[ ...

在 linux 上设置定时任务 1$ crontab -e 每五分钟删除一次 docker 镜像 1*/5 * * * * docker image prune -f 每周日凌晨一点半删除一次 docker 镜像 15 * * * 0 docker image prune -f

原题链接 考察模运算公式： (a + b) % n = (a % n + b % n) % n; 123456789101112class Solution {public: vector<bool> prefixesDivBy5(vector<int>& A) { int x = 0; vector<bool> ans; for(int i=0;i<A.size();i++) { x = ((x<<1)+A[i])%5; ans.push_back(x==0); } return ans; }};

快速把 n 个有交集的区间合并，输出合并后的区间个数。 思路： 按区间左端点排序。 维护一个当前区间。遍历所有区间，动态更新当前区间左右端点的值。 12345678910111213141516171819202122232425262728293031323334353637#include <iostream>#include <algorithm>#include <vector>using namespace std;typedef pair<int,int> PII;const int N = 100010;int n;vector<PII> segs;void merge (vector<PII>& segs) { vector<PII> res; sort(segs.begin(), segs.end()); int st=-2e9, ed = -2e9; for(auto seg: segs) { if(ed<s ...

手写一个 unique 函数： 12345678910vector<int>::iterator unique(vector<int> a&) { int j = 0; for (int i = 0; i < a.size(); i++) { if (!i || a[i] != a[i - 1]) { a[j++] = a[i]; } } // a[0] ~ a[j-1] 是所有不重复的元素 return a.begin() + j;}

原题链接 并查集模板。 123456789101112131415161718192021222324252627282930class Solution {public: int Find(vector<int>& parent, int index) { if(parent[index]!=index) { return Find(parent, parent[index]); } return parent[index]; } void Union(vector<int>& parent, int index1, int index2) { parent[Find(parent, index1)] = Find(parent, index2); } vector<int> findRedundantConnection(vector<vector& ...

原题链接 双指针题目，测试用例会爆 int，所以需要转成 long long 进行计算。 1234567891011121314151617class Solution {public: vector<string> summaryRanges(vector<int>& nums) { if(nums.size() == 0) return {}; vector<string> res; for(int i=0, j=1;i<nums.size();i++) { while(j<nums.size()&&(long long)nums[j] - (long long)nums[j-1] == 1) j++; if((long long)nums[i]!=(long long)nums[j-1]) res.push_back(to_string(n ...

原题链接 这道题的思想非常巧妙，先将整个数组反转，然后反转 [0, k) 前 k 个数，再反转第 k 个数以后的数 [k, n)，就完成了数组元素整体右移 k 个位置。 12345678910class Solution {public: void rotate(vector<int>& nums, int k) { int n = nums.size(); k%=n; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin()+k, nums.end()); }};