C++算法笔记

基础语法与环境配置

万能竞赛模板

• ​x
  1
  #include<bits/stdc++.h>         // 万能头文件
  2
  using namespace std;
  3
  
  4
  #define endl '\n'
  5
  #define int long long           // 简化long long 数据类型的声明          
  6
  const int MOD=998244353;        // 取模值(质数),也有1e9+7  
  7
  
  8
  void solve(){}                  // 实际解决方案
  9
  
  10
  signed main(){
  11
      
  12
      ios::sync_with_stdio(false); // 加速外挂
  13
      cin.tie(nullptr);           // endl换为 '\n'
  14
      
  15
      int T=1;
  16
      cin>>T;                     // 测试案例个数
  17
      while(T--)solve();
  18
      return 0;
  19
  }
  

   

输入输出基础

• 浮点数控制: cout<<fixed<<setprecision(n);

• 整行读入: getline(cin,str);

• 自定义分隔符: getline(cin,str,',')

• 符合ACM的输出格式, 元素间空格,元素末尾换行

  xxxxxxxxxx
  3
  1
  for (int i = 0; i < n; i++){
  2
      cout << a[i] << " \n"[i == n - 1];
  3
  }
  

常见存储思维转换:

• 题设与矩阵相关,各行输入的元素间连续(同一行内每个元素间无空格),则优先以vector<string>v存储01回文

• 需要打表存储固定数据时,可压缩存储为0/1矩阵,输出可考虑""YN"[条件]来简化A+B Problem|01矩阵

• 1s大概${10}^8$$10^8$循环量,数据量较大的容器遍历可能超时,数据随机可以尝试暴力求解,找到结果后立即推出玄幻

数据类型转换与判断

• 当操作数类型为long long时,直接使用的常数优先加LL后缀来声明类型,否则溢出.例: long long t = 1<<big_num会溢出,需要改为ll t = 1LL<<big_num

• 当操作数的范围接近${10}^9$$10^9$时,对其进行和积运算的结果用长整型来存储

数学函数

常用内置函数

• abs(). sqrt().

• round():四舍五入化为整数,floor()向下取整,ceil()向上取整

• min(a,b) , max({a,b,c}):多个数找最值

• hypot(dx, dy)：直接计算 $\sqrt{d{x}^2+d{y}^2}$$\sqrt{dx^2 + dy^2}$，防止溢出。

• gcd(a, b) / lcm(a, b)：最大公约数与最小公倍数。

• __lg(x) 返回的是 $x$$x$ 的二进制表示中，最高位 1 所在的位置（从 0 开始计数）

模板函数

1. is_prime ( 素数 )

   xxxxxxxxxx
   32
   1
   // 版本一:判断是否为素数
   2
   vector<bool> isPrime(n, true);
   3
   void Prime(){
   4
       // 素数筛选法
   5
       for (int i = 2; i * i < MAX_N; i++) {s
   6
           if (isPrime[i]) {
   7
               for (int j = i * i; j < MAX_N; j += i) {
   8
                   isPrime[j] = false;
   9
               }
   10
           }
   11
       }
   12
   }
   13
   
   14
   // 版本二
   15
   const int N = 1e8 + 10;
   16
   bitset<N> isNotPrime; // 0 为素数，1 为非素数
   17
   vector<int> primeList;// 记录前n个素数
   18
   
   19
   void initPrime()
   20
   {
   21
       // 素数筛选法
   22
       isNotPrime[0] = isNotPrime[1] = 1;
   23
       for (int i = 2; i < N; i++){
   24
           if (!isNotPrime[i]) primeList.push_back(i);
   25
           if (primeList.size() >= n) break;// 只需要n个素数列表,提前返回
   26
           for (int p : primeList){
   27
               if (i * p >= 1e8) break;// 防止越界访问 bitset
   28
               isNotPrime[i * p] = 1;
   29
               if (i % p == 0) break;// 线性筛精髓：保证每个合数只被筛一次
   30
           }
   31
       }
   32
   }
   

2. Factorial ( 阶乘 )

   xxxxxxxxxx
   6
   1
   vector<long long> fact(MAX_N,1);// 太大的空间开不出来,数组大小需要控制
   2
   void Factorial(){// 预处理操作,直接以数组形式调用
   3
       for (int i = 1; i < MAX_N; i++){
   4
           fact[i] = (fact[i - 1] * i) % MOD;
   5
       }
   6
   }
   

3. GCD,LCM ( 辗转相除法 )

   xxxxxxxxxx
   18
   1
   // 递归版
   2
   long long gcd(long long a, long long b) {
   3
       return b == 0 ? a : gcd(b, a % b);
   4
   }
   5
   // 非递归版：避免栈溢出（处理极大数字时）
   6
   long long gcd_iter(long long a, long long b) {
   7
       while (b) {
   8
           a %= b;
   9
           swap(a, b);
   10
       }
   11
       return a;
   12
   }
   13
   
   14
   long long lcm(long long a, long long b) {
   15
       if (a == 0 || b == 0) return 0;
   16
       // 注意：先除后乘可以防止 a * b 直接相乘导致的溢出
   17
       return (a / gcd(a, b)) * b;
   18
   }
   

