Leetcode笔记
- 取余运算规则
(a + b) % p = (a % p + b % p) % p
由递归式可得：F(N) % 1e9+7 = (F(N-1)%1e9+7 + F(N-2)%1e9+7) % 1e9+7 - 并非所有容器都使用sort算法
既然问的是STL的sort算法实现，那么先确认一个问题，哪些STL容器需要用到sort算法？
首先，关系型容器拥有自动排序功能，因为底层采用RB-Tree，所以不需要用到sort算法。
其次，序列式容器中的stack、queue和priority-queue都有特定的出入口，不允许用户对元素排序。
剩下的vector、deque、array，适用sort算法，因为标准库中的sort要求iterator类型为random_access，只有这三种容器是。
array、vector、deque、set/multiset、map/multimap、 unordered_set/unordered_multiset、unordered_map/unordered_multimap
不带sort()成员函数，如需使用，可以调用sort()全局函数
list、forward_list()带sort()成员函数 - 实现逻辑
STL的sort算法，数据量大时采用QuickSort快排算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。如果递归层次过深，还会改用HeapSort堆排序。
- 实现逻辑
- 优先队列里的数据并不是排序的，因为它的底层可以用vector、array、deque等数组实现的容器，这些容器中的数据并没有排序。只不过优先队列设置了优先级，使数据出队的时候按照你想要的顺序出。
- 注意输出数据的类型转换，int转为double等，除法尽量写成乘法，加上static_cast
- //int mid=(r+l)/2;
防止溢出：int mid=l+((r-l)>>1);（归并排序中） - (target - 1) / 2 等效于 target / 2 下取整
- 使用动态规划解决问题一般分为三步：
表示状态；
找出状态转移方程；
边界处理。 - 常见的逻辑运算符有三种，即 “与&&”，“或∣∣”，“非!” ；而其有重要的短路效应，如下所示：
if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false
if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true - 动态规划
零钱兑换：硬币数量不限，给定金额，问所需最少硬币数量
零钱兑换II：硬币数量不限，给定金额，问有多少种兑换方法（完全背包问题，硬币数量不限）
0-1背包：物品个数有限，每个含有价值，给定背包重量，问最大价值
整数拆分：给定数组中能否拼出给定的和
拼多多集团-PDD公司福利 470人发布
