左程云视频笔记
1.并查集
class UnionFind {
public:
vector<int> father;
//初始化，坐标和对应值相等的位置是根节点
UnionFind(int num) {
for (int i = 0; i < num; ++i) {
father.push_back(i);
}
}
int find(int n) {
if (farther[n] == n) {
return n;
}
father[n] = find(father[n]);
return father[n];
}
bool union(int a, int b) {
int fa = father[a];
int fb = father[b];
bool isConnected = (fa == fb);
father[fb] = fa;
return isconnected;
}
};
2.KMP
vector<int> getNext(string& str) {
int n = str.size();
vector<int> next(n);
if (n == 1) return {-1};
next[0] = -1;
next[1] = 0;
int i = 2, cn = 0;//cn表示拿哪个位置的字符和i-1位置的比,前缀范围
while (i < n) {
if (str[i-1] == str[cn]) {
//相等说明前缀串和
next[i++] = ++cn;
} else if (cn > 0) {
//当前跳到cn位置的字符，和i-1位置的字符配不上
//可以往前跳那就往前跳
cn = next[cn];
} else {
//没法往前跳i位置就应该是0
next[i++] = 0;
}
}
return next;
}
int KMP(string& str1, string& str2) {
int n1 = str1.size(), n2 = str2.size();
if (n1 < n2 or n1 == 0 or n2 == 0) return -1;
int i1 = 0, i2 = 0;
vector<int> next = getNext(str2);
while (i1 < n1 and i2 < n2) {
//相等的话两者一起往前走
if (str1[i1] == str2[i2]) ++i1, ++i2;
//str2处在第一个位置，str1换一个位置和str2匹配
//这里等同于next[i2] == -1;没法往前跳，str1向前走
else if (i2 == 0) ++i1;
//i2可以往前跳就往前跳
else i2 = next[i2];
}
//i2匹配到了最后说明匹配成功
return i2 == n2 ? i1 - i2 : -1;
}
3.哈希表
性质：
- 输入集合很大，输出集合较小。
- 相同的输入一定有相同的输出。
- 不同的输入可能有哈希碰撞。
- 映射到的输出集合较为均匀的分散。
输入集合in通过哈希函数f映射到输出集合out之后再经过取模m,得到集合mi，则集合mi也是均匀分布。
例：有1G内存，求无符号整型最多出现多少次？ 哈希表映射之后再映射这样就会产生很多重复。
4.布隆过滤器
条件：
- 对集合只有加入和查找两种操作；
- 可以允许一定误差（不在集合中被误认为在集合中）； 使用场景：黑名单集合，爬虫去重问题。 要点：使用位图进行压缩 使用基础类型进行拼凑
//表示320bits
int arr[10];
//1.取出178bit位的状态
int numIdx = 178 / 32, bitIdx = 178 % 32;
int status = (arr[numIdx] >> bitIdx) & 1;
//2.把178位的状态改成1
arr[numIdx] = arr[numIdx] | (1 << bitIdx);
//3.把178位的状态改成0
arr[numIdx] = arr[numIdx] & (~(1 << bitIdx));
使用位图设计布隆过滤器
n个URL通过K个哈希函数映射成K个out集合，统一取模m得到x，所有x位置就标记为是集合中的黑色。- K和m取多大？ 位图m开多大决定了失误率，m确定之后再去计算用多少个哈希函数。 样本量n，可接受失误率P
5.一致性哈希
目前主要应用于分布式缓存当中，一致性哈希可以有效地解决分布式存储结构下动态增加和删除节点
6.最长回文字串
- 中心扩散方法(需要考虑奇偶) 时间复杂度.
string longestPalindrome(string s) {
string res;
int n = s.size();
for(int k = 0;k < s.size();++k){
//奇数情况
for(int i = k,j = k;i >=0 && j < n && s[i] == s[j];--i,++j){
if(j-i+1 > res.size()) res = s.substr(i,j-i+1);
}
//偶数情况
for(int i = k,j = k + 1;i >=0 && j < n && s[i] == s[j];--i,++j){
if(j-i+1 > res.size()) res = s.substr(i,j-i+1);
}
}
return res;
}
- Manacher算法 生成一个回文半径数组，最右回文右边界。R记录右边扩充最远的idx位置。
- 生成处理串，决绝奇偶回文串单独讨论的情况。
- 设定中心坐标mid和右闭边界R
- 遍历，两种情况：
-
- mid在R外：从mid往两边暴力扩
- 2-1. i' 都在回文区域[L,R]内：pArr[i] = 某O(1)表达式
- 2-2. i' 回文区域有一部分在[L,R]外：pArr[i] = 某O(1)表达式
- 2-3. i' 回文区域和[L,R]的左边界压线：从R之外的字符开始往外扩，然后确定pArr[i]的答案：第一步扩失败了R不变，否则R变大。
-
class Solution {
public:
int expand(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) / 2;
}
string longestPalindrome(string s) {
int start = 0, end = -1;
string t = "#";
for (char c: s) {
t += c;
t += '#';
}
t += '#';
s = t;
vector<int> arm_len;
int right = -1, j = -1;
for (int i = 0; i < s.size(); ++i) {
int cur_arm_len;
if (right >= i) {
int i_sym = j * 2 - i;
int min_arm_len = min(arm_len[i_sym], right - i);
cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
} else {
cur_arm_len = expand(s, i, i);
}
arm_len.push_back(cur_arm_len);
if (i + cur_arm_len > right) {
j = i;
right = i + cur_arm_len;
}
if (cur_arm_len * 2 + 1 > end - start) {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
}
string ans;
for (int i = start; i <= end; ++i) {
if (s[i] != '#') {
ans += s[i];
}
}
return ans;
}
};
7.最长回文子序列
也即最长公共子序列
int longestPalindromeSubseq(string s) {
int n = s.size();
//dp[i][j]字符串 s 在 [i,j]范围内最长的回文序列长度
vector<vector<int>> dp(n,vector<int>(n));
//初始化：当 i == j 的时候 结果一定是 1
for(int i = 0;i < n;++i) dp[i][i] = 1;
//i 从尾到头遍历 ，j 从 i + 1 遍历到最后
for(int i = n - 1;i >= 0;--i){
for(int j = i + 1;j < n;++j){
//如果相等：下一层和前一列的 + 2
if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
//否则：还是下一层的这一列，这一层的下一列
else dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
8.滑动窗口的最大值
双端队列从头到尾递增
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>res;
deque<int> q;
for(int i=0;i<nums.size();i++){
if(!q.empty() && i>k-1+q.front()) q.pop_front(); //保证窗口大小，去掉失效的
while(!q.empty() && nums[q.back()]<=nums[i]) q.pop_back(); //保证单调性，
q.push_back(i); //加入队列
if(i>=k-1) res.push_back(nums[q.front()]); //一定大小下可以加入答案了
}
return res;
}
9.单调栈
查找右边第一个比自己大的数：维持一个单调递减的单调栈
num:5 4 3 6 1 2 0 7
idx:0 1 2 3 4 5 6 7
idx 0 1 2 --- 3 4 --- 3 5 --- 3 5 6
num 5 4 3 --- 6 1 --- 6 2 --- 6 2 0
栈底大栈顶小，只要新加入的数的下标不能够维持单调性了就需要弹出，弹出的idx数必须进行更新。
vector<int> dailyTemperatures(vector<int>& T) {
int n = T.size();
stack<int> stk;
stk.push(0);
vector<int> res(n, 0);
for (int i = 1; i < n; ++i) {
if (T[stk.top()] >= T[i]) {
stk.push(i);
} else {
while (!stk.empty() and T[stk.top()] < T[i]) {
int idx = stk.top(); stk.pop();
res[idx] = i - idx;
}
stk.push(i);
}
}
return res;
}
如果存在相同的数，栈中存放的就是链表结构。同一个链表中存放的是对应数值相等的不同下标。
例题：正数组中累积和与最小值的乘积，假设叫做指标A，给定一个数组，请返回子数组中指标A的最大值。
5 3 2 1 6 7 8 4
5:[5]---5 * 5 = 25
3:[5,3][3]---(5+3)*3=24
2:[5,3,2][3,2][2]
1:[5,3,2,1]---(5+3+2+1)*1 =
树形DP套路
二叉树节点间的最大距离问题
从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫做a到b的距离，那么二叉树任何两个节点之间都有距离，求整颗树上最大的距离。包括其本身也算一个距离。
常见分类：包含根节点还是不包含根节点。
- 根节点参与：左树高 + 1 + 右树高
- 根节点不参与：max左 + max右
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
struct Info {
int maxDis;
int hight;
};
递归函数：返回以x为头的整棵树，两个信息
struct Info {
int maxDis, hight;
Info(int x, int y):maxDis(x), hight(y) {}
};
class Solution {
int res = INT_MIN;
Info getMax(TreeNode* root) {
if (!root) return Info(0, 0);
//不经过root节点
Info leftInfo = getMax(root->left);
Info rightInfo = getMax(root->right);
int p1 = leftInfo.maxDis;
int p2 = rightInfo.maxDis;
int p3 = leftInfo.hight + 1 + rightInfo.hight;
int maxDis = max({p1, p2, p3});
int hight = max(leftInfo.hight, rightInfo.hight) + 1;
return Info(maxDis, hight);
}
public:
int maxPathSum(TreeNode* root) {
Info disAndHight = getMax(root);
return disAndHight.maxDis;
}
};
LeetCode二叉树中最大路径和
class Solution {
int res = INT_MIN;
int getMax(TreeNode* root) {
if (!root) return 0;
int left = max(0, getMax(root->left));
int right = max(0, getMax(root->right));
res = max(res, left + right + root->val);
return max(left, right) + root->val;
}
public:
int maxPathSum(TreeNode* root) {
getMax(root);
return res;
}
};
派对的最大值
x
a b c
- x参与：x乐 + a不乐下的最大值 + b
Morris遍历
一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1).通过利用原树中大量空闲指针达到节省空间的目的。Morris遍历会改变树结构。
没有左树只能遍历到一次，有的话能遍历两次。
void morris(TreeNode* root) {
if (!root) return;
TreeNode* cur = root;
TreeNode* mostRight = nullptr;
while (cur != nullptr) {
mostRight = cur->left; //第一步先走到左节点
if (mostRight != nullptr) { //有左子树
while (mostRight->right and mostRight->right != cur) {
mostRight = mostRight->right;
}
//mostRight变成cur左子树上最右边的节点
if (!mostRight->right) {
mostRight->right = cur; //第一次来到cur
cur = cur->left;
continue;
} else { //mostRight->right == cur
mostRight->right = nullptr;
}
}
//没有左树就直接往右走了
cur = cur->right;
}
}
大数据题目
有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL
- 可以使用布隆过滤器
- 哈希函数分流 某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天人们Top100词汇的可行方法。
- 小根堆：还是使用哈希分流然后再放到堆中再汇总 32位无符号整型，现有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。
- 位图：一个位只能表示是否存在，两个位就可以表示0次1次2次 可以使用最多10MB的内存，怎么找到40亿个整数的中位数
- 范围统计的思想：转换成数组长度且为2的整数次，如等分成2048份，遍历桶排序，计数 10G无序文件通过5G内存转换成有序的文件
- 小根堆(数据+词频)小根堆达到最大size之后不再改变，只会进行堆顶的比较，每一次遍历都可以取出size个最小的数据。
- 5G是为了确定堆的数量
位运算题目
给定两个有符号32位整数a和b，不做任何比较判断返回a和b中较大的数
//反转，n不是1就是0
int flip(int n) {
return n ^ 1;
}
//n如果是非负数就返回1，n如果是负数就返回0
int sign(int n) {
return flip((n >> 31) & 1);
}
int getMax(int a, int b) {
int c = a - b;
int scA = sign(c); //a-b为非负则scA为1，否则为0；
int scB = flip(scA); //scA为0，scB为1，scA为1，scB为0
//互斥返回
return a * scA + b * scB;
}
判断一个32位正数是不是2的幂、4的幂
取出二进制中的一个1看和他本身是不是相等
bool isPowerOfTwo(int n) {
return (n > 0) && (((n - 1) & n) == 0);
}
4的幂：首先是2的幂，有一个1在1、3、5的奇数位置
bool is4Power(int n) {
//...1010101
return (n & (n -1) == 0) && (n & 0x55555555) != 0;
}
给定两个32位有符号整数a和b，使用位运算实现加减乘除
- 异或^ 无进位相加
- 与& 表示：如果相加的话会产生进位信息1， 所以与运算之后再向左移动一位之后就是该位置上的进位信息（往上进位） 直到没有进位信息了就停止计算
15: 0 1 1 1 1
11: 0 1 0 1 1
--------------
^ : 0 0 1 0 0
& : 1 0 1 1 0
--------------
^ : 1 0 0 1 0
& : 0 1 0 0 0
--------------
^ : 1 1 0 1 0
& : 0 0 0 0 0
没有进位信息&了最终的^即为结果
int add(int a, int b) {
int sum = a;
while (b != 0) {
sum = a ^ b; //无进位相加
b = (a & b) << 1; //进位信息
a = sum;
}
return sum;
}
//只需要将b取反就是加法
int minus(int a, int b) {
b = ~b + 1;
return add(a, b);
}
乘法和十进制乘法是一样的，b如果是某一位是1就将a的数值左移一位，最后将所有对应的数相加
int multi(int a, int b) {
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res = add(res, a);
}
a <<= 1;
b >>= 1;
}
return res;
}
除法：尽可能向左但又不能超过
具有平衡性的树
有序表所有操作O(logN):红黑树、AVL树，SBTRree,这三者判断平衡性的标准不一样。其他操作差不多。
跳表
不考虑平衡性：默认搜索二叉树数值唯一。搜索二叉树不能自平衡。
搜索二叉树+左右旋 = SBTree/AVL
头节点倒向哪边就是怎么旋：头节点倒向左边就是左旋：让树变得平衡一点
LL：左子树的左边过长，做一次单次右旋
怎么判断该怎么旋：判断左右子树深度，依次查看是4种情况的哪一种
每加入一个或删除一个都检查是不是具有平衡性
SB树
平衡性： 每棵子树的大小，不小于其兄弟的子树大小。 每颗叔叔树的大小，不小于任何侄子树的大小
红黑树
- 每个结点要么红的要么黑的
- 头和叶子节点（null）是黑的
- 红点不相邻
- 每条路径上的黑节点一样多
跳表
key，value，指向外面数据的指针（多链表）
哔哩哔哩公司氛围 96人发布
投递华为等公司10个岗位