4. ($A^B)\mathrm{\%}MOD$$A^B) \% MOD$​ ( 快速幂 )

   xxxxxxxxxx
   21
   1
   // MOD一般在全局定义
   2
   // 迭代写法
   3
   long long qpow(int a, int b){
   4
       long long res = 1;
   5
       a%=MOD; // 防止 a过大,直接对其取模
   6
       while (b > 0){
   7
           if (b & 1)res = res * a % MOD;  // 二进制最后一位为 1的情况
   8
           a = a * a % MOD;    // 底数进行平方
   9
           b >>= 1;    // 幂次减半
   10
       }
   11
       return res;
   12
   }
   13
   
   14
   // 递归写法
   15
   long long qpow(int a, int b){
   16
       if (b == 1)return a;
   17
       long long res = modpow(a, b >> 1);
   18
       res = res * res % MOD;
   19
       if (b & 1)return a * res % MOD;
   20
       return res;
   21
   }
   

技巧结论

1. 分数计算 $H(n)=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$H(n)=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$​

   xxxxxxxxxx
   1
   1
   sum += (1.0 / i);   // 用 1.0进行除法,强制转化为浮点运算
   

2. 约瑟夫环 (如:星期1~7循环).

   xxxxxxxxxx
   3
   1
   (index+Δstep)%n;            // 顺时针循环
   2
   (index-Δstep%n+n)%n;        // 逆时针循环
   3
   
   

   • 当多次循环处理结果不受循环次数影响时,可以进行2*n次循环来处理

     for (int i = 0; i < nums.size() * 2; i++) {}

3. 两点间距 $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$\sqrt {(x_1-x_2)^2+(y_1-y_2)^2}$​

   xxxxxxxxxx
   1
   1
   hypot(x1-x2,y1-y2);     // 返回两点间距
   

4. 取模运算

   xxxxxxxxxx
   9
   1
   (a+b)%MOD = a%MOD + b%MOD;  // 满足结合律
   2
   (a*b)%MOD = a%MOD * b%MOD;
   3
   
   4
   (a-b)%MOD = (a%MOD - b%MOD + MOD)%MOD;  // 不允许有负数
   5
   
   6
   // 费马小定理: 求a在模p下的乘法逆元
   7
   long long inv(long long a){ // MOD在全局定义
   8
       return modpow(a,MOD-2);
   9
   }
   

5. 三角形面积

   • 根据几何坐标(向量叉乘): $Area=\frac{1}{2}|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|$$Area=\frac{1}{2}|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|$,本质为$|\overrightarrow{OA}\times \overrightarrow{OB}|$$|\overrightarrow{OA}\times\overrightarrow{OB}|$

   • 根据边长长度(海伦公式): $Area=\sqrt{s(s-a)(s-b)(s-c)},s=\frac{a+b+c}{2}$$Area=\sqrt{s(s-a)(s-b)(s-c)}, s=\frac{a+b+c}{2}$

6. 周期性边界处理

   • "轮流操作": 利用数学偏移思想,计算周期结束前的最后一步, 而不是下一个周期的第零步小L的游戏

位运算

• 运算符号

• 运算结论

名词解释 ( 不完全中肯 )

1. 乘法逆元 : 根据费马小定理，在模数 m 为质数，且 b 不是 m的倍数的情况下有：$\frac{a}{b}\mathrm{mod}MOD=a\times (b^{MOD-2})\mathrm{mod}MOD$$\frac{a}{b}\mathrm{~mod~}MOD=a\times(b^{MOD-2})\mathrm{~mod~}MOD$​

2. 长度为 n 的排列：由 $1,2,\dots ,n$$1,2,…,n$​ 这 n 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，{2,3,1,5,4}是一个长度为 5 的排列，而 {1,2,2}和 {1,3,4}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

3. MEX: MEX 定义为没有出现在集合中的最小非负整数。例如，$MEX(1,2,3)=0、MEX(0,2,5)=1$$MEX⁡(1,2,3)=0、MEX(0,2,5)=1$。

4. 数组的字典序比较: 从左到右逐个比较两个数组的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素小的数组字典序也小。如果一直比较到其中一个数组结束，则长度较短的数组字典序更小。例如, {2,3,4,5} 的字典序小于 {2,4,3,5},也小于 {3,2,4,5}

5. 连通块: 在网格中，若两个坐标间的曼哈顿距离为 1 则视为相邻。由数值相等的格子按该相邻关系划分的极大连通子集称为一个连通块。对于网格中的两个点$(x_1,x_2)$$(x_1,x_2)$和$(x_2,y_2)$$(x_2,y_2)$, 其曼哈顿距离为$|x_1-x_2|+|y_1-y_2|$$|x_1-x_2|+|y_1-y_2|$

