二分查找类

对于有序序列需要可以选择二分查找方法，将时间复杂度由o(n)降为o(log(n))
二分查找不止可查找数目也可根据如奇数偶数划分
二分为输入向量 题2276

最大递增序列

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

  1. 使用数组记录当前增长数组
  2. 使用二分查找找到位置，如果插入最后或替换位置

对于JAVA：Arrays.binarySearch(dp, 0, res, pair[1])
对于C++：binary_search(arr[], size , indx) arr[]： 数组首地址；size： 数组元素个数;indx: 需要查找的值。
lower_bound(arr.begin(), arr.end(), indx) 函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置

  1. 统计辅助数组程度

烧饼问题
找到最大反转到头，二次反转到底，后进行递归调用
接雨水问题
双指针+动态规划算法

三色标记法

标记三种状态，即未被访问，不满足条件， 满足条件当我们首次访问一个节点时，将其标记为灰色，并继续搜索与其相连的节点。如果在搜索过程中遇到了一个灰色节点，则说明找到了一个环，此时退出搜索

多数之和

一般解法：排序+双指针
注意问题1. 溢出问题2. 唯一性问题3.边界条件

广度优先搜索

通过queue记录节点遍历情况，通过其他记录节点访问状态，未被访问的加入队列，遍历直到队列为空

弗洛伊德算法

for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 三次循环，同时更新最短距离与相应的， 其中k为中间节点
image.png

迪杰特斯拉算法

image.png
使用当前最短节点对距离进行更新
对于附加条件增加额外信息，使用优先队列进行存储最短

KMP算法

首先统计匹配数组内部相等位置在匹配数组是通过记录结果进行跳转

  1.     int strStr(string haystack, string needle) {
  2.         int n = haystack.size(), m = needle.size();
  3.         if (m == 0) {
  4.             return 0;
  5.         }
  6.         vector<int> pi(m);
  7.         for (int i = 1, j = 0; i < m; i++) {
  8.             while (j > 0 && needle[i] != needle[j]) {
  9.                 j = pi[j - 1];
  10.             }
  11.             if (needle[i] == needle[j]) {
  12.                 j++;
  13.             }
  14.             pi[i] = j;
  15.         }
  16.         for (int i = 0, j = 0; i < n; i++) {
  17.             while (j > 0 && haystack[i] != needle[j]) {
  18.                 j = pi[j - 1];
  19.             }
  20.             if (haystack[i] == needle[j]) {
  21.                 j++;
  22.             }
  23.             if (j == m) {
  24.                 return i - m + 1;
  25.             }
  26.         }
  27.         return -1;

Rabin-Karp 字符串编码

image.png

BrianKernighan算法

统计一个数值中1的数量
通过不断去除最后一个1的方法 即 题型总结 - 图4的方法去除最低位1，通过循环数统计数量

环形链表问题

使用快慢指针找到相等的点，并设计标记方法对中间结果进行剪枝
例子：457题 141题

背包问题

背包问题为NP问题因此一般使用动态规划算法进求解（参考背包9讲)
使用二元数组分别记录当前重量数与背包内内容数，分别考虑没个状态下是否取出当前元素是否满足要求
对于完全背包问题使用正序更新， 对于01背包使用功倒序更新
等和子集就是两个背包

丑数问题

解法1：使用计算去除堆栈中最小元素分别与因子相乘，并放入set中防止发生重合
解法2：使用动态规划算法分别计算最小因子位置，每次计算其中最小的，并对最小point值加1

栈相关

主要处理先入后出情况
132模式维护一个单调栈，考虑逆向遍历

动态规划算法

将大问题拆分为子问题，分别研究子问题之间推导关系与子问题关系
对于滚动数组问题，分析其中更新与前一状态关系进而减少内存使用
中间结果不一定值最终值
//装换目标条件，根据题目要求找到等价问题如494题 转化为和为负数
动态规划递推公式可能是多级差分的

单调栈问题

单调栈通过记录数值坐标值保持栈内数据的递增性，
与问题相反
对于如最大矩形，柱状图最大矩形问题，需要通过单调栈计算左右边界，右边界为单调数，左边界为栈顶数值
https://github.com/labuladong/fucking-algorithm/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E5%8D%95%E8%B0%83%E6%A0%88.md

  1. vector<int> nextGreaterElement(vector<int>& nums) {
  2.     vector<int> res(nums.size()); // 存放答案的数组
  3.     stack<int> s;
  5.     for (int i = nums.size() - 1; i >= 0; i--) {
  6.         while (!s.empty() && s.top() <= nums[i]) {
  8.             s.pop();
  9.         }
  10.         // nums[i] 身后的 next great number
  11.         res[i] = s.empty() ? -1 : s.top();
  12.         // 
  13.         s.push(nums[i]);
  14.     }
  15.     return res;
  16. }

图遍历

可以记录图遍历状态实现动态规划
—-

广度遍历

队列结构，先进先出

深度遍历

