前言
这里简单记录下
工作学习知识点总结
c++相关知识点
进程间通信
- 管道
- 命名管道
- 消息队列
- 信号
- 信号量
- 共享内存
- socket套接字
线程间通信
- 锁机制
互斥锁、读写锁、条件变量
- 信号量
- 信号
线程同步
- 临界区
- 信号量
- 互斥量
- 事件
topK
海量数据
快速排序
退化改进
二分查找
linux五种IO模型
tcp协议
redis常见问题
堆排序
- 大顶堆
- 小顶堆
应用场景
红黑树
常用容器的底层数据结构和时间复杂度
vector和map的底层实现
数据库
- 索引
- 幻读
boost
stl内存管理
- 一级配置器
- 二级配置器
其他问题
其他问题1
迭代器种类和作用，左值引用和右值引用区别，二叉树节点怎么找它的层数，lambda怎么用，容器的配接器有什么作用
线程数目是cpu核数
红黑树左旋右旋
数据一致性，数据库写挂了，怎么处理
指针和引用的区别
servlet和socket区别
哈希冲突
其他问题2
深拷贝浅拷贝
设计模式
拷贝构造函数的理解
智能指针
stl的组件(容器 算法 迭代器 仿函数 配接器 适配器)
c++11 thread
多态(virtual怎么实现的多态)
leetcode
- 并查集
https://zhuanlan.zhihu.com/p/93647900 - 动态规划
- BFS DFS 回溯算法
五大算法
https://www.jianshu.com/p/4abfd96d91e6
https://www.jianshu.com/p/48a6bdfccff1
- 递归分治
- 回溯法
- 动态规划
- 贪心算法
- 分支界限
递归、迭代和动态规划的区别与联系
定义
递归：程序调用自身，从顶部将问题分解，通过解决所有分解出来的小问题，来解决整个问题。
迭代：利用变量的原值推算出变量的一个新值。递归中一定有迭代，但迭代中不一定有递归。
动态规划：通常与递归相反，其从底部开始解决问题，将所有小问题解决掉，进而解决整个问题。
下面通过斐波那契数列对三者进行对比：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21…
递归公式：F[n] = F[n-1] + F[n-2] (n >= 3), 递归结束条件：F[1] = 1, F[2] = 1递归
自上而下调用函数本身，速度较慢，不推荐。
要知道第n个数，必须要先知道第n-1和第n-2个数；
而想要知道第n-1个数，必须要知道第n-2和第n-3个数。
f(n) = f(n-1) + f(n-2)
= f(n-2) + f(n-3) + f(n-3) + f(n-4)
= …1
2
3
4
5
6
7int Fibonacci(int n) {
if (n <= 2) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}迭代
利用原值去求解下一个值，一般比递归速度更快。
由第1个数和第2个数去求解第3个数；
由第2个数和第3个数去求解第4个数；
以此类推：
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
…1
2
3
4
5
6
7
8
9
10
11
12
13
14int Fibonacci(int n) {
if (n <= 2) {
return 1;
}
int f1 = 1, f2 = 1;
int res = 0;
for (int i = 3; i <= 3; ++i) {
res = f1 + f2;
f1 = f2;
f2 = res;
}
return res;
}动态规划
动态规划采用空间换时间的方法，速度比迭代更快一些。
子问题可能需要多次计算，即子问题的重接性质；
利用额外空间，将子问题的解保存起来，每个子问题只用计算一次，以节省时间。1
2
3
4
5
6
7
8
9
10int Fibonacci(int n) {
std::vector<int> dp(n);
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
印象笔记
1 | 变量的命名规则，运算符优先级，函数，递归，贪心算法，回溯，分治，动态规划（0/1背包），分支限界kmp，最小生成树，最短路径 |