6. 子序列: 从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。例: {1,2,3,4,5}的子序列之一可以是 {2,5}

进阶语法

• Lambda 表达式 auto 函数名 = [捕获列表](参数列表) -> 返回类型 { 函数体 };

  • [ 捕获列表 ]中,填&可以引用捕获外边的变量,同时避免容器的拷贝

  • ( 参数列表 )中,一般为(const vector<T>& 容器名)避免大量拷贝导致TLE

  xxxxxxxxxx
  14
  1
  // 场景1: 自定义排序规则
  2
  sort(v.begin(),v.end(),[](int a,int b){
  3
      return a > b;// 降序排列,但不推荐
  4
  })
  5
  
  6
  // 场景2: 可高效处理的内部函数, 多次执行同一逻辑
  7
  auto func = [&](const vector<long long>& vec, ...) {
  8
      long long ans = 0;
  9
     ...
  10
      return ans;
  11
  };
  12
  
  13
  // 场景3: 优先队列自定义规则,关键字decltype
  14
  priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
  

   

STL容器

迭代器

• xxxxxxxxxx
  10
  1
  auto itA=v.begin(); // 指向容器第一个元素,*it表示实际存储的值
  2
  auto itB=v.end(); //指向最后一个元素的下一个位置,*it报错
  3
  for(auto it=v.begin();it!=v.end();it++);// 遍历
  4
  
  5
  auto itA=v.rbegin(); // 指向容器最后一个元素
  6
  auto itB=v.rend(); //指向第一个元素的前一个位置
  7
  for(auto it=v.rbegin();it!=v.rend();it++);// 逆序遍历
  8
  
  9
  min_element(v.begin(),v.end()); // 返回指向最小值的迭代器,本质是O(n)的遍历
  10
  max_element(v.begin(),v.end()); // *max_element得到具体值
  

algorithm

• sort ( 排序 )

  xxxxxxxxxx
  7
  1
  sort(v.begin(),v.end()); // 升序排序
  2
      sort(v.begin(),v.end(),greater<T>); // 降序排序,不推荐
  3
  sort(v.rbegin(),v.rend());//效率高,推荐使用
  4
  
  5
  sort(v.begin(), v.end(), [](int a, int b) {
  6
          return a > b;
  7
      }); // 自定义排序
  

   

• merge ( 合并 )

  xxxxxxxxxx
  3
  1
  //merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  2
  merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin()); // 合并两个序列
  3
  
  

• accumulate ( 累加和 )

  xxxxxxxxxx
  3
  1
  //accumulate(iterator beg, iterator end, value);
  2
  int total = accumulate(v.begin(), v.end(), 0);// 计算容器元素累计总和
  3
  
  

• fill ( 填充 )

  xxxxxxxxxx
  2
  1
  //fill(iterator beg, iterator end, value);
  2
  fill(v.begin(), v.end(), val);//容器区间内元素填充为指定的值
  

• count ( 计数 )

  xxxxxxxxxx
  2
  1
  // count(iterator beg, iterator end, value), 返回值为整数
  2
  int numX=count(v.begin(),v.end(),x);// 统计容器区间内值为 x的个数
  

   

string

增删改查

• xxxxxxxxxx
  5
  1
  strA+=strB;     // 尾部拼接
  2
  str.insert(index,"A");  //指定索引index位置插入字符"A"
  3
  
  4
  auto pos=str.find("abc");   // 查找str是否包含子串,pos为size_t类型,直接输出则为索引
  5
  if(pos!=string::npos){} // 表示查找成功的情况
  

reverse ( 反转字符串 )

• xxxxxxxxxx
  1
  1
  reverse(str.begin(),str.end()); // 无返回值
  

replace ( 替换字符 )

• xxxxxxxxxx
  1
  1
  replace(str.begin(),str.end(),'A','B'); // 将所有'A'替换为'B', 无返回值
  

transform ( 转换大小写 )

• xxxxxxxxxx
  2
  1
  transform(s.begin(), s.end(), s.begin(), ::tolower);// 全部转为小写字符
  2
  transform(s.begin(), s.end(), s.begin(), ::tolower);// 全部转为大写字符
  

substr ( 分割子串 )

• xxxxxxxxxx
  2
  1
  // substr(起始索引, 字符个数)
  2
  string t=str.substr(0,2); // 从索引0位置开始分割str的两个字符
  

remove+erase ( 去除所有空格 )

• xxxxxxxxxx
  4
  1
  str.erase(remove(str.begin(),str.end(),' '),str.end());
  2
  
  3
  auto new_end=remove(str.begin(), str.end(), ' ');   // 将所有非空格字符覆盖到容器前面，保持相对顺序,返回的迭代器指向新范围的末尾（第一个被"移除"的空格的位置）
  4
  str.erase(new_end, str.end());  // 从 new_end 到容器末尾的所有元素进行真正的删除
  

