基本数据结构

C++

vector<>：push_back(), pop_back(), begin(), end(), erase(),
stack<>:
unorder_set<>
map 默认排序，通过红黑树实现
set<>默认排序
unorder_map<>: insert(a, b)
set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。
遍历: for (auto mp: unorder_map<>) mp->first, mp->second
查找: mp.find(x); 是否存在mp.find(a)!=mp.end()
bitmap 二进制数组， flip反转数组，(int)small.to_ulong()转换类型
排序：sort(it.begin(), it.end(), less<>()||greater<>())
查找：lower_bound(ret.begin(), ret.end(), idx)
堆 priority_queue q(greater>(), move(num));
最大数值 max_element(）
1<C++内嵌函数: function 名称 = &{}
push_back() 与emplace_back()区别
在引入右值引用，转移构造函数，转移复制运算符之前，通常使用push_back()向容器中加入一个右值元素（临时对象）的时候，首先会调用构造函数构造这个临时对象，然后需要调用拷贝构造函数将这个临时对象放入容器中。原来的临时变量释放。这样造成的问题是临时变量申请的资源就浪费。
引入了右值引用，转移构造函数（请看这里）后，push_back()右值时就会调用*构造函数和转移构造函数。在这上面有进一步优化的空间就是使用emplace_back，在容器尾部添加一个元素，这个元素原地构造，不需要触发拷贝构造和转移构造。而且调用形式更加简洁，直接根据参数初始化临时对象的成员。

大小写转换 toupper, tolower
我们之前使用的typeid运算符来查询一个变量的类型，这种类型查询在运行时进行。RTTI机制为每一个类型产生一个type_info类型的数据，而typeid查询返回的变量相应type_info数据，通过name成员函数返回类型的名称。
vector容器可以使用insert在特定的位置扩展新的元素，当且仅当新的vector大小超过当前vector容量时，会导致分配的存储空间自动重新分配。

Java

ArrayList<>: add(), set(), get(), remov(int)
HashSet<>
HashMap
排序：Collections.sort(sites);
最小堆 PriorityQueue pq = new PriorityQueue(new Comparator(){}) 插入pq.offer(pair); 退出ans[i] = pq.poll()[1]
自定义排序
Collections.sort(nodes, new Comparator() { public int compare(int[] tuple1, int[] tuple2) {});
序列最大元素Arrays.stream(dist).max().getAsInt();

大小写转换Character.toUpperCase

相关算法

边界条件测试

  1. 对于有构造函数的代码考虑默认构造函数情况
  2. 考虑输入为负数，空值等情况

x & -x可以用来筛选二进制数中最后一位位置

其他

  1. 复制对象，如果修改原始对象需要对其进行恢复
  2. 对于排序数组使用二分查找

能使用公递归算法的情况下考虑记录中间结果，防止重复运算，即动态规划算法
仔细读题从数轴上找规律
注意输入是否有重复，是否能转换为有序数组进而进行二分查找
对于有序序列使用双指针或二分查找
对于状态有限的数列可以使用int中1的位置记录状态，节省内存使用空间
监控二叉树：动态规划与递归算法结合
每个节点记录三个状态a放置摄像头状态，b覆盖整个树摄像头最少数目， c覆盖两子数摄像头数目
状态压缩对于数量较少的使用bitmap记录结果Ingeter.bitCount(mask)/__builtin_popcount(mask)统计1的个数
接雨水问题

  1. 分别统计两侧最大值最小值，或使用单调栈保存最小值
  2. 双指针解法，使用双指针同时遍历左侧与右侧的最小值

办公室问题II

计算时间段的重合问题

  1. class Solution {
  2.     public int minMeetingRooms(int[][] intervals) {
  4.     // Check for the base case. If there are no intervals, return 0
  5.     if (intervals.length == 0) {
  6.       return 0;
  7.     }
  9.     Integer[] start = new Integer[intervals.length];
  10.     Integer[] end = new Integer[intervals.length];
  12.     for (int i = 0; i < intervals.length; i++) {
  13.       start[i] = intervals[i][0];
  14.       end[i] = intervals[i][1];
  15.     }
  17.     // Sort the intervals by end time
  18.     Arrays.sort(
  19.         end,
  20.         new Comparator<Integer>() {
  21.           public int compare(Integer a, Integer b) {
  22.             return a - b;
  23.           }
  24.         });
  26.     // Sort the intervals by start time
  27.     Arrays.sort(
  28.         start,
  29.         new Comparator<Integer>() {
  30.           public int compare(Integer a, Integer b) {
  31.             return a - b;
  32.           }
  33.         });
  35.     // The two pointers in the algorithm: e_ptr and s_ptr.
  36.     int startPointer = 0, endPointer = 0;
  38.     // Variables to keep track of maximum number of rooms used.
  39.     int usedRooms = 0;
  41.     // Iterate over intervals.
  42.     while (startPointer < intervals.length) {
  44.       // If there is a meeting that has ended by the time the meeting at `start_pointer` starts
  45.       if (start[startPointer] >= end[endPointer]) {
  46.         usedRooms -= 1;
  47.         endPointer += 1;
  48.       }
  50.       // We do this irrespective of whether a room frees up or not.
  51.       // If a room got free, then this used_rooms += 1 wouldn't have any effect. used_rooms would
  52.       // remain the same in that case. If no room was free, then this would increase used_rooms
  53.       usedRooms += 1;
  54.       startPointer += 1;
  56.     }
  58.     return usedRooms;
  59.   }
  60. }

矩阵置零

本地方法，将其中第0行作为记录，此时存在修改则使用额外参数记录该是否置零

最大子正方形

通过分析矩形特点分为子问题，即上，左与左上最小值+1

C++二分法查找上界：upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin()

连续1的非负整数个数

使用动态规划算法构建使用构建字典树，其中为高度为多少字典树连续1个数
层次查看方法计算分别计算左右子树
image.png

因数分解

通过短除法进行因数分解，如题650中，使用因数分解计算最小复制次数

  1. for (int i = 2; i * i < n; i++){
  2.     while (n % i == 0)
  3.         n /=i;
  4.         ret += i;
  5. }

动态规划问题

  1. 寻找递归关系
  2. 对递归关系进行化简

见题629https://leetcode-cn.com/problems/k-inverse-pairs-array/solution/kge-ni-xu-dui-shu-zu-by-leetcode-solutio-0hkr/

水塘抽水

https://leetcode-cn.com/problems/random-pick-index/solution/sui-ji-shu-suo-yin-by-leetcode-solution-ofsq/
通过o(n)的复杂度从数组中抽取目标的随机抽取，通过计算该数cnt与随机数是否能整除决定是否选取该数值。

约瑟夫环

https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/solution/by-huang-bin-bin-7-zvh1/
通过反向推到的方法节省空间占用，避免递归
(f(n - 1) + m) % n