介绍

用于记录刷题笔记本，总结刷题技巧。

主题

Topic	Description
刷题记录	leetcode题目中的刷题记录
关键点记录	一些常见的题目技巧、问题、记录
liangkang233’s blog	个人博客主页

题目分析

注意节点释放内存需要把上层节点的指向子树指针置空。写遍历写成一坨shit。。。建议二刷

关键

序列：
1. 子序列元素相同并不代表是 同一子序列 ，只要子序列元素索引不同即为不同子序列，子集合 才是考虑元素不同（题目 891）
2. 子序列 是不要求连续的相对位置不变，而 子数组 和子串一样，是需要连续的
例如 12345678 的子序列可以是 1345678 子数组只能是 45678 之类的
二叉树：
1. 前序/后序+中序序列可以唯一确定一棵二叉树，只知道前序和后序不唯一确定参考 105.从前序与中序遍历序列构造二叉树蓝桥杯例题和 889.根据前序和后序遍历构造二叉树
2. 创建树的模板 createTree 297.二叉树的序列化与反序列化
3. 二叉搜索树使用中序遍历为升序或者降序
链表题目注意:
1. 舍得用变量，千万别想着节省变量，否则容易被逻辑绕晕
2. head 有可能需要改动时，先增加一个假head，返回的时候直接取假head.next，这样就不需要为修改 head 增加一大堆逻辑了。
3. 链表指针使用 next prev 来做 ++ – 操作。
leetcode输入测试：
1. 若是例如44.通配符匹配的类似多个string时外面还要加”“，例如输入s="io" p="io*"时，应该是输入 ""io"\n"io*""
  
  即测试内容包含字符串外面再包一个"" 类似的还有 ""***|**|*****|**||**|*"\n[[1,17]]\n"
2. 非文件的话多个参数使用\n分隔，文件的话直接回车分行即可。
常用函数表达式
1. distance(first, last) 函数求迭代器之间的距离 非随机访问迭代器例如set map 事件复杂度为 O(n) 739.每日温度此列题用map 做下标查找二分下标
2. 判断是否为字符使用 isalpha()
3. C++ 科学计数法表达数字(double) 0.01 => 1e-2; 100 => 1e2;
4. C++ std库实现的二分查找 lower_bound()返回第一个大于等于 upper_bound()返回第一个大于
5. size() 返回值为无符号数，其与负数相比较时负数会转为无符号数，所以判断结果会出问题。一定要在判断前转为int。
顺序容器中关于 emplace_back 用法还包含了vector 的 size reserver 的注意事项
找寻全部解时dfs效果比bfs效果好或者差不多，只需要一条路径或判断是否有效时推荐bfs。bfs(队列) dfs(栈)的具体实现可采用递归迭代，一般用递归好写点也好理解。dfs栈的状态如果会返回上次递归则算法就是回溯。
Set map 相关
1. map 基础语法包含 key_cmp 与 value_cmp 区别
2. map set 的自定义比较函数传函数而不是类
3. multiset是元素可以重复的有序队列，非常好用，会自动排序队内元素。（set是不会出现元素重复的有序数组底层红黑树，所以元素无需排序时尽量hash实现的unordered_set）跟优先队列的区别，这个分析的不错优先队列能否被set或multiset（c++语法）替换？ - 知乎 (zhihu.com)
4. multiset erase 删除值时会将所有相等值删除，erase单个迭代器才是删单个元素。查询该值范围时可用 equal_range 返回一个pair 指向头和末尾的后一个元素 erase输入两个迭代器删范围。
5. unordered_set 不能直接用pair做key，需要传入hash函数例如下参考1 参考2
```
struct SimpleHash {
    size_t operator()(const std::pair<int, int>& p) const {
        return hash<int>{}(p.first) ^ hash<int>{}(p.second);
    }
};
unordered_set<pair<int, int>, SimpleHash> myset; 
```
greater less 模板解析
字符串相关 stringstream、istringstream、ostringstream 三者的区别
常见容器 vector queue stack 双端队列:deque 双向链表 list
基本类构造重载 priority forrange 使用关于堆的自实现
C++格式的转换: static_cast dynamic_cast 比c的强转安全
C++ 类定义的函数方法要在类内使用需要 static 修饰举例 102行此处的自定义比较函数一般使用匿名函数
C、C++格式化字符串 , Jacky Walker (wukongcoo1.github.io) 可以实现前缀补0 等操作
在声明时可以不加形参名，定义时再加。且在类内声明static函数，类外定义时不要加static 示例 (声明时需要告诉编译器这是什么类型，但定义时，编译器会自己找声明C++中有很多类似语法：比如，默认参数列表，是声明的时候加默认参数，定义函数的时候不需要; 定义inline函数也是声明的时候加inline，定义的时候不加
动态规划背包问题总结:
1. 常规 01 背包 i j 遍历优化为1维需要 j 逆序 i 为背包种类 j 为背包上限
2. 多重 01 背包 i j k 遍历优化为1维需要 j 逆序 i 为背包种类 j 为背包上限 k为对应背包可以出现的个数
3. 完全 01 背包 i j 遍历优化为1维需要 j 正序 i 为背包种类 j 为背包上限
4. 完全背包归纳
LRU LFU
1. Least Recently Used LRU对于循环出现的数据，缓存命中不高
  
  比如，这样的数据，1，1，1，2，2，2，3，4，1，1，1，2，2，2…..
  
  当走到3，4的时候，1，2会被淘汰掉，但是后面还有很多1，2
2. Least Frequently Used LFU对于交替出现的数据，缓存命中不高
  
  比如，1，1，1，2，2，3，4，3，4，3，4，3，4，3，4，3，4……
  
  由于前面被（1(3次)，2(2次)）3加入把2淘汰，4加入把3淘汰，3加入把4淘汰，然而3，4才是最需要缓存的，1去到了3次，谁也淘汰不了它了。
类内 sort 调用谓词函数报错相关

出现sort() error: reference to non-static member function must be called 原因：sort()函数接受二元谓词，但是在类内定义的myCompare函数作为成员函数，实际上有三个参数，this指针、m、n。解决方案：
1. 将myCompare()函数挪到类定义的外面，即改为非成员函数；
2. 将myCompare()函数定义为静态成员函数，没有this指针。
3. 将myCompare()函数定义为类的友元函数，但是此时必须在类外声明该函数，否则，即使在类内定义了该友元函数，该函数仍然是不可见的。
求一堆点中曼哈顿距离最大的值
随机值问题：
- 如何等概率地从n个数中随机抽出m个数？__牛客网 (nowcoder.com)
- 382.链表随机节点无需注入srand随机种子
- rand使用方法 srand正确用法应该放在类的构造函数内，只初始化一次。
求所有质因数
B. Zero Tree 思维树形dp

leetcode-cpp

leetcode 刷题笔记

介绍

主题

题目分析

关键