vector ( 动态数组 )

一维动态数组声明

• xxxxxxxxxx
  3
  1
  vector<T>v; // 只声明, 不开辟空间, 后续用v.push_back()插入
  2
  vector<T>v(n);  // 开辟大小为n的空间并初始化为0,可直接用v[i] 
  3
  vector<T>v(str.begin(),str.end());  // 用字符串进行拷贝构造
  

增删

• xxxxxxxxxx
  7
  1
  v.push_back(ele);   // 在数组末尾增添元素ele
  2
  v.emplace_back(ele); // 末尾增添元素,可节省调用构造函数的时间,支持多参数
  3
  v.pop_back();   // 删除最后一个元素
  4
  
  5
  v.insert(iterator,ele); // 在迭代器it位置插入元素ele
  6
  v.erase(iterator);  //删除迭代器it位置的元素
  7
  v.erase(iteratorA,iteratorB);   // 删除迭代器itA~itB之间的元素
  

查找

• xxxxxxxxxx
  5
  1
  v.empty();  // 判断是否为空
  2
  v.size();   // 返回元素个数
  3
  
  4
  v.begin();  // 返回首元素的值
  5
  v.back();   // 返回尾元素的值
  

stack (栈)

• xxxxxxxxxx
  8
  1
  stack<T> stk;   // 声明容器
  2
  
  3
  stk.push(val);  // 向栈顶添加元素val
  4
  stk.pop();  // 从栈顶移除第一个元素
  5
  stk.top();  // 返回栈顶元素
  6
  
  7
  stk.empty();    // 判断栈是否为空
  8
  stk.size();     // 返回栈的大小
  

• 习题集

  • 验证栈序列

queue (队列)

• xxxxxxxxxx
  9
  1
  queue<T> que;   // 声明容器
  2
  
  3
  que.push(val);  // 往队尾添加元素val
  4
  que.pop();  // 从队头移除第一个元素
  5
  que.front();    // 返回队首元素
  6
  que.back();     // 返回队尾元素
  7
  
  8
  que.empty();    // 判断队列是否为空
  9
  que.size();     // 返回队列的大小
  

•  

list (双向链表)

• 适用条件: 保留插入顺序,支持拼接

• xxxxxxxxxx
  15
  1
  list<T> lt;
  2
  
  3
  lt.push_front(val); // 在容器开头插入一个元素
  4
  lt.push_back(val);  // 在容器尾部加入一个元素
  5
  
  6
  lt.pop_front(); // 从容器开头移除第一个元素
  7
  lt.pop_back();  // 删除容器中最后一个元素
  8
  
  9
  lt.insert(pos,lt.begin(),ls.end());//在pos位置插入[beg,end)区间的数据，无返回值。
  10
  lt.erase(lt.begin(),lt.end());//删除[beg,end)区间的数据，返回下一个数据的位置。
  11
  lt.erase(it);//删除迭代器it所指位置的值，返回下一个数据的位置。
  12
  lt.remove(val);//删除容器中所有与val值匹配的元素。
  13
  
  14
  lt.front(); // 返回首元素的值
  15
  lt.back();  // 返回尾元素
  

• 反转和排序

• xxxxxxxxxx
  5
  1
  lt.sort(); // 默认的排序规则从小到大
  2
  lt.sort(greater<T>()); // 降序
  3
  lt.sort(cmp);   // 自定义
  4
  
  5
  lt.reverse();
  

priority_queue (优先队列)

• 声明

  xxxxxxxxxx
  5
  1
  priority_queue<T>pq;    // 大根堆,最大值先出队
  2
  priority_queue<T, vector<T>, greater<T> > pq; // 小根堆,最小值先出队
  3
  priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);    // 自定义
  4
  
  5
  auto cmp = [](int a, int b) { return 表达式(例:a > b); };
  

• 两端优先队列考虑使用 multiset

set (集合)

set ( 所有元素在插入时自动被排序 )

• 键值对声明

• xxxxxxxxxx
  5
  1
  set<T>st;   // 默认构造声明
  2
  set<T,greater<T1> >st;  // 元素降序排序
  3
  set<T,decltype(cmp)> st(cmp);   // 自定义排序规则
  4
  
  5
  auto cmp=[](T1 a,T2 b){retrun 表达式(例: a>b );} // 自定义
  

• 基本操作

• xxxxxxxxxx
  10
  1
  st.size();  // 返回元素个数(去重后)
  2
  st.empty(); // 判断是否为空,返回值bool
  3
  
  4
  st.insert(ele); // 插入元素ele
  5
  st.insert(ele).second // 返回bool值,插入成功为true, 已有元素ele则返回false
  6
  st.erase(ele);  // 删除元素ele
  7
  st.erase(it);   // 删除迭代器it所在指向位置的值
  8
  
  9
  st.count(ele);  // 返回值为ele的个数
  10
  st,find(ele);   // 查找元素ele是否存在,存在则返回it,否则返回st.end()
  

   

