做过的算法题和一些记录的笔记
- nowcoder 牛客网
- fudan
- PAT
- LeetCode 下的是国际站中的相关题目，lc-cn 和 lc-plug 下是中国站的题目
学习资源：
-
Leetcode/剑指Offer题解： https://www.cyc2018.xyz/#%E7%AE%97%E6%B3%95
-
maomao算法笔记 <= 按照leetcode题型进行分类，动态规划这块整理的不错
其他：
- OJ的输入输出的问题 牛客网在线判题系统使用帮助
目录：
数组：
-
滑动窗口法：
滑动窗口法方法，一般用于解决数组或字符串中，满足某类条件的最大或最小的连续区间。leetcode 相关例题：
链表：
-
删除链表中的节点时，并不一定需要知道其 prev_p 指针，直接将其值和下一个节点进行交换，然后删除下一个节点即可。前提是所删除的节点不是末尾节点！！
-
通过快慢双指针，一个每次走一步，另一个每次走两布。可以确定链表的中间节点。 👉 链表反转 + 快慢指针 示例。
快慢指针也可用于判断链表中是否存在环，若存在环则 fast 与 slow 肯定会在若干步之后相遇，若要确定环的入口，slow 与 fast 相遇时我们再额外使用一个指针 ptr 它指向链表头部， 它和 slow 每次向后移动一个位置，最终它们会在入环点相遇 👉环形链表 II。
-
双向链表可以很方面的检索其前后节点，插入、删除时链表的链接都很便捷。
递归的过程过程本质上是一系列的函数栈调用，所有的递归过程都可以通过迭代来实现。
相关题目：
-
字符串表达式计算：
中缀表达式转后缀表达式（逆波兰表达式）。 例1， 例2， 符号栈是否进行弹出取决于，当前操作符与栈顶操作符优先谁高，栈顶优先级高或者相等则先进行出栈和计算（相同优先级别，从左到右计算， 所以也要弹出），直到栈顶元素优先机低于当前操作符
-
单调栈，是借助栈保存遍历过程中的递增、递减情况，以辅助算法的实现。 例：总结：单调递减栈，一般用来在遍历元素的过程中，找后续第一个比自身大的元素。递增栈反之~
其他题目补充：
-
单调队列
-
并查集
因为判断两个元素是否处于同一个集合的时候，通过比对两个是否拥有同样的 root。所以可以直接将集合中元素指向 root，压缩路径，以提高访问速度。
知识点：地址映射函数 + 冲突处理方法。
地址映射函数（哈希函数）：？
冲突处理方法：1）开地址发法；2）闭地址法 => 拉链法 在C++ STL 中，冲突处理方法是？
相关题目：
树的遍历：二叉树的先序、中序、后序、层次序遍历。因为树本身是一种特殊的图，因为深度、广度优先遍历的概念也存在。二叉树的广度优先遍历 = 层次序遍历，先序遍历 = （每次先访问左子树的）深度优先遍历。
二叉搜索树（BST）相关：二叉搜索树具备一些特殊的性质。
完全二叉树：每个节点都有左右两个子树，如果通过数组来存储完全二叉树，则每个节点的左右子节点可以通过快速计算下标获得。
平衡二叉树：检查二叉树是否平衡；二叉树平衡调整。
红黑树：红黑树着色规则？
字典树/前缀树：实际上就是一个26叉树，每个节点有26个节点，对应26个字符。👉前缀树
其他：
-
给定一个先序遍历结果，求可能的后续遍历结果的可能数 = catalan 数 = C(2n,n) / (n+1)。 假设n个节点存在二叉排序树的个数是G(n)，G(n) = G(0)G(n-1)+G(1)(n-2)+...+G(n-1)*G(0)
值得说的题目：
-
通过迭代实现树的遍历 👉 通过栈迭代实现中序遍历 。在二叉树的三种遍历中，通过栈实现的难度排序是：后序 > 中序 > 前序。
-
典型的层次序遍历代码写法 👉 二叉树层次遍历示例 。
-
二叉搜索树中，两个节点的最近公共祖先，因为是二叉搜索树，遍历找分叉节点。 延伸题目：在普通二叉树中，找两个节点的公共祖先，通过 👉 递归求解！
-
判断一个树是否是对称二叉树
-
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树
-
二叉树的层次序遍历：借助队列实现
-
通过中序 + 后续重构一个二叉树；通过 中序 + 后续 重构一个二叉树；树中应该是不存在重复元素的 => 转化为递归建树的过程
-
树的递归遍历十分简单，但是要会通过迭代的方式完成同样的操作。例如，题目：通过迭代实现树的先序遍历 =>通过栈完成
-
将二叉树叶子节点的 null 指针进行填充，使其能够快速达到某种访问目的 =>
线索二叉树 -
判断一个二叉搜索树的后序遍历序列是否是合法的. => 二叉搜索树的后序遍历序列
-
二叉树的存储和加载 😭，👉 二叉树的序列化与反序列化
最大/最小堆是优先级队列的一种实现方法. C++中的堆 相关题目：
- 数据流中的中位数
斐波那契数递归实现版本的时间复杂度是O(2^n)；
递归本身不应该单独作为一个算法类别，而是很多算法的实现通过递归完成。递归的本质就是将问题划分为更小的子问题进行递归求解，把握住两点：1）子问题与原问题之间的关联；2）递归终止条件；
DFS过程本身很适合通过递归实现：
这些题不会做：
二分查找思想：二分查找适合在有序的数组种查找某一个值，或者某一个边界！
搜索相关题目：
排序：
-
计数排序思想：
对公司员工按照年龄进行排序，年龄的可取值（0~99）。遍历一次统计各个年龄员工的个数，然后再遍历一遍直接将员工放在合适的位置上。时间复杂度O(n) 空间复杂度O(1)
-
Top-k 排序：top-k快排中，找到第 k 个基准位置即可。👉 数组中的第K个最大元素
哈希分支法：海量数据中出现次数最多的前 K 个，Map-Reduce 思想。
其他例题：前k个高频元素
-
归并排序，归并排序分为 1）自顶部向下 2）自底向上，两种归并方法 ？实际上，两者的思路都是分治，前者是基于递归的实现过程，后者是基于迭代的实现过程。
多路归并思想 👉 有序矩阵中第K小的元素 ，合并K个升序链表
-
快排实现 ： 雪糕的最大数量
void quick_sort(vector<int>& nums, int i, int j) { if (i >= j) return; // 以基准划分 int pivot_num = nums[i]; int c = i + 1, high = j; while (c < high) { if (nums[c] <= pivot_num) c++; else { swap(nums[c], nums[high]); high--; } } int pivot = nums[high] > pivot_num ? high-1 : high; swap(nums[pivot], nums[i]); // 分治 quick_sort(nums, i, pivot - 1); quick_sort(nums, pivot + 1, j); }
相关的题目：
-
🚩字符串编辑距离
-
KMP — 字符串匹配
主要在于 next[j] 数组的计算，next[j] 表示在模式串第 j 个位置匹配失败时，应该下一步应该跳转至模式串的第几个字符。next[j] 为 0 时，主串前移一位，模式串重新从头开始匹配。
int m = evil.size(); fail.resize(m); // fail数组初始值均为0 // 这是 KMP 算法的一部分，把「evil」看作模式串，得到它的 fail[] 数组 for (int i = 1; i < m; ++i) { int j = fail[i - 1]; while (j && evil[j] != evil[i]) { j = fail[j - 1]; } if (evil[j] == evil[i]) { fail[i] = j + 1; } }next数组的性质：S[0] 到 S[i] 这一段子串中，前next[i]个字符与后next[i]个字符一模一样。最后得到的 fail / next 数组中的内容
// 求 KMP 算法中的 next 数组，next数组的本质是 max_match_len 数组 // a b a b a b // 0 0 1 2 3 4 // 当 s[i] 与主串匹配失败时，应从s[ next[i - 1] ] 处接着与主串继续匹配相关题目：👉 最长快乐前缀
深度优先DFS、广度优先BFS；一般深度优先遍历通过递归实现，广度优先遍历通过队列实现。广度优先一个经典的应用就是寻找最优路径。
在图遍历时注意连通域的问题，一般遍历尝试从任意一个节点开始进行DFS或者BFS，并记录 visit 情况，这样就可以处理不同的连通域了。求图中连通域的个数：
- 从每一个节点尝试DFS遍历，统计能够遍历的次数 岛屿数量
- 也可以尝试从每一个节点开始广度优先遍历
- 借助并查集，连通域的个数就是并查集中连通分量的数目。
最小生成树；
最短路径；
💔 动态规划的核心：1）定义问题状态；2）获取状态之间的转移方程，用已经计算的状态值来推算当前新的状态值；3）求解问题时，采用 递归 或 递推（迭代） 均可。
在构建状态之间的转移方程时，如何讲原问题进行表述是最为关键的一步。这里列举几个例子：
合理的表述之上状态转移方程的构建则十分简单：看 当前状态 可以转移到其它哪些状态。另一种方式是看当 前状态 可以由之前的哪些状态转移。
-
dp[i] = max(dp[j] + 1) , s.t. dp[i] > dp[j], j in (0, i-1): -
最长回文子串，最长回文子序列
注意子串和子序列的区别，子序列不被是连续的。在最长回文子序列中：dp[i][j] 表示 i~j 之间的序列中的最长回文子序列。
if(s[i] == s[j]): dp[i][j] = max(dp[i+1][j-1]+2, dp[i+1][j] , dp[i][j-1]); else: dp[i][j] = max(dp[i+1][j] , dp[i][j-1]); -
数塔dp
-
背包问题：1）01背包；2）完全背包；3）多重背包问题；
// 背包问题中，dp[i][j]表示： 前 i 个物品中，容量为 j 的背包所能获得的物品总价值 // 01背包：不选 i 与 选 i dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); // 完全背包：i 物品可以被多次选择 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]); // 多重背包: 每种物品被选择的次数有限制 dp[i][j] = max(dp[i-1][j], dp[i-1][j-k * w[i]] + k * v[i]); // s.t. k in (1, limit);
-
数位DP数位dp 一般应用于：1) 求出在给定区间[A,B]内，符合条件P(i)的数i的个数. 2) 条件 P(i) 一般与数的大小无关，而与 数的组成 有关。
例题：数字1的个数，至少有1位重复的数字，找到所有好字符串。
补充笔记：
- 从算法实现的角度来看动态规划的过程是一个打表操作，一般而言DP状态设置是两维的话（dp[i][j]）时间复杂度为O(m*n)，但是在很多问题中可以通过滚动数字对空间使用进行优化为O(m)或者O(n)。
- 动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。
补充例题：
-
二叉树的最大路径和， 通过 👉 “递归式式的动态规划” 求解。
-
方法1： 1）用栈模拟一遍，将所有无法匹配的括号的位置全部置1，例如: ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0] ； 2）经过这样的处理后, 此题就变成了寻找最长的连续的0的长度。 实际上1）2）步骤可以合并为一个步骤，每次读取到')'时进行出栈，记录最大连续出栈个数便为结果数。 方法2 动态规划： dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。状态转移方程 👉[最长有效括号] -
// G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0) dp[i] += dp[j - 1] * dp[i - j]; -
一般当我们实现 DFS+打表 （也称
记忆化搜索）的方式之后，很容易得到其基于迭代的 动态规划 ：交错字符串 、 分割等和子集👉 记忆化搜索
这些题不会做：主要还是不知道一道题是不是要用dp来做，以及状态如何表示 ！
-
恰有K根木棍可以看到的排列数目 <= 借助滚动数组进行空间优化
在动态规划中，不管是行优先遍历还是列优先遍历，都可以实现状态转移的计算。但是，只有一种情况下可以基于滚动数组的进行优化。
C++中的位运算操作符： 带符号左右移：<< 、>>， 与或非： &、 | 、! ， 异或：^，取反：~
-
C++中没有（java中有）无符号左右移：
<<<、>>>。在c++中实现的方式也很简单，先将拟进行无符号右移的数转换成无符号类型，然后执行普通右移即可。 -
异或操作具有的性质： 0 ^ x = x ，x ^ x = 0. a^b = c ， a^b^b = a， 即 c^b=a 同理 c^a =b.
需要比较熟练的：
- 判断和统计数的二进制表示下，1 和 0 的个数
// 把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0 。 那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
int num = 0;
while(n){
n &= (n - 1);
num++;
}参考题目：
- 数组中数字出现的次数
- 数组中数字出现的次数2
- 判断一个整数是否是2的幂 ，如果 n 是正整数并且 n & (n - 1) = 0，那么 n 就是 2 的幂。如果 n 是正整数并且 n & (-n) = n，那么 n 就是 2 的幂
大数的 + - ，* /
其他：
快速幂，是一个在 Θ(logn) 的时间内计算 a^n 的小技巧，而暴力的计算需要 Θ(n) 的时间。教程 👉 快速幂思想 。求 2^1000，可以用 快速幂+大数乘法 2^20 · 2^20 · ......
-
凸多边形判断：一个凸多边形，保证相邻边总是单调的向顺时针或逆时针旋转。叉积的正负可以判断是否单调旋转。 => 通过相邻两边叉积（外积）来判断 👉 link。注意二维空间叉积的结果是一个伪向量。
-
判断点是否在三角形内（是否在多边形内）：~