• 取余运算规则
    (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背包：物品个数有限，每个含有价值，给定背包重量，问最大价值
    整数拆分：给定数组中能否拼出给定的和