multiset ( 允许容器中有重复的元素 )

• xxxxxxxxxx
  20
  1
  mset.erase(val); // 删掉所有为val的值
  2
  
  3
  mset.erase(mset.rbegin());  // 删掉最大值(默认)
  4
  ms.erase(prev(ms.end()));   // 同理
  5
  ms.erase(--ms.end());       // 同上
  6
  
  7
  mset.erase(mset.begin());   // 删掉最小值(默认)
  8
  
  9
  
  10
  int getPre(int x){  //TODO 实现找前驱
  11
      auto it = mset.lower_bound(x);// 找到第一个> =x 的元素
  12
      if(it == mset.begin()) return -1;   
  13
      else return *prev(it);// 找到第一个> =x 的元素,prev()返回it的前一个迭代器,也可以用*(--it),返回第一个比x小的数
  14
  }
  15
  
  16
  int getBack(int x){ //TODO 实现找后继
  17
      auto it = mset.upper_bound(x);// 找到第一个 >x 的元素
  18
      if(it == M.end()) return -1;
  19
      else return *it;
  20
  }
  

unordered_set ( 仅用来去重 )

map (键值对)

map ( 用于key需要排序的情况 )

• 键值对声明

• xxxxxxxxxx
  5
  1
  map<T1,T2>mp;   // 一般声明,keys升序排序
  2
  map<T1,T2,greater<T1> >mp;  // keys降序排序
  3
  map<T1,T2,decltype(cmp)> mp(cmp);   // 自定义排序规则
  4
  
  5
  auto cmp=[](T1 a,T2 b){retrun 表达式(例: a>b );} // 自定义
  

• 基本操作

• xxxxxxxxxx
  15
  1
  mp.size();  //返回keys元素的数目
  2
  mp.empty(); //判断是否为空,返回值bool
  3
  
  4
  mp[key]=value;  // 插入键值对{key:val}
  5
  mp.erase(key);  // 删除map中键为key的键值对
  6
  
  7
  mp.count(key);  // 统计key元素的个数
  8
  mp.find(key);   // 查找key是否存在,存在则返回it,否则返回mp.end()
  9
  
  10
  for(auto it = mp.begin();it != mp.end();it++){
  11
  if(mp.find(key)==mp.end()){}    // 未查找到元素的情况
  12
  cout << "key:"<<it->first;      // 访问用it->first为键key,it->second为值val
  13
  cout <<"value:"<< it->second;
  14
  }
  15
  
  

   

multimap ( 用于键key可重复的情况 )

unordered_map ( 不需要排序, 性能最好, 最常用 )

基础算法

二分法

利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止

• 二分查找目标元素target索引

• xxxxxxxxxx
  17
  1
  /* 二分查找目标元素（左闭右开区间） */
  2
  int binarySearchLCRO(vector<int> &nums, int target) {// nums必须有序
  3
      // 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
  4
      int i = 0, j = nums.size();
  5
      // 循环，当搜索区间为空时跳出（当 i = j 时为空）
  6
      while (i < j) {
  7
          int m = i + (j - i) / 2; // 计算中点索引 m, 防止溢出
  8
          if (nums[m] < target)    // 此情况说明 target 在区间 [m+1, j) 中
  9
              i = m + 1;
  10
          else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
  11
              j = m;
  12
          else // 找到目标元素，返回其索引
  13
              return m;
  14
      }
  15
      // 未找到目标元素，返回 -1
  16
      return -1;
  17
  }
  

• 二分查找插入点 ( 存在重复元素 )

• xxxxxxxxxx
  16
  1
  /* 二分查找插入点（左闭右开区间） */
  2
  int binarySearchInsertion(vector<int> &nums, int target) {
  3
      int i = 0, j = nums.size(); // 初始化左闭右开区间 [0, n)
  4
      while (i < j) {             // 当 i == j 时，区间为空，循环结束
  5
          int m = i + (j - i) / 2; // 计算中点索引 m
  6
          if (nums[m] < target) {
  7
              i = m + 1;           // target 在区间 [m+1, j) 中
  8
          } else if (nums[m] > target) {
  9
              j = m;              // target 在区间 [i, m) 中, 可与else直接合并
  10
          } else {
  11
              j = m;    // 关键点：为了找到最左侧插入点，即便相等也收缩右边界
  12
          }
  13
      }
  14
      // 返回插入点 i (此时 i == j)
  15
      return i;
  16
  }
  

• 哈希查找, 利用键值对 { 元素,索引 }来记录位置,本质是借助计数排序的思想