栈结构，后进先出

  1.     void dfs(int u) {
  2.         visited[u] = 1;
  3.         for (int v: edges[u]) {
  4.             if (visited[v] == 0) {
  5.                 dfs(v);
  6.                 if (!valid) {
  7.                     return;
  8.                 }
  9.             }
  10.             else if (visited[v] == 1) {
  11.                 valid = false;
  12.                 return;
  13.             }
  14.         }
  15.         visited[u] = 2;
  16.     }
  18.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  19.         edges.resize(numCourses);
  20.         visited.resize(numCourses);
  21.         for (const auto& info: prerequisites) {
  22.             edges[info[1]].push_back(info[0]);
  23.         }
  24.         for (int i = 0; i < numCourses && valid; ++i) {
  25.             if (!visited[i]) {
  26.                 dfs(i);
  27.             }
  28.         }
  29.         return valid;
  30.     }

棋盘问题

在棋盘上能否追上计算目的地与之间的曼哈顿距离

滑动窗问题

  1. 使用优先队列记录当前滑窗内最大值
  2. 单调队列，分析下标与数值之间的关系，保证队列内严格单调递减，而下标递增
  3. 预处理+分组，分别统计每个固定窗内最大值，如果非不重叠窗则计算当前值与所在窗最大值关系，通过递推关系进行分析

重复数字问题

对于只有单个数字重复一次可以使用异或进行运算

不确定重复次数时方法

  1. 二分法

通过将目标区间进行二分，查找二分区内数组数量，如果数字数量大于长度则重复数字在该区间

  1. 二进制

统计二进制中位数重复次数进行二分查找

  1. 快慢指针

将数组当做链表，则重复数值一定形成环，通过快慢指针找到环所在位置（不形成自环）

回溯算法

通过回溯与深度遍历相结合，可以根据遍历条件限制进行适当剪枝操作

根据身高重建队列

身高与排名反向排序，即升序在身高相同情况下则排名降序排列，后根据空位情况进行移动与插入

递增数组问题

对于递增数组使用记录记录数组变化时间点数据后进行累加
将时间复杂度从题型总结 - 图5降低为题型总结 - 图6
连续数据也可以使用前缀和方法如题560

字母扑克牌等有限状态

可使用定长数组记录状态，在一定范围内可使用范围外数值进行标记，用取余数方法不改变原值

任务调度

构造方法
考虑执行任务最多的一种出现最大数量以及最大值的数量，最大时长与数值长度之间的差距
image.png

Manacher算法

https://vdn1.vzuu.com/SD/16cefb82-237d-11eb-921e-ee4d6c3fcc25.mp4?disable_local_cache=1&auth_key=1630678820-0-0-f3556069d8f3b72ca9d084cb0e219dfd&f=mp4&bu=pico&expiration=1630678820&v=hw

  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         int n = s.size();
  5.         string t = "$#";
  6.         for (const char &c: s) {
  7.             t += c;
  8.             t += '#';
  9.         }
  10.         n = t.size();
  11.         t += '!';
  13.         auto f = vector <int> (n);
  14.         int iMax = 0, rMax = 0, ans = 0;
  15.         for (int i = 1; i < n; ++i) {
  16.             // 初始化 f[i]
  17.             f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
  18.             // 中心拓展
  19.             while (t[i + f[i]] == t[i - f[i]]) ++f[i];
  20.             // 动态维护 iMax 和 rMax
  21.             if (i + f[i] - 1 > rMax) {
  22.                 iMax = i;
  23.                 rMax = i + f[i] - 1;
  24.             }
  25.             // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
  26.             ans += (f[i] / 2);
  27.         }
  29.         return ans;
  30.     }
  31. };

串联子串

通过可以通过判断两个hashmap是否相同，同时维护多个窗来减少循环次数

旋转矩阵

除计算对应旋转位置外，还可以通过两次180度翻转实现90旋转

动态规划与贪心算法

对于可以动态规划的例子尝试局部最优是否为最优解
其中记录方法不限于使用数组记录状态，可以使用hashmap对题目进行优化如hashmap, int>

荷兰国旗问题

对于少于小于等于3的排序问题，如题目75或排列奇数偶数问题，分别把两种数据分别放在状态的序列的头部与尾部

前缀和问题

前缀和可以通过哈希散列方式记录，减少记录量

贪心算法

例题超级洗衣机517
A 与 BB 两组之间的衣服，最多需要 image.png 次衣服移动；
组内的某一台洗衣机内的衣服数量过多，需要向左右两侧移出衣服，这最多需要image.png 次衣服移动。

  1. class Solution {
  2. public:
  3.     int findMinMoves(vector<int> &machines) {
  4.         int tot = accumulate(machines.begin(), machines.end(), 0);
  5.         int n = machines.size();
  6.         if (tot % n) {
  7.             return -1;
  8.         }
  9.         int avg = tot / n;
  10.         int ans = 0, sum = 0;
  11.         for (int num: machines) {
  12.             num -= avg;
  13.             sum += num;
  14.             ans = max(ans, max(abs(sum), num));
  15.         }
  16.         return ans;
  17.     }
  18. };

Boyer-Moore投票算法

思路

将众数记为 +1其他为-1则求和大于0

接雨水问题

题407二维接雨水问题：
通过短板效应，使用优先队列，从外到内，从低到高对进行更新，进而统计接雨水数量