• xxxxxxxxxx
  17
  1
  // 预处理：空间 O(n)，时间 O(n)
  2
  unordered_map<int, int> setupHash(vector<int> &nums) {
  3
      unordered_map<int, int> dic;
  4
      // 倒序遍历，确保记录的是相同元素的第一个（最左侧）索引
  5
      for (int i = nums.size() - 1; i >= 0; i--) {
  6
          dic[nums[i]] = i;
  7
      }
  8
      return dic;
  9
  }
  10
  
  11
  // 查找：时间 O(1)
  12
  int findTarget(unordered_map<int, int> &dic, int target) {
  13
      if (dic.find(target) != dic.end()) {
  14
          return dic[target];
  15
      }
  16
      return -1; // 如果不存在，哈希表无法直接给出“插入点”
  17
  }
  

前缀和/差分

• 一维前缀和

  • 通过 O(n）时间预处理，能够将单次复杂度降低到 O(1）

  • 对于数组 $a_n$$a_n$ ,序列的前缀和为$S_i=\sum _{j=1}^i{a}_j$$S_i=\sum_{j=1}^{i}a_j$ ,递推关系式为$S_0=0,S_i=S_{i-1}+a_i$$S_0=0,S_i=S_{i-1}+a_i$​

  • 想要询问区间 [l,r]内的序列和,只需要计算差值$S([l,r])=S_r-S_{l-1}$$S([l,r])=S_r-S_{l-1}$​

• xxxxxxxxxx
  16
  1
  int n;                // 数组大小.
  2
  std::vector<int> a;   // 数组. (下标从 1 开始)
  3
  std::vector<int> prefix;  // 前缀和数组.
  4
  
  5
  // 计算前缀和
  6
  void prefix_sum() {
  7
    prefix = a;
  8
    for (int i = 1; i <= n; ++i) {
  9
      prefix[i] += prefix[i - 1];
  10
    }
  11
    // Or 简化:
  12
    // std::partial_sum(a.begin(), a.end(), ps.begin());
  13
  }
  14
  
  15
  // 查询 [l, r] 区间内的元素的和
  16
  int query(int l, int r) { return prefix[r] - prefix[l - 1]; }
  

• 二维前缀和

  • 给定大小为 $m\times n$$m\times n$的二维数组 A,求出其前缀和 S,则S的大小同样为 $m\times n$$m\times n$ 且$S_{i,j}=\sum _{i^{\prime }\le i}\sum _{j^{\prime }\le j}{A}_{i^{\prime },j^{\prime }}.$$S_{i,j}=\sum_{i^{\prime}\leq i}\sum_{j^{\prime}\leq j}A_{i^{\prime},j^{\prime}}.$​

  • 基于容斥原理,得到递推关系 $S_{i,j}=A_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}.$$S_{i,j}=A_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}.$​

  • 要想查询子矩阵的和,则计算 $S_{i_2,j_2}-S_{i_1-1,j_2}-S_{i_2,j_1-1}+S_{i_1-1,j_1-1}$$S_{i_2,j_2}-S_{i_1-1,j_2}-S_{i_2,j_1-1}+S_{i_1-1,j_1-1}$,时间复杂度降到O(mn)​

• xxxxxxxxxx
  15
  1
  int n, m;
  2
  std::vector<std::vector<int>> a, ps;  // (n + 1) x (m + 1).
  3
  
  4
  // 计算二维数组的前缀和
  5
  void prefix_sum() {
  6
    ps = a;
  7
    for (int i = 1; i <= n; ++i)
  8
      for (int j = 1; j <= m; ++j)
  9
        ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
  10
  }
  11
  
  12
  // 查找在 [x1, y1] 到 [x2, y2] 的子矩阵的元素和
  13
  int query(int x1, int y1, int x2, int y2) {
  14
    return ps[x2][y2] - ps[x1 - 1][y2] - ps[x2][y1 - 1] + ps[x1 - 1][y1 - 1];
  15
  }
  

• 一维差分

  • 前缀和的逆运算, 一般是通过维护差分序列信息, 对区间多次修改后恢复原序列, 实现对原序列的查询

  • 对于数组 $a_n$$a_n$, 差分序列为 $D_i=a_i-a_{i-1},a_0=0$$D_i=a_i-a_{i-1}, a_0=0$, 差分序列的前缀和即为原数组

  • 区间操作,在区间 [l,r]中的每个数都加上一个值v, 则 $D_l=D_l+v,D_{r+1}=D_{r+1}-v$$D_l=D_l+v, D_{r+1}=D_{r+1}-v$​

• xxxxxxxxxx
  13
  1
  int n;
  2
  std::vector<int> diff, a;
  3
  
  4
  // 为区间 [l, r]内所有元素加值 v
  5
  void add(int l, int r, int v) {
  6
    diff[l] += v;
  7
    if (r < n) diff[r + 1] -= v;
  8
  }
  9
  
  10
  // 在所有修改之后,查询之前执行前缀和操作恢复原序列
  11
  void prefix_sum() {
  12
    for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + diff[i];
  13
  }
  

• 二维差分

  • 多维差分可看作多维前缀和的逆运算,则求多维差分数组的操作就相当于根据多维前缀和求它的原数组,即 $D_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}.$$D_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}.$​

  • 要对左上角$(x_1,y_1)$$(x_1,y_1)$,右下角$(x_2,y_2)$$(x_2,y_2)$的矩阵中每个数字加上v,可以对其差分数组进行操作

    $\begin{array}{c}{D}_{x_1,y_1}\leftarrow D_{x_1,y_1}+v,\\ D_{x_1,y_2+1}\leftarrow D_{x_1,y_2+1}-v,\\ D_{x_2+1,y_1}\leftarrow D_{x_2+1,y_1}-v,\\ D_{x_2+1,y_2+1}\leftarrow D_{x_2+1,y_2+1}+v.\end{array}$$\begin{gathered} D_{x_1,y_1}\leftarrow D_{x_1,y_1}+v, \\ D_{x_1,y_2+1}\leftarrow D_{x_1,y_2+1}-v, \\ D_{x_2+1,y_1}\leftarrow D_{x_2+1,y_1}-v, \\ D_{x_2+1,y_2+1}\leftarrow D_{x_2+1,y_2+1}+v. \end{gathered}$​

  • 在所有修改操作结束后，只需要执行一遍二维前缀和，就可以快速查询更新后的数组的值

  xxxxxxxxxx
  21
  1
  int n, m;
  2
  std::vector<std::vector<int>> diff, a;
  3
  
  4
  // 为 [x1, y1] 到 [x2, y2]的每一个元素都加v
  5
  void add(int x1, int y1, int x2, int y2, int v) {
  6
    diff[x1][y1] += v;
  7
    if (x2 < n) diff[x2 + 1][y1] -= v;
  8
    if (y2 < m) diff[x1][y2 + 1] -= v;
  9
    if (x2 < n && y2 < m) diff[x2 + 1][y2 + 1] += v;
  10
  }
  11
  
  12
  // 在所有修改之后,查询之前执行前缀和操作恢复原序列.
  13
  void prefix_sum() {
  14
    a = diff;
  15
  
  16
    for (int i = 1; i <= n; ++i)
  17
      for (int j = 1; j <= m; ++j) a[i][j] += a[i - 1][j];
  18
  
  19
    for (int i = 1; i <= n; ++i)
  20
      for (int j = 1; j <= m; ++j) a[i][j] += a[i][j - 1];
  21
  }
  

   

模拟/枚举/倍增

严格遵循题目规则，不重不漏地 (or 有智慧地)穷举所有可能状态

1. 建表查询: 将状态抽象化, 对于日期(仅12个固定值), 方位(上,下,左,右)等可枚举的量,直接建表

   xxxxxxxxxx
   9
   1
   // 数组查表处理月份天数,索引从1开始
   2
   int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
   3
   // 数字确定移动方向
   4
   int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
   5
   for(int k=0;k<4;k++){
   6
       int xx=x+dir[k][0],yy=y+dir[k][1];
   7
       if(边界合法性判断)continue;// 新坐标不合法
   8
       ... // 执行解决办法
   9
   }
   

2. 面向过程,结果编程: 保证所有过程都在问题之内,排演所有结果符合测试集要求

3. 关于枚举: 考虑可能的情况, 枚举的元素, 枚举的空间范围(有优化空间), 枚举顺序

4. 打表: 用于填空题, 暴力模拟题目要求, 人工寻找输出结果, 一般运行时间t>1s

贪心

鼠目寸光: 不从整体最优上加以考虑，而是始终做出在当前看来最好的选择,刷题!刷题!再刷题!

• 注意点:

  1. 可以一直向前走, 没有后顾之忧. ( 贪心思想的选择, 局部最优走到终点即为全局最优 )

  2. 关键问题转化, 边界条件的处理. ( 找到贪心策略 )

  3. 每轮都将问题转化成一个规模更小的子问题，直到问题被解决.

  4. 一般配合排序等方法找最值

   

• 典型例题思维:

  • 双向约束(邻域依赖)问题: 将双向约束拆分为两个单向约束, 分别进行遍历。先解决左邻居，再解决右邻居, 最后取极值。

    分发糖果

    接雨水(贪心,双指针,动态规划,单调栈)

  • 容器选择,性能优化: vector(动态数组)的增删操作相对于list(双向链表)的耗费要大得多,依据已有思路可以转变容器优化性能

    根据身高重建队列

  • 区间排序方向选择: 不重叠调度选右端点；合并区间选左端点。

    • 选右边界排序,可避免区间范围过大的问题

    用最少数量的箭引爆气球(合并区间)

    无重叠区间(左右均可,推荐右)

  • 遍历顺序的选择: 不要有后顾之忧,宁愿边界多处理,也不回头看一步

    单调递增的数字

    划分字母区间

单调栈

要寻找任⼀个元素的右边或者左边第⼀个⽐⾃⼰⼤或者⼩的元素的位置,考虑单调栈

• 单调栈: 本质是空间换时间,通过维护栈中的元素单调性,在遍历的过程中记录右边第⼀个⽐当前元素⾼的元素，优点是整个数组只需要遍历⼀次,单调栈⾥只需要存放元素的下标i

• 一般模板:

  xxxxxxxxxx
  10
  1
  stack<int> stk;// 递增栈
  2
  vector<int> ans(n);
  3
  for (int i = 0; i < n; i++){
  4
      while (!stk.empty() && a[stk.top()] < a[i]){//找到第一个比当前值大的元素
  5
          ans[stk.top()] = i + 1;//存放该元素的下标
  6
          //有时为ans[stk.top()]i-stk.top()存放距离
  7
          stk.pop();
  8
      }
  9
      stk.push(i);
  10
  }
  

单调队列(滑动窗口)

维护元素单调性的队列就叫做单调队列,可用于获取窗口内最值(队首元素)

• 单调队列的设计:

  • pop(val)：如果窗口移除的元素val等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作

  • push(va):如果push的元素val大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

• 一般模板:

  xxxxxxxxxx
  15
  1
  deque<int> dque; // 使用deque来实现单调队列
  2
  
  3
  void pop(int value) {
  4
      if (!dque.empty() && value == dque.front()) {
  5
          dque.pop_front();
  6
      }
  7
  }
  8
  
  9
  void push(int value) {
  10
      //保持队列里的数值是单调从大到小
  11
      while (!dque.empty() && value > dque.back()) {
  12
          dque.pop_back();
  13
      }
  14
      dque.push_back(value);// 存储下标也可
  15
  }
  

• 滑动窗口取最大值 leetcode NO.239

  xxxxxxxxxx
  20
  1
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  2
      //定义单调队列
  3
      //.....
  4
      vector<int> result;
  5
      // 先将前k的元素放进队列
  6
      for (int i = 0; i < k; i++) { 
  7
          dque.push(nums[i]);
  8
      }
  9
      // result 记录前k的元素的最大值
  10
      result.push_back(dque.front()); 
  11
      for (int i = k; i < nums.size(); i++) {
  12
          // 滑动窗口移除最前面元素
  13
          dque.pop(nums[i - k]); 
  14
          // 滑动窗口前加入最后面的元素
  15
          dque.push(nums[i]); 
  16
          // 记录对应的最大值
  17
          result.push_back(dque.front()); 
  18
      }
  19
      return result;
  20
  }
  

   

搜索

backtrack ( 回溯 )

核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止. 本质上是穷举, 效率并不高, 一般为指数级别, 可借助剪枝优化来提高效率.

• 一般解决以下问题:

  xxxxxxxxxx
  5
  1
  1. 组合问题：N个数里面按一定规则找出k个数的集合, 不强调元素顺序
  2
  2. 切割问题：一个字符串按一定规则有几种切割方式
  3
  3. 子集问题：一个N个数的集合里有多少符合条件的子集
  4
  4. 排列问题：N个数按一定规则全排列，有几种排列方式, 强调元素顺序
  5
  5. 棋盘问题：N皇后，解数独等等
  

• 一般模板[ 回溯函数, 终止条件,遍历过程,( 剪枝 ) ]

  xxxxxxxxxx
  24
  1
  // 参数列表 vector<vector<T> >&res, vector<T>&path, int startIndex, vector<T>nums
  2
  void backtrack(参数) {   
  3
      // 求子集等情况,可在该行存放结果
  4
      if (终止条件) {
  5
          存放结果;
  6
          return;
  7
      }
  8
  
  9
      for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  10
    //for(int i=startIndex; i<nums.size()&& (剪枝操作) ; i++ )
  11
          if(...){continue;}// 也可以剪枝
  12
          处理节点;
  13
          // path.push_back(nums[i]);
  14
          backtrack(路径，选择列表); // 递归
  15
          // backtrack(res, path, i+1, nums);
  16
          回溯，撤销处理结果;
  17
          // path.pop_back();
  18
      }
  19
  }
  20
  
  21
  // 调用
  22
  vector<vector<T>> res;
  23
  vector<T>path;
  24
  backtrack(res,path , 0, nums);
  

  • 关于startIndex

    • i==startIndex是为了避免单纯因为顺序不同而重复出现的子答案

    • 在回溯过程中for(i=start；xxxx; i++){},i++是为了确保子答案的选取时不会再从头开始选取

    • 如果是排列，不同顺序代表了不同的答案，则int i=0. startlndex不再需要

    • 去重操作,if (i > start && num[i] == num[i-1]) continue;

  • 关于sum Target

    • 题目要求子项和等于target，因此首先要注意除了正常return，还要考虑sum>target立刻return

    • 剪枝操作，sum+子项<=target，但是要注意子项必须满足升序排列，有必要时提前sort()

  • 关于优化

    • 组合类问题, 如果仅用于求符合解的个数, 可以使用dp优化例: 目标和