My notes and solution for leetcode problems.
Top- 常用文档
- String
- List
- Hashmap
- Linked List
- Tree
- Trie
- Graph
- Heap
- Stack
- UnionFind
- SegmentTree ----
- Math
- Prime
- Sort
- PrefixSum
- BinarySearch
- SlidingWindow
- TwoPointer
- DFS
- BFS
- DP
- Greedy
- SQL
- OOD
collections, heapq, itertools, bisect, sortedcontainers,
O(n): Greedy, stack, bfs, dfs O(n logn): sort, binary, tree like, heap O(n^2): dp, Dijkstra
从每一个下标出发，以他为中心，检查奇数长度和偶数长度发的 substring 是否为 palindrome。还可以用 dp，dp[i][j]表示 s[i:j]是否是 palindrome。
先转成 str 然后 reverse 再拼起来。用到 rjust 来限制不会超出 64 位。用到 _ (1 - 2 _ (x < 0))来判断正负。
s.zfill(n)可以在头部加 0 把 string s 补到 n 长度。补齐 a b 之后就对应位相加，根据结果看这一位最后结果以及是否要进位。加完之后最后看看有没有多余的进位。
直接对每个长度可以被 s 长度整除的 substring 复制到和 s 一样长然后比较是否相等。
简单，检测到回文串就加一就行了。
easy.
直接过一遍 str，让频率高的放在第一个，9 个 button 放完了就放第二个，依次。每放一个字母就 count += number of ch in str * 字母在 button 里的位置。
简单，不过注意字符串里插入变量的格式：'str%格式'%(插入的东西)
先过一遍找到每个连续 0,1 的开始下标和连续长度，然后对所有连续 0 找对应的下一个相邻连续 1，取 res = max(res, min(连续 0 长度，连续 1 长度) * 2)。
不能有 palindrome，就是不能有任何偶数及奇数长度的 palindrome，就是不能有任意长为 2 或 3 的 palindrome，就是任意连续两个或三个字符不能相同。先把字符都转成 ascii 码，方便递增。因为是下一个最小的，所以从后往前递增。如果一个字符递增到了 k，说明要进位，就看前一个字符，当前字符先不管。如果不进位，且当前字符和前两个字符都不同，就把后面的依次放上 0， 1， 2 里面最小的且和前两个不同的字符。最后把数字转成字母。也算 greedy 吧。
用数字记录字母，然后从第一个非 0 开始到他后面的第一个 0 为止，所有减 1，然后再转成字母。注意这个 window 的边界条件。
简单，直接依次检查每个位置是否一样。
用 count 记录目前见到过的不同数字的个数，往后检查，碰到新的数就放到 nums 的 count 位置上，count 加 1。
简单。不等于 val 的元素往前放，等于的不管就行了。
简单，三个 list 代表行，列，块，其中元素分别表示第几个。然后每个数字往里放，放的同时检查这一行，列，块是否已经有这个数字了。
先按区间起点排序，然后依次检查，如果当前的起点在前一个区间内就更新终点为两个区间里终点大的那个。
list 的基本操作，先取集合去重然后排序，从小到大依次检测，和前一个相同就当前 sequence 加一并更新 res，不同就重置当前 sequence。
简单，直接按空格分割，然后翻转再拼接
直接过一遍 nums，如果和前一个相差大于一则 ans.append 一个数或一个区间。注意 corner case，比如 nums = []，以及 lower 和 upper 处的情况。
简单，直接根据 . 分割字符串，然后依次比较。
这里因为 A-Z 是用 1-26 编号的，所以每步都减 1，让余数范围变成从 0-25。商的部分不变或者只是把余 0 的部分变成 A。注意 ord()可以把字符转成 ascii 码，chr()把 ascii 码转成字符。
直接过一遍，检查每个 meeting 的开始时间是否早于前一个的结束时间。
简单。过一遍记录数字，再过一遍找到没记录的数字。
简单。碰到非 0 的就往 list 前面放，同时 count+= 1，最后从 count 到 nums 末尾改成 0。
依次检测 abbreviation，看到数字就加到 num 里，看到字母就检测。最后看是否检测到 word 的尾部了。
其实很简单。要想到增加 n-1 个数等价于减少 1 个数。然后算每个数跟最小值的差就行了。
因为从左往右递减的序列没有比他更大的，所以对这个数从右往左找，找到第一个左边比右边小的数，左边是 i。从这个 digit 再往右走，找到最右边的比他大的 digit，j，交换这两个 digit。然后 reverse 从 i + 1 开始到最右边的 digits。
先过一遍，用字典记录每个数字的频率，第一次和最后一次出现的位置。再过一遍字典，更新 max_fre 和 min_len。
还有个时间 O(N), 空间 O(1)的方法。记录 currMax, possibleMax, length。如果当前的小于 currMax，就说明当前元素必须在左边，所以更新 currMax， possibleMax 和 length。
简单，把棋子填进去然后检查谁赢了。
简单，easy 题。
因为只有两个字母，所以只要算其中一个字母不在正确位置上的最小位置数就行了。取两个字母里面这个数更小的那一个。
直接算出时针和秒针的角度，然后取差的绝对值，再取跟补角里更小的那个。
交替 append list。
先从后往前过一遍记录到每个下标为止的最小值，然后从前往后，每步记录到前一个为止的最大值，比较当前与相邻的大小以及和前面所有的最大值、后面所有的最小值的大小。
easy，一个指针过一遍，比较当前元素和之前最小元素，更新当前最小元素。
直接求和然后减去 armor 和 max(damage)里的最小值表示抵消一次攻击。完全是 easy 啊为什么会是 medium。
用 Pascal Triangle 即组合数来算每个数在最终答案里用到的次数，然后直接一个个加上去。注意算组合数的时候要用//不要用/，不然后面会小数位有问题。也可以直接 recursive 做，不过很慢。
直接排个序然后从小到大分就行。
先排序，然后依次处理值不一样的元素，被减去的值等于 max(nums)的时候就结束。
直接 brute force。对所有可能的列的组合，分别检查每一行是否有没有被 cover 的 1。如果这一行所有 1 都被 cover 了当前列组合的 cover 数加一。取所有组合里 cover 数最大的那个。
直接过一遍，用 set 记录，看到已经存在的就 res += 1 并重置 set。
easy
要发现不同组合的规则。(0, 0) -> (0, 0)，(1, 0) -> (1, 1)，(0, 1) -> (1, 1)，(1, 1) -> (1, 0)。所以只有 0 的情况无法改变，只要有 1 个 1，就可以修改成任何情况。所以只要检查 s 和 target 是否同时全为 0 或者同时都含有 1 就行了。
简单，每行过一遍就行了。
和前一题基本一样。
简单，brute force 就行了。
每改一个数只会影响当前位置和前一个位置的 adjacent element。所以就依次过一遍 query，每个 query 只看两个位置的变化就行了。
简单题，直接取余数就行。
标得 medium 不过实际 easy。依次根据 derived 判断当前位置是否取反就行了。
从中间往两边出发，每次保存对称位置上更小的那个元素，最后再把保存了的都拼起来。
直接暴力解，每个数都算一遍所有组合看满不满足 punishment 条件。
分别让左半边和右半边一样，然后根据奇偶还有中间元素和中间元素两边是否相同判断最后的和。
简单。
简单。
转 n 圈，每次更新每个位置上的最低 cost 加上转到这一圈需要的转圈 cost，每一圈都保存当前最低总 cost，最后输出。
简单，找不是最小最大值的。
根据操作次数 k 减去 k _ num2，剩下的就是由 2i 组成的部分。bit_count()可以看 int 的二进制表示里面有几个 2i。k 最小要大于等于这个 bit_count()，因为这样才能组合出来；最大要小于等于 num1 - k _ num2，因为每次操作最少会减去 1，所以最大不能超过剩下的数。从小到大遍历 k，检测到一个符合条件的 k 就输出，没有的话就 return -1。
首先得到整个 array 的 mex。然后找到第一个使得当前 currMex 等于 mex 的位置，同时在 count 里减去已经用过的元素。然后在更新过的 count 里找到 nextMex，然后重复上一步。
用 hashmap 储存与当前值的和为 target 的值，以及当前值的 index。继续查找每一个值，如果在 hashmap 里就输出储存的 index 和当前的 index。
跟 2sum 基本一样，先排序，然后对每一个值把他当成 2sum 里的 k，然后对之后的做 2sum，依次重复 n 次。
和 3sum 基本一样。另外这里面两个外部循环都有 if i == 0 or nums[i - 1] != nums[i]，是用来避免重复计算的。
对每个 str 排序作为参照物，如果之后的 str 排序后和这个一样就说明他们是 anagram。
跟 Two Sum 一样，不过把 hashmap 的值的 index 换成了 count，因为只要找到是否有就行了不要下标。然后用 count 可以避免重复访问同一个元素。
简单。两个 string 分别放到 Counter 里面去，然后看 ransom 的是否包含在 magazine 的 Counter 里面。
两个 map。一个保存 key, (frequency, value)对，一个保存 frequency, keys 对。key 是 OrderedDict。根据 key 查找 frequency，更新两个 map。同时维护当前有 key 的最小频率。
用一个 hashmap 记录到每个下标为止的子串合对应的子串数。对每个新下标，count 加上合为 当前子串合 - k 的子串数。
先过一遍 group，找出每个 size 都有哪些人，然后对每个 size 里的那些人按 size 大小分组。
用到了 Counter 和 SortedSet。先过一遍 Counter 统计每个字母出现了多少次，然后过一遍 Counter 统计每个出现频率的字母有多少个。然后把出现频率放到 sortedSet 里，从大到小，把每个出现频率的字母减少字母个数减一个，然后如果出现频率大于一（说明可以减少该字母）且该出现频率对应的字母数也大于一（说明确实有字母被减少了），那就在该频率减一的频率上加上该频率对应的字母数减一（因为有一个字母没有被减少）。
跟 2sum 基本一样。不过用 count 来记录，然后每碰到一个匹配的就 count--，res++
和 2sum 差不多，在每个 string，count 先加上 memo 里面记录的个数，然后对比 num 和 target 的 prefix 或 suffix 是否一样，一样的话就把 target 去掉 num 的那部分加到 memo 里去。
得到 k 的下标，计算到 k 右边每个下标为止大于小于 k 的数的个数并保存在 hashmap 里；然后从 k 往左边一样计算，根据 hashmap 里的个数，加起来等于 0 或 1 的个数，就是从这个下标开始满足条件的 subarray 个数。
要想到 beautiful subarray 就是 subarray 的依次 xor 等于 0 的意思。然后就是跟 560 一样了，用字典储存到每个位置的 xor 总和，然后每个新位置查一下字典里等于当前 xor 的个数，加到 count 上就行。这样从之前到当前位置的 xor 就为 0 了。
按余数分类，同时记录当前余数个数。然后 q 从 0 开始，再 r 从 0 到 value - 1，遍历余数集，直到余数集里找不到下一个，就是不存在的，然后返回 q * value + r
先过一遍，统计每个元素的行列。然后根据 array，在每个位置对应的行列 count+1。然后如果有达到填满某一行或者某一列的就返回这个位置的 index。
两个 hashmap，分别记录每个数的频率和每个频率对应的数。每次增减都更新这两个 hashmap。
简单，基本就是 2sum。
创建一个新链表，如果 l1 或 l2 后面还有就继续延长这个链表
先过一遍确定 node 个数，然后再过一遍数到需要改变的位置。
简单，建一个新 head 然后根据 list1 和 list2 大小一次往 head 后面加就行了。
merge sort 的方法做，分成两部分然后 merge 两部分分别的结果。
把比 x 小的和大于等于 x 的元素分别放到两个 list 里然后再现重新生成一个 linkedlist。
我用的简单的先复制再建立联系，可以用 recursive 的方法直接在复制的时候就建立联系。
遍历链表，把见过的放进 set，之后如果碰到之前放进 set 过的就是 cycle，否则不是。
遍历链表，放进 list，然后按 list 的下标依次交替改变 next 指向的元素。
用双链表做。保存 head 和 tail，然后自己写一个 addNode 和 removeNode 函数。另外用一个 dict 保存 key 和对应 node 的指针。get 的时候删掉对应 node 并再次加到头部；put 的时候如果已经在里面就删掉，然后如果 dict 还是满的就说明 put 的是新元素，删掉 tail 前的 node，然后再把新 node 的加到头部。
简单。head.next 存在时每一步把当前的 next 指向 prev，然后更新 prev 和 head。最后把最后的 head 再指向 prev。
过两遍 linkedlist 乘 10 相加，然后加起来再除 10 取余从尾到头建个新 linkedlist。
根据剩余总数和剩余组数，如果能整除下一组就有正好整除那么多个 node，不能的话就是整除向上取整那么多个。
先过一遍按正负分到两个 list 里，然后再按顺序连起来。
写一个 helper 生成两个数之间的所有二叉树，然后以每个数为 root，递归他的左右子树，然后组合起来以这个数为 root 的树。
简单，用 q 记录每个 node 和对应 depth，每一步更新 depth 就行了。
写一个 helper 算从每个 node 开始的子树下的 max path sum 和以这个 node 为终点的最大 path sum。然后返回 helper[0]就行了。
跟下面一个基本一样，不过利用了 BST 的结构，直接判断当前节点的值，如果在 p，q 之间就是找到了，小于更小的或者大于更大的就去另一边找。
用一个 helper 判断在当前子树中是否检测到 p 或 q。在 root，helper(root.left)，helper(root.right)中如果有两个检测到了就是找到了 LCA，修改全局变量 self.ans。每一层返回 curr or 上面两个，这样就算找到了 LCA，后续返回的也是 True 就是 1，之后不会重复修改全局变量。
dfs(node)返回当前 node 下的所有 path。然后每一步返回左右 child 的所有 path 再和当前的拼接起来。
dfs 一遍检测是否能遍历整个图，然后看是否是树（边数等于点数减一）。
直接分别取 left boundary, leaves, and right boundary。
用每个 num 前两位表示一个 node，然后建 dict 储存值。dfs 根据 node 数值关系遍历，到每个 node 就在当前和上加上当前 node 的 value。然后到 leave 的时候就在 self.ans 上加上当前和。
两个 dfs。先 post order，从下往上，更新每个 node 所在子树的节点数和子树中到该 node 的所有距离和。依次往上更新。这之后 root 的就已经是 root 到所有其他 node 的距离和了。然后 pre order，用 parent node 的 ans 去更新 child 的 ans。
recursion 做，对 n 个 node 的树递归左右子树从 0 到 n - 1。同时用一个字典记录 n 个 node 的树的所有组合方式，之后递归到的时候就不用重复计算。
bfs 找到 deepest leaves，并记录每个 node 的 parent。从最底层的 leaves 开始，回溯 parent，直到只剩某一层一个 parent。
已经把 parent 给出来了，直接把到 parent 的 path 打出来，然后找到 path 上最后一个相同的 node。
和基本情况差不多，不过这次不是检测是否只有两个，而是检测是否所有 node 都被在当前子树下找到了。
做个辅助函数，在树里找到对应元素并记录路径。只有找到对应元素才会返回 True，否则都返回的是空 list，所以只有找到了才会记录 path。并且是倒着记录的。然后把 start 和 dest 相同的 prefix 去掉，这里就是从 LCA 开始的路径了，到 start 的都替换成 U，再加上到 dest 的路径就行了。
用两个 queue 按层 bfs 遍历树，然后对每层求 min swap。重点是 min swap。注意 iterative traversal 的时候就用普通 stack 就行，然后先后顺序反过来。
在每个点让他的左右子路径相等。res 加上左右子路径的差，然后更新这个点的 cost 到本来的 cost 加上子路径的 cost。
拓扑排序，能被排的就是可以直接做的。然后找到剩下的点里面的所有圈，每个 cycle 可以做 cycle 点数 - 1 个。
就是 nested hashmap。一开始就是一个{}，每一层就加一个 key，每到一个终点就在终点的 hashmap 里加一个'$'的 key 表示到达终点了。
用 Trie 保存加进去的 word，然后每次 search 检查。
先用一个 trie 记录所有 word，然后从 board 的每个位置开始 dfs。如果在 trie 里找到了，就去掉这个词。如果某个叶节点到底了而且已经找到过了，就去掉这个叶节点。
Trie 里有三个东西，isFile 看这个是 file 还是 directory，children 保存当前目录下所有 file 和 directory，content 就是 content。查找 path 的时候直接往下一路走就行了，因为 childer 是一个 defaultdict，如果不存在会自动新建一个。
用 Trie 记录 product，并在每一层用 suggestion 记录三个词，然后对 word 每个字母到每一层的时候直接访问对应的 suggestion。还可以用 sort + binary search。
先预处理一遍，每个 bus route 当成一个 node，建立 node 之间的边，然后再 bfs。预处理的部分可以优化。
先排序，然后用 Kruscal 找出一个最小生成树并记录这个树的最小权。然后对每个边考虑不带这个边和强制带这个边，再用 Kruscal 看是否能组成等于最小权的最小生成树，来判断这个边是否是 critical 或 seudo critical 的。把 union find 写成一个类，方便后面每次 Kruscal 里方便调用。
简单，统计一下每个 node 的度然后暴力就行了。注意相连的 node 的 network rank 要减一。
拓扑排序，排序路上经过的入度为 0 的点就是可以的 recipe。
记录每个 building 的左右边到 edges，然后排序依次过。每个边先把在 edges 后面同一位置的 edge 加进 heap，然后把 heap 里小于等于当前位置的右 edge 都清出去。等于的也要清，因为只记录左 edge，不清的话可能会影响后面的。然后就把 heap 里最高的记录到 res，如果和 res 里前一个 height 不一样的话。
Use a heap to keep the end time of each room. Process meetings by their start time. If the start time is earlier than the earliest endtime, then it means more room is needed. Otherwise just allocate the already finished room to the current meeting. 只用保存每个 meeting room 的结束时间就行了，如果新的 meeting 在某个结束后才开始就直接替换那个结束时间，即把新的 meeting 安排在旧的 meeting 后面。
建一个最大堆和一个最小堆，保存他们的大小，每次有新的数进来就让他进最小或最大堆，保持最大堆和最小堆个数相等或者多 1。
先算出每个字母的出现次数，然后依次把出现次数最多或第二多的 append 到末尾。用 heap 来看出现最多的字母。
实际是用 sortedlist 做的。还可以用 segment tree 做。先记录所有 query 的 start 和 end 以及对应 query 的 index，还有类型用来区分这是 start 还是 end。比如(start, index, type)。sortedlist 是想象所有区间叠在一起，然后按 index 先后区分区间里数轴的距离。一根垂直于数轴的竖线扫过去，碰到 start 就把对应区间的 index 放入 sortedlist，遇到 end 就把对应区间的 index remove。然后每一步把 res 里对应 sortedlist 里最小的 index 那一个增加。如果是按数轴上一个个点移动的竖线就每次加一，因为是一步步移动的。如果是按记录下来的每个 query 来移动，就可以每次加上 pos 对应 start/end，减去 last_pos 就是前一个 query 的 pos。
先得到所有正数的和，这是可能得最大和。然后开始去掉和里的正数，或者加上剩下的负数，这两个都等价于从最大和里减去 nums 里的绝对值。因为是从最大和往下，所以把 nums 按绝对值排序之后依次减去每个值，并且每一步考虑加上 nextSum - absNum[idx + 1]和 nextSum + absNum[idx] - absNum[idx + 1]两种情况，即是否减去下标 idx 的值。每一步的结果都放到一个最大堆里，下一步再从最大堆里取，保证了是从 maxSum 依次往下递减。absNum 排序过，也是用来保证 maxSum 依次递减。
用两个 min heap，一个保存可以用的房间，一个保存使用中的房间，以结束时间为关健字。每一步先把结束时间小于当前开始时间的都挪到可用房间，如果当前有可用房间则直接用，没有的话则推迟当前 meeting 到下一个可以用的房间为止。
用 heap 记录每个位置左边和右边最小的 k 个数，然后用 list 记录里面最大的那个数。然后对每个位置 i，如果他比前 i - 1 个里面最小的 k 个大，也比后 i + 1 个里面最小的 k 个大，就满足条件。
模拟，以 arrival time 来划分时间段。每次把下一个时间点到达的人都加到 in 和 exit 的 heap 里去，然后从这个时间点再到更下一个 arrival time 之间根据 rule 通过门。
Dijrastra 的想法，因为所有 special road 的终点从任何起点都是可达的，所以里面每一步都要更新到所有重点的距离。每次取出最小距离，然后更新先到这个点，然后走到其他 road 的起点，然后再走 special road 到相应终点的距离。最后 res 返回先到每一个终点，再正常走到 target 的距离，这些的最小距离。
stack 记录正括号，对每个反括号用字典取正括号看是不是在 stack 末尾，且 stack 不空。最后检查 stack 是否空。
用 monostack 做的。brute force 就是看每个 index 左边和右边最高的，这个 index 处可以 trap 的就确定了。然后可以先记录每个 index 左边和右边最高的，相当于一维 dp。stack 不太一样，算的是从当前 index 往左，横着填充。找到前一个比他小的作为 base，然后再找更左边的一个，当前和更左边的就组成了 bound，就可以横着填充。如果更左边的依然比当前小，就继续往左边看并填充。
按/分割，然后根据.和..决定 pop 还是不管还是加入 stack，最后用/连接。
可以用 stack 是因为实际只有 n 个 rectangle 要检查。对每个 height，以他为高的最大 rectangle 的两边就是从他向左向右到第一个比他矮的位置。。假设已经有一个 stack，里面放着从低到高排列的 height，检测到新的 height 比 stack 末尾的 height 低的时候就开始依次 pop 这样当前位置比 stack 末尾矮所以构成他的右边。因为 stack 是从低到高，所以每 pop 一个 stack 里的前一个就是他的左边。pop 直到当前 height 不比 stack 末尾小。到 heights 末尾再把剩下的全部 pop 出来。
对每一行，保存到当前位置为止的连续 1 的个数。然后叠起来，从列来看，每一列就是一个 histgram，就转化成了上一题 84。所以预处理出 n 个 hist 之后，只用再对每一列做一次 largest rectangle 就可以了。
operand 保存当前的数字，res 保存当前计算结果，sign 保存当前符号。碰到数字就更新 operand，碰到加减号就根据 operand 和之前的 sign 运算更新 res，然后更新 operand 和下一个 sign。碰到(就放到 stack 里，碰到)就更新 res 来结束当前括号内的运算然后从 stack 里 pop 出前面的 sign 和 res。
碰到数字就更新当前数字，碰到符号表示当前数字结束，根据前一个符号进行操作。前一个符号是加减号就根据符号正负 append 到 stack 里，并更新下一个符号为当前符号。前一个是乘除就直接对 stack 最后的和当前数字进行运算，然后再 append 回去。最后对 stack 求和。
让 stack 里保存到当前位置为止的最小 substring。如果当前元素不在里面就放进来。每次新元素进来，把前面 stack 里比这个大的且后面还有的 pop 出去。
用两个 stack 分别保存括号外面的数字和字母。碰到[就把当前的数字和字母加到 stack 里，然后碰到]的时候就把当前字母乘上数字 stack 里最后一个的倍数，再在前面加上字母 stack 的最后一个。
首先预处理一个 monostack，找到每个数的 nextGreater。每步从末尾 pop 出 stack 里比当前元素小的元素的下标。用字典记录那个元素:当前元素。然后过 nums1，在字典里找相应的元素。
过一遍 monostack，每次 pop 出比当前小的元素的下标并更新那些元素的 nextGreater。更新完之后把当前下标放进 stack。再过第二遍，这样之前 nextGreater 在左边的也可以被更新了。
用 stack 记录 asteroid， 每个新的如果往右那么不会和 stack 里已有的碰撞，直接加进去；如果往左就一直碰撞到自己消失或者没有可以碰撞的为止。
简单，每次 pop 出比当前低的 temperature 的下标就行。
和 769 完全没区别啊。
保存一个递增 stack，里面每个数就是一个 chunk 的最大元素。每次把大于当前元素的都 pop 出来。当前元素前面比当前大的元素都必须和当前元素在同一个 chunk 里。
和 227 差不多，不过碰到(的时候重置 previous operator 到+，开始新的一个 term。因为前面肯定有其他符号，所以不用处理 curr。然后碰到)的时候就说明一个 term 算完了，把 stack 一直 pop 并加到 curr 直到碰到一个 operator。更新 previous operator。最后再把 stack 里剩下的所有 term 求和。最开始可以在 s 后面加一个@或者其他任意不会碰到的字符，这样不用单独处理碰到尾部的情况。
也可以用 divide conquer 做。不过这里用 stack。记录当前 frame 的 score，如果是(就是 0，是)就把当前 frame*2 再加到更前一个上面。
保存每个 price 和他前面小于等于他的 price 的个数。每次把 stack 末尾小于等于当前 price 的 pop 出来就行。
过两遍数组，找到每个元素右边第一个比他小的元素的下标，以及左边第一个小于等于他的元素的下标。在这两个之间，所有数组都以他为最小值。所以再过一遍数组，求这两个下标之间，包含这个元素的总数组数就行了。
先过一遍 linked list，然后用单调栈来在每个数依次把单调栈里比他小的 pop 出去。
排序，atack 从小到大，defence 从大到小，然后从后往前遍历，保存目前见过的最大 defence。因为 atack 从小到大，所以往前走的时候 atack 一直变小。因为 defence 从大到小，所以不会出现倒挂的情况。 还可以用 greedy，就是先过一遍，找出对每个 atack，比他大的那些 atack 里面，可能的最大 defence。然后再过一遍，对每个 atack，查找比他大的 atack 里面的最大 defence 是否比他自己的 defence 大。
维护一个 decreasing stack。每次从 stack 末尾开始把高度小于等于当前高度的 idx 都 pop 掉。
和 907 基本一样，不过这次要对每个元素，同时找出以他为最大值的数组数和以他为最小值的数组数。每次这两个相减就行了。
条件翻译过来就是可以跳到下一个大于等于当前元素或者小于当前元素的位置。用两个 monostack 记录每个元素下一个大于等于或小于的下标。每到一个新位置，pop 出 monostack 里小于或大于等于新位置的元素的下标，然后用 list 记录被 pop 出的位置的下一个大于等于或小于为当前位置。最后 dp，从头开始，看每个位置的下一个大于等于或小于的元素的下标，然后更新相应位置的 dp。
直接一个 stack 往前走，碰到*就 pop 就行了。
写的是 dp，不过其实是 stack，因为只有一维。对每个字符，根据他前面的字符分类讨论就行了。
用 stack，从头往后，监测到 AB 或者 CD 就 pop。
先排序，然后按照 position 顺序从左到右，用 stack 记录已有的 robot，如果新加进来的是往左的就一直和 stack 末尾往右的 robot 碰撞，直到末尾不往右或者其中一个消失。一开始排序的时候记得把原来在 position 里的顺序也记录一下，最后按这个再排一次序，然后输出每个 robot 的 health。
可以用来检查集合连通性。
对每个石头，连接他的 row 和 col。因为 row 数有限，所以 col 直接+10001 就行。最后检查有多少连通集。
把每个格子分成四个三角形，根据每一个位置是\或/或者空格，连接格子里的三角形。然后连接相邻格子的三角形。最后统计有多少三角形的 root 是他自己，即连同集个数。
用 unionfind 做的，但里面废操作太多了。可以用 bfs，每次开始 bfs 的时候设置一个 boolean isclosed = True，之后如果碰到边界就改成 False。这样依次 bfs 就可以了。
找出不联通集的个数，返回个数减一。
用 union find 来记录 alice 和 bob 的边是否都是连通的。最后检查加进去的边是不是等于 n - 1。这里 UF 用的是一个列表，因为正好 node 都是从 1 到 n 标记的。用 dict 也可以，就是中间复制的时候要手动写一个 deep copy。
先预处理，对 threshold 到 n 的每个数字用 union find 建立连通分量，然后每个 query 判断是否在一个等价类里面。
先对 queries 和 edges 分别排序，然后对每个 query，把 distance 小于当前 query 的 limit 的那些 edge 用 union 连起来，然后用 find 判断当前 query 的 p 和 q 是否连同。因为只连接了小于当前 limit 的所有边，所以直接判断就行，不用另外看每个边的 distance。
对每一个 node 做 bfs 就可以得到最大 group 数。用 union find 来记录连通分量。其实不用 union find 也可以，只要记录了连通分量就可以。
先找到连通集，然后看每个连通集是否是 complete 的。
最基本的构造 segment tree。用列表构造，tree 的 root 在下标 1 的位置。bottom up 递归构造，update 和 query。query 的时候 left 和 right 往中间缩，如果 left 是右 child 或 right 是左 child 就说明其 parent 包含不属于这个区间的数据，直接把 left 或 right 的值加上去然后再往上多走一层；否则说明其 parent 完全包含在区间内，不用加，直接移动到 parent，然后下一步再次判断区间范围。要 loop 到 left = right 为止，因为最后这个区间也要加。因为最后这个区间只可能是左/右 child 其一，所以不会重复计算。
只要(的个数大于)的个数就可以在后面加)。只要(的个数不超过总括号的个数一半就可以在后面加(。就根据这个规则对 queue 里的每个组合继续往后加括号就行了。
有点繁琐。对矩阵分层，然后每层依次转四个元素。
暴力会超时，所以根据 n 的二进制表示来考虑结果里有哪些 x 的二次 power。可以用 bitmask 或者 recursion。从小到大可能会超出 float 范围，所以可以限制将超出范围的时候返回 0（因为答案不会超出范围，中间的 power 超出范围就说明是负幂就是除）。也可以从大到小做，不会超出范围。
建立四个方向，每一步把当前位置加入 visited 并构建下一步位置，如果下一步已经在 visited 里面就换到下一个方向并重新构建下一步的位置。重复直到 visited 元素等于 matrix 元素个数。
简单，初始化 n 等于 1 和 2 的情况，然后每一行根据前一行来生成。
以每个点为中心，计算他到其他所有点的向量的方向，方向一样就说明他们在一条直线上。用 map 记录每个方向的 count。这样得到通过这一个点的所有可能直线上的最多点数。对所有点重复，得到通过所有点的可能直线中的最大点数。
用 bit mask。要 reverse 一个 32bit 的数，可以先交换他的前 16bit 和后 16bit。然后在这两部分里面交换前 8 和后 8bit。依次进行，最后交换每两 bit 里的前一个 bit 和后一个 bit。通过 bit mask 可以达到目的，比如 16 位 F0F0F0F0 的 2 进制是 11110000111100001111000011110000，0x0F0F0F0F 的 2 进制是 00001111000011110000111100001111，对 n 做&这两个 mask 就得到每 8bit 中的左 4bit 和右 4bit。然后结果分别右移 4bit 左移 4bit 再做|，就得到交换 4bit 后拼接的结果。对 16,8,4,2,1 分别做一次这种操作，就得到整个 reversed 32 bit 数字。
先找到这个数有多少位，然后找出具体是哪个数，然后取余找到具体是这个数的哪一位。
找到 increasing point 后的最大 digit，跟他前面第一个比他小的 digit 交换。
就是插空，每多一对就在之前的所有里面的空隙之间插入。
类似 two sum。对每个数，找到他和 k 的最大公约数。然后 k 除公约数，得到需要另一个数来补充的部分。再对每一个数看是否被 k 的所有除数整除。能被某个除数整除就说明这个数满足这个补充部分。
因为可以往 8 个方向走，所以用 2 或 3 步就可以走回原地。所以如果起点终点相同就看是否步数大于等于 2，如果不同就看曼哈顿距离是否小于步数要求就行了。只要小于步数要求，中间总是可以通过绕回原地来用掉多余的步数。
首先看哪些位置大于 1，哪些位置等于 0，然后放进 list。大于 1 的放进去 x - 1 次，x 是具体数值，表示这个位置要被分配 x - 1 次。然后计算这两个 list 里面每两个点之间的曼哈顿距离，这里用了 scipy.spatial.distance.cdist 这个函数。然后就是一个找矩阵最小分配 cost 问题，用的算法是Hungatian算法。直接用了 scipy.optimize.linear_sum_assignment 这个函数。
- 筛法
- all primes are either 2， 3， 或者 6n - 1/6n + 1 for some n 范围不大可以用筛法，这样筛一次就行了。但是空间需求很大。如果数字范围很大就用 prune，只有用到了才会算空间。
主要注意怎么筛素数。对小于 x 的素数，从 2 到 sqrt(x)为止，如果 i 是素数就把 i 的所有倍数都标位合数，依次标记。最后把没被标记为合数的拿出来，就剩下的是素数。
其实算是 dp 了。注意空集的时候返回的是 1，因为要和其他情况组合，其他子集里可能有元素，所以不返回 0。最后再只减去一个 1，就是所有子集都为空集的情况。
用 prune，然后对每个对角线上的元素，用 sqrt 之后再 prune 了的子集来判断是否是素数。用到了 lambda 函数，filter，all，集合的并｜，sorted。
把数组看成一个图，每个数字是一个节点，从当前位置到排序好后应该在的位置有一条边，得到一些不交的圈。最后 swap 数 = sum(每个圈的大小 - 1)。按顺序遍历排序后的数组，用元组保存原始位置，通过访问原始位置来遍历整个圈。用一个 list 或者 set 来 track 是否每个元素都 visit 了。
最简单的是用 heap。然后可以用快速选择，每一步选一个 pivot 然后 partition，返回 partition 后的 pivot 下标。如果下标等于 k smallest 就返回，否则根据相对大小在 pivot 左边或者右边继续找。可以 iterative 来做，就是给一个 start 一个 end，每一步把 start 或 end 重新定位到 partition 之后的 pivot，直到 start 等于 end。
比较复杂，对 pair distance 用 binary search，用一个 possible 表示是否有 k 或更多个 pair 的 distance 小于等于 v。用 prefix sum 来简化对 possible 的计算。直接抄的，之后重写一遍。用 multiplicity 保存 number of nums[j] == nums[i] (j < i)。再用 prefix 保存 nums 里 number of values <= v。然后在 0 和 nums[-1] - nums[0]之间二分找。二分每一步用 possible 判断是否有 k or more pairs with distance <= guess。这里遍历 nums，对每个数 x 和其下标 i，每次加上 prefix[min(x + guess, W)] - prefix[x] + multiplicity[i]。其中 prefix[min(x + guess, W)] - prefix[x]是 nums 里大于 x 小于等于 min(x + guess, W)的数的个数。multiplicity[i]是等于 x 但在 x 前面的数的个数。这些 pair 的差都小于 k，全部加起来看是否大于等于 k。x 和他前面且小于他的 pair 在其他迭代里已经计算过了。
自定义 key 排序，先找一遍把数字都找出来，剩下的分别按 content 和 identifier 排序。也可以统一一起排序，key 为另一个还是，用来生成一个 tuple 产生顺序。注意 str.split()可以定义 maxsplit。
用一个 dict 记录每个人的访问顺序，然后用 Counter 记录每个人访问过的网站的所有 combination，然后用 max，key=lambda x:pattern[x]取出 pattern 里面最大且字典序最小的元素那个。注意 Counter 可以用 update 方法来更新。itertools 有 combinations 可以求 list 的所有组合。这里对所有组合用了 set，因为同一个用户可能在不同时间有相同 pattern，只看做一次 pattern。
直接做。可以一行解决其实。注意 python 有 bin 函数，直接返回一个数的二进制表达。另外 count 函数直接返回一个数里某个数的个数。
过一遍所有 vote，用 list 记录每个 team 的票数和 team 字母本身。然后随便找一个 vote 排序，根据 record.get()作为 key。这里 key 就是一个函数，函数参数就是每个被排序的 element。记录的时候用负数别用正数，因为是 rank 要票数多的且字母小的优先。
简单的单位容量背包问题，直接按价值从大到小放就行了。
要求用 counting sort，直接 count 然后 greedy，从小到大如果当前价格的总价格不超多 coin 就 coin 减去当前总价，否则看剩下的 coin 最多能买多少个当前价格的。
记录下所有 candle 的位置，然后对每个 query 用二分，找到从左往右和从右往左的第一个 candle，然后两个之间的距离减去两个之间的 candle 数，就是 plate 数。
直接找到第一个最小元素和最后一个最大元素，然后算把他们放到正确位置的 swap 数。
考虑分别 pop 掉每一组递增序列。记录原始位置然后排序。从小到大，如果原始位置比前一个小就说明当前元素在原数组里属于一组新的数。res 加上剩下的所有元素，因为要把剩下的都 rotate 一遍才能 pop 掉当前组的所有元素。而且也当前组的最后一个元素也肯定是在末尾，所以要完全 rotate 一遍。因为如果末尾元素大于当前组最大元素，那就属于当前组。如果小于那就已经在前面的迭代里被 pop 掉了。
实际是 prefix suffix product。先从头往后，记录 prefix product。然后从后往前，在之前对应的 prefix product 上再乘上 suffix product。
先用 cache 记录每个 query 开始的位置和结束的下一个位置，然后过一遍，期间每个位置的 currSum 加上对应的 cache。
先过一遍 matrix，算出到每个 i j 为止的 submatrix 和。然后对任意两行，对 memo[x2][y1] - memo[x1 - 1][y1]用 y1 做 prefix sum。就和 2 sum 一样，每列先看当前 sum 减 target 在不在 hashmap 里，然后加对应的个数。最后放到 hashmap。
同 370。一模一样只能说。
同 370，不过这次用的是 dict 来当 cache。上面一个其实也可以，不过因为上面本来就要返回一个 list 所以直接用了 list。
类似 two sum，在每个下标处查之前和当前 substring 奇偶一样或者只差一个的 substring 的频率。每一步 xor 来处理 bitmask，用 bitmask 来记录 substring 的奇偶频率。
先排序，然后从没到 target 的开始从后往前，看把后 j 个补到 target 需要多少。然后用 new 减去这个，就是剩下来可以用在前面补 partial 的。先算一个 prefix sum 计算把前 i 个补到和第 i 个一样多需要多少 cost。然后用剩下来的再 cost 里二分查找，找到最多可以补到多少。然后算 partial 和 full 分别的分数。
先算出每个元素右边第一个比他小的下标，左边第一个小于等于他的下标，然后对每个元素，计算所有以他为最小元素的数组的和。这里要用两次 prefix sum，并且最后算的时候数组和是这样 racc _ ln - lacc _ rn 的形式。自己想大概是想不出来的，只能看碰到的话记不记得了。
对每一行做一次 prefix sum。另外也可以用 2dcache 来做，在每个矩形的左上角、右下角外+1，右上角外、左下角外-1 不过还没看懂，之后有兴趣可以看看这里。
先给 nums 排个序然后算前缀后缀和。每个 query 找到当前 query 在 nums 里的位置然后根据前缀后缀和以及当前位置算出需要的增减数。记得 bisect_left 找到的下标左边的严格小于查找的数，下标及下标右边大于等于查找的数。
用 dict 存数和对应的下标。距离里面把每个绝对值号拆开，然后就可以有公式了。对每个数，先算一个 prefix sum，然后每个下标里面套公式和 prefix sum 就行了。
先过一遍，保存 prefix 和 sufix sum，然后直接算结果。
主要难度在时间复杂度。把数量少的那个叫 A，然后通过不断调整 partitionA 和 partitionB 使正好 A 中 partitionA 左边加 B 中 partitionB 左边的元素正好是 A 和 B merge 之后的左半边，即满足条件 maxLeftA <= minRightB and maxLeftB <= minRightA。
先通过 left 和 mid 的大小关系判断转折点在左边还是右边，然后再通过 target 和递增那一边的两端的大小关系判断 target 在哪边。
简单，直接二分根据平方大小找。
bisect_left 返回下标 i，这之前的所有元素严格小于搜索的元素 x，i 及 i 之后的元素大于等于 x。先搜索所有行的第一个元素。如果返回的下标元素等于 target 则结束。否则说明 target 在下标对应的那一行（可能超出）。然后在下标对应的行再次搜索，判断搜索出来的元素是否等于 target。
和 33 基本一样，加一个步骤每轮如果 left 和 right 和相邻的相等就往中间移动，这样保证 nums[left] <= nums[mid]的时候转折点肯定在右边，否则在左边的话说明 mid 到 right 为止全都相等，那 right 就会一直往左走直到不相等。
不太好想，主要要想好判断条件。如果第一个小于最后一个那就是没有 rotate。然后看 mid 和他前后的比较看是否已经找到。最后把 mid 跟 left 和 right 比较，判断 rotate point 在哪边。
沿着对角线，从每个对角线元素开始往右和往下分别 binary search。
简单。可以把相等情况放在第一个判断，这样可以不用每次都运行到最底端，而且可以避免中间 out of range。
每次判断 mid 和他左右元素的大小，如果不是 mid - 1 < mid > mid + 1 就说明不是 peak，根据落在 peak 左边或右边决定下一步 binary 的方向。
用一个列表 snaps 记录每个位置上的数字变化。每个位置都是一个 list，只记录每次 snap 之间他最后被 set 的值。所以每次 set 的时候，如果 snap_id 没变就先 pop 再 append。set 时同时记录 val 和 snap_id。snap 的时候只更新 id。get 的时候在 snaps 对应 index 的 list 上二分找对应的 snap_id。
从最小速度到最大速度之间二分搜索。另外用一个函数来验证每个速度是否能达到。
对 potions 排序，然后在里面找对应每个 success/spell 的下标，有了下标就可以直接得到个数了。
就是 snowflake 的 oa。不过有 O(n)解法，greedy，明天再看看。
cost 函数是凸函数，所以可以用二分法来找这个最小值。每一步计算 mid 和 mid + 1 的 cost，判断最小值点在 mid 的左边还是右边，然后二分就行了
感觉 binary sort 这种的越来越多了。对 tastiness 二分，每步检查是否有一组 k 个 candy，tastiness 大于等于 mid。
把(i, j)和(k, l)分开看。保存一个 sortedlist，每加进来一个新的 j 就放到里面。对每一个 j，再对 k 循环。记录比 nums[j]大的 nums[k]的个数，也就是每个 k 右边比 nums[j]大的 nums[l]的个数。然后在 sortedlist 里二分找比 nums[k]小的 nums[i]的个数。两个相乘再加到总的 res 上。
counter 看一下每个数出现次数，然后依次往里面放就行了。
mini max 问题用二分法。这里每次检测 mid 这个最大 difference 可不可以达到。因为排序后的所有最小 difference 肯定出现在相邻元素之间，所以每次检测的时候只用检测那些相邻的元素就行了。
先想到用 list 来储存每一列每一行最后更新的数和更新顺序，然后每一列二分找这一列里在当前列顺序之前更新的行数，然后这些行被列覆盖，剩下的保持行的数。
从第 x 位开始，每一步把他之前的第 x 个元素放到 sortedlist 里。这样可以保证轮到每个元素的时候，他 x 位之前的数都在 sortedlist 里。然后每一步再 sortedlist 里二分找离当前元素最近的元素。因为加元素的方式，保证了里面所有元素都离当前元素至少 x 位。然后比较二分出来的位置上的元素和当前元素的差，并更新当前的最小差。这里用了 sortedcontainers，而且 sortedcontainers 里的结构可以直接 call bisect_left 函数。
条件 2 总是满足的，而条件 1 等价于|x| <= |y|, |y| <= 2|x|。所以先取绝对值，排序，然后从前往后对每个下标 i，找到 i < j, nums[j] <= 2nums[i]的最大的 j。从 i + 1 到 j 都是满足和 i 的 perfect pair。
可以用二分查找答案范围，也可以先排序然后递增 barrier 来逐步减小 sum。都是 nlogn。
从 0 到最大值二分查找。每轮验证当前的 max 是否可以达到。i 从后往前，diff = Math.max(nums[i] + diff - max, 0);这里如果 nums[i] <= max 就没问题，否则作为 diff 传到下一个数，这个 diff 需要在之后被抹平。如果到 0 都没被抹平就说明当前的 max 无法达到；diff 最后为 0 则说明可以达到。
在最小 max，1x1，和最大 max，nxn 里面二分，求满足条件的最大 kxk。
对答案二分。二分的每一步中假设现在是 x，首先过一遍 vulnerability，把大于等于 x 的元素标位 1，其他是 0。然后再过一遍，记录每一行 1 的个数。这个和前面可以合成一步。再对每一列，记录第一个为 1 的行的 index。如果有一列找不到说明不管怎么取这一列的 min 都小于 x，往左二分。都找到之后如果行 index 的数量小于 M 说明可以，向右二分，包含当前 x。如果 index 数等于 M 但是其中存在一行，1 的 count 数大于 1，说明有一行可以覆盖多列，一样可以，向右二分。否则向左二分。
记录之前每一个数的下标，以及 left。每一步如果以前记录过且在 window 内，则更新 left 到记录过的下标+1，否则不用管。然后把当前元素的下标也记录进去。最后更新 res 到当前下标 - left + 1.
用一个 Counter 记录 t 里面每个字母出现次数，然后保存一个 window，记录当前 window 内字母出现次数。如果某个字母出现次数满足了 Counter，enough 加 1.enough 表示当前 window 内已满足条件的字母数。如果 enough 等于 Counter 内字母数就说明完全满足要求，就把 window 左边界收缩直到 enough 减 1.这时更新 res 和 minimum length。
window 记录里面的和，大于等于 target 之后开始缩小 window 并更新最小 window 大小。
要想到 maintain 一个 deque，储存当前 window 里从最大元素开始往右依次减小的下标。这样第一个下标始终是当前 window 里最大元素的下标。因为加进去一个数之后 window 里面这个数之前的元素就都没用了，所以 window 是单调的。用一个 clean 函数来维护，clean 是 O(1)的。首先从左边去掉不在 window 里的下标，然后从右边开始去掉小于当前元素的下标。因为维护前是从大到小，所以维护后也是从大到小。然后用这个 deque 遍历 nums 就行了。
遍历所有 unique char 个数的 substring。根据当前 window 里 unique 字母个数决定是 r 右移或 l 右移。移动之后如果当前 window 的 unique 字母个数和当前遍历的个数和当前 window 里至少出现 k 次的字母数都一样就说明该 substring 满足条件，更新 ans。
用一个 set 储存当前 window 里的元素方便快速查找，用一个 deque 按顺序储存当前 window 的元素和下标。每一步，如果 window 已经满了，丢掉最前面的，更新 window 大小；如果新元素已经在 window 里，丢掉到重复元素位置并根据最后丢掉的元素的下标更新 window 大小；最后把新的元素放进来，如果 window 是满的就 substring 数加一。
因为可以交换任意两个位置，所以对一个 subarray，把所有 1 集中到这里的 swap 数就是里面 0 的个数。然后用 sliding window 统计每个 window 里 0 的个数就行了。
和 239 一样，用一个 mono deque 记录每个下标位置的最大 score，每一步更新并保持 window 单调下降，且 window 里 score 最大的在第一个。
滑动窗口，用字典统计窗口的的数字和个数。
直接 sliding window 就行了。。。每加进来一个就检测窗口内元素是否过多，过多就一直++左边界，不然就重复加新元素。
用 hashmap 记录当前 window 里的 good pair。然后 right 右移 hashmap 对应增加，left 左移直到 window 里 count 数小于 k。
统计以每个下标作为左边界的所有 complete subarray。窗口往右滑，如果当前窗口是一个 complete subarray 那么从当前窗口往右的所有 subarray 都是 complete 的。然后窗口左边右移一位，如果当前窗口不 complete 了就右移右边界直到 complete，如果直接 complete 就直接统计。
先预处理，得到每个数以及包含这个数的所有区间，然后对每个数的区间用 sliding window，依次加入下一个区间直到 count 超过 k，然后就把 window 头部的区间 pop 出去。
双指针往中间走。每一步指针指向更小元素的那个往中间走一步。证明：假设有 l 和 r 另外两个 height 使得 area 更大，所以我们之前肯定没有同时使用过这两个 height。因为指针会移动直到相撞，所以其中一个肯定在遍历中被访问过，假设是 l 那么左指针停在 l 的时候。要么一直在这里直到右指针移动到 l。但不可能，因为这样会经过 r。要么右指针经过 r 前 l 右移了。这说明右指针还没到 r 的时候 l 比右指针低，但这导致一个更大的 area，也矛盾。所以不存在这样的 l 和 r。
排序，然后对每个位置设为 target，对后面的数做 2 sum。因为是 unique 组合，所以如果当前数和前一个一样就跳过。
brute force 的话就直接做，linear 用 KMP。首先预处理 needle，得到 longest_boarder 的 list。每个位置 i 表示 needle[:i]的最大 boarder 长度。boarder 意思是相同的 prefix 和 suffix。有了这个之后如果 needle 和 haystack 不匹配就可以不用对 needle 从头开始，因为 needle 一部分的 suffix 和他的 prefix 一样，就可以跳过这些 prefix。有了 longest_boarder 之后开始匹配 haystack 和 needle，如果相同就两个 pointer 都加一，不同的话如果 needle pointer 为 0 也就没有 prefix 可以跳过，直接 h_pointer 加一。n_pointer 不为 0 那么有可能有 prefix 可以跳过，所以 n_pointer 从 longest_boarder[n_pointer - 1]开始。
可以直接用 quicksort，merge sort 之类的。还有一个 O(N)的方法，保持三个指针，p0, p2, curr。p0 左边全是 0，p2 右边全是 2，curr 是当前位置。如果当前是 0，交换 curr 和 p0。因为 curr 在 p0 右边，所以从 p0 换过来的是已经检测过的，p0 和 curr 都可以++。如果 curr 是 1 则不变。如果 curr 是 2，交换 curr 和 p2，p2--。这里因为从 p2 交换过来的没有检测过，所以 curr 不能前移，要保持在原地。
Two Sum 可以用 two pointer 做也可以用 hashmap 做，用 two pointer 的缺点是要先排序，优点是空间 O(1)。这里既然已经排过序了，就可以直接用 two pointer。
初始化两个 vector，然后用 turn 记录当前轮到谁，再轮流输出。
BST 的 inorder 遍历会得到一个 nondecreasing 的序列。所以用一个 inorder+twopointer 就行了。
排序之后依次匹配最小的和最大的，小于等于 limit 就一起放进去，否则只把大的放进去。
先排序，然后用 two pointer。很简单。还可以利用题目的条件 k 在 1-1000 之间，不过这个感觉不够通用，就算了。
从 root 开始 DFS，可以用一个 self 全局变量记录。另外其实可以不用 memo，因为每条路只计算了一次。
不是最快的，还可以用一维 dp 做。分别记录以 nums[i]结尾的负数和正数长度。这里用的双指针，实际是三指针，记录当前 window 左右边界和当前 window 第一个负数的位置。根据新数的正负选择用左边界还是第一个负数来计算。其实应该也是 O(n)但是不知道为什么比其他的慢。
先移到右边再 rotate。移动操作就是一个 two pointer。right 表示下一个放物品的位置，左指针移动到物品了就放到 right 那里然后 right 左移。如果碰到障碍物了下一个可以放物品的地方就在障碍物左边。
简单，因为可以直接变成任意字母，不是 swap，就直接记录从两边往中间不是 palindrome 的 pair 个数就行了。
记录左右边的当前和。哪边小就往中间移动并加上移动到的值，count += 1。如果相等就同时往中间移动，重置两个 sum。
每次右边加进来一个新数，如果 window 长度超过 k 或者 window 内有重复数就左边收缩直到满足条件。之后如果 window 长度正好是 k 就更新结果。
一个 pointer 在 t 上，s 里从左到右，每 match 一个 t 的 pointer 就右移。最后看 pointer 到结尾还差多少。
先排序。因为最多有 n//2 对，所以 j 从(n + 1) // 2 开始。之后 i 从 0 开始，满足条件就 i++，否则不变。最后 i * 2 就行。
因为每个 forbidden 的 work 最多长 10，所以可以对每个 right，看他往前数的 10 个 substring 在不在 forbidden 里面，在的话就 left 右移，否则不变。每步结束后更新 res。其中检测是否在 forbidden 里可以用 set 做也可以用 trie 做。
str1 和 str2 分别放一个 pointer。str1 的 pointer 依次往前，每匹配到一个满足条件的就把 str2 的前进。如果 str2 的到顶了就可以，如果 str1 到顶了 str2 还没到顶，就说明不行。
先排序，然后从左往右，对每个 index 做双指针。根据左指针右移和右指针左移，median 和 mean 的相对变化，来决定下一步移动哪个指针。
简单，recursive 遍历，对前一步生成的所有组合加上这一步的数字对应的所有字母。
简单。下一个长度的 combination 由上一个长度加上所有可能得没用到的数组成。也可以用 recursion。
简单，记得 res 里先放一个空集，因为之后不会遍历到；另外把 res 作为参数传到函数里就可以直接修改外部变量了。
从 board 的每个位置开始 dfs+backtrack 搜索 word。注意先 pre check 是否 board 里包含了 word 里的所有字母，不然会超时。
保存一个 seen dict，然后对每个 neighbor 迭代 clone。
用 backtrack 往下一个个查，注意要缓存不然会超时。用@lru_cache缓存。
直接检测是否有环。中途传回 True / False，方便检测到环的话快速结束。
一个拓扑排序。对每个点，如果已经标记了则跳过，如果已经临时标记了说明有环 return。都没有则给一个临时标记，然后对所有相邻的点 dfs。都 dfs 完了返回之后再去掉当前临时标记，做永久标记，然后放到拓扑序最前面。
dfs 返回从当前坐标开始的最长路径长度，用一个 path_length 来记录已计算过的格子
简单 dfs，从每个边上的元素开始 dfs，遍历到的就加一。先遍历上边和左边，然后重置 visited，再遍历下边和右边。最后计数为 2 的说明从 pacific 和 atlantic 都可以遍历到。
直接 dfs，对每个单词从每个下标分成两半，查找前一半和后一半是否在 words 里或者能表示成 words 里词的拼接。把 words 转换成 set，加上 memorization 来提速。
maxDiff 记录从这个 player 开始，他能达到的最大 difference。A 可以从左边或右边拿，A 拿了之后 B 拿，B 依然要从 B 开始最大化他的 difference。那么 A 的 difference 就是 A 拿左边或右边之后减去 B 的 maxDiff，两个里面更大的那一个。
T(N!), O(N) 直接 backtrack，用一个 self.count 来记录当前有效 permutation。每次 idx 到末尾就更新 count。
直接 dfs。检测连通分量个数。
T(
先检测整体和是否能被 k 整除，可以的话用 backtrack。每次往当前和里加一个元素，如果超过 target_sum 就直接返回，如果等于就 count += 1 然后当前和清零继续下一次 backtrack，如果小于就依次往当前和里加入下一个元素并 backtrack。注意就算从当前元素，不从头开始 backtrack，且预先排序，依然在 python 上超时。
从长到短倒着 dfs。这样可以不用每个字母每个位置都插入再尝试。
基础 dfs，记得 base case 一次只处理一项，不要把多种情况的 base case 合在一起处理。
用两次 dfs，第一次以 0 为 root，算出每个节点的最大和；第二次从 0 开始，往下 dfs 的时候传一个 parent_contribution，即在每个节点的 parent 方向的最大路径和。为了计算 parent_contribution，在每个节点算出包含他自己的 parent_contribution 在内的前两大的路径和。这样在所有子节点上，如果碰到了最大路径的节点，就把第二大的作为 parent_contribution 传入。
按除 k 的余数分类，然后在每个子集里讨论。每个子集里如果和前一个恰好差 k 就不能取，就是 house robber 问题。中间每一步乘的是 v - 1，因为考虑的是取当前元素的情况，所以减去全部不取的那个情况。同样，最后返回 res - 1 也是这样。
dp，对每个子列[i:j]检查[i:j - 1]或[i + 1:j]是否满足当前条件且本身可以被 split。
简单，用两个 q 交替记录当前层和下一层的 node，然后每层的 val 依次 append 到一个 list 里。
首先建一个 interword 的字典，保存这些 interword 可以通向哪些 word。然后从 begin word 开始 bfs。TLE 了。
因为只要找到 endWord 就行，所以可以直接 bfs+visited，不管中间是否有路径重叠。注意用一个 interWord 保存中间态，预处理 wordList 找到所有中间态，然后每一步转换成中间态之后再查找这个中间态可以到达哪些词。
简单 bfs，每遍历一个 island 就把这个 island 变成 0.记得加到 q 里的时候就变，不然可能会有很多重复加进去的。虽然最后 O(n)时间差不多，但是实际可能会超时。
先找出 node 之间的 edge 关系，然后拓扑排序。找关系直接找每两个相邻 word 之间第一个不同的 letter 就行，不要想太复杂。注意特殊情况，如果相邻 word，后一个正好是前一个的前缀，说明不可能。另外拓扑排序之后如果 output 长度小于 indegree 长度，说明排序完成后还有的 node 入度不为 0，说明有圈，一样不可能。
基本 bfs，从每个 gate 出发 bfs 并记录经过的格子。
可以从每个空地开始 bfs 到每个 building，或者从 building 开始 bfs 到空地。从 building 开始还可以每一步只 bfs 之前能 bfs 到的那些空格，可以更快。从空地开始的会超市。
先把所有 0 的距离置为 0，然后从 0 开始出发 bfs，把剩下的所有距离安上。
bfs，每一层计算每个点的 index，这一层过完之后更新最大 index 差，即宽度。
和昨天的一样，不过可以从边界开始 bfs，然后统计没有被 bfs 到的 1 的个数。
简单 bfs。记得 queue 里面本来就是按长度顺序排列的，所以不需要用 heap 另外排序。
bfs，queue 里每一步记录 state 包含当前位置和还能去掉几个 obstacle。用 set 记录这个 state 保证不重复。
bfs，每一步往前后一格和所有一样数字的 index 走。之前先预处理一下，记录数字和对应的所有 index。index 走了之后记得清空记录，这样之后就不会重复访问了。
简单 bfs。先记录所有单向边并同时保存双向边。然后从 0 出发 bfs 延双向边走，每走一步判断当前对应的单向边是否指向 0，不指向的话就 count + 1。
bfs + heap。依次把没去过的点放到 heap 里面，注意四周的点的到达时间取 max(time + 1, grid[nrow][ncol] + wait)。
一般看到 Maximum 或者 Minimum 就想到可能是 DP。DP 是可以把原问题分解为一些不相交的子问题，然后对所有子问题递归得到原问题的解。
dp(i, j)表示 s[i:]和 p[j:]是否匹配。每次计算先算一个 first_match，看当前位置上的是否能匹配。然后看后面有没有跟*。有的话分 0 个和多个的情况，多个就直接把 s 当前的去掉，0 个就把 p 当前两位去掉。没有的话就 s 和 p 都往后移一位。
每一步找到以当前元素为结尾的最大子序列。这些子序列里最大的就是最终答案。
简单 dp，根据当前位置是否有障碍物决定返回上方和左方的和或是直接 0.
简单 dp。
简单 dp。
明明是 DP 不是 DFS 啊。如果作 change，看看当前位置的 character 是否一样。如果作 delete，在 dp[i-1][j]上加 1。如果作 insert，在 dp[i][j-1]上加 1。取三个里面最小的。
可以用 recursion，很简单，不过要加 cache。也可以手动加。另外也可以三维 bottom to top dp，dp[length][i][j]表示从 s1 第 i 位开始，s2 第 j 位开始，长为 length 的子串是否 scramble。
简单 DP。dp(i)表示 s[i:]的 decode 方法数。注意各种边界条件。
简单 dp。dp(i1, i2, i3)表示是否能用 s1[i1:], s2[i2:]构建出 s3[i3:]。
简单，甚至不能称为 dp，保存到目前为止的最小值，取当前价格和当前最小值的差并更新当前最大值。
因为可以卖无限次，所以只要后一天比前一天价格高就可以买进卖出。
dp[k][i]是最多进行 k 次交易，最后一次最多在 prices[i]卖出，的最高总收益。所以如果最后一次不在 prices[i]卖出，就等于 dp[k][i - 1]；如果卖出，就等于 prices[i] - prices[j] + dp[k][j - 1] for j = 0, ..., i。因为只有 j 在变，所以等价于求 min of prices[j] - dp[k][j - 1]。因为这里只有 j 在变，所以直接用 min(currMin, prices[i] - dp[k][i - 1])就行了，因为比 i 小的已经在前面算过了，这里只要算当前值会不会更小就行。
每一步记录当前为止的最小值和最大值，并更新当前最大值。
和 123 一模一样，就是推广到最多进行 k 次交易。另外注意这里允许在同一天先买进再卖出。
最简单的一维 dp。
用原版 house robber 作辅助函数，根据拿不拿 nums[-1]分两种情况，分别做两次 dp。
dp[i][j]表示以 i, j 为右下角的最大 square 边长。如果 matrix[i][j]等于 1，那么 dp[i][j]等于和 i, j 相邻的三个正方形中最小的那个的边长加 1。
dp[i] = 以第 i 个元素结尾的最长递增子序列。di[i] = max(dp[j] + 1) if dp[i] > dp[j] for j < i.
建一个两行的 dp，第一行表示在当前位置没有卖出，第二行表示在当前位置卖出了。迭代思路和 k 次交易的一样，用一个 currMin 来减少运算。最后取两行末尾的最大值。
很标准的 dp 题，对用到的硬币数量和 amount 大小进行 dp。
recursion + memorization。根据拿不拿 root 分类。加上点边界条件就行了。
对 target 进行 dp，以 nums 里的每个数 num 作结尾都是不同的组合，然后 dp(target-num)。用 cache 加记忆。
不是最优解，差不多是 brute force+cache。可以用 DP。用一个字典储存 key:value, key 是每个位置，value 是能到这个位置的 jump 的长度的集合。最后如果最后一个位置在字典里，就说明可以跳到这里，否则不可以。
dp 从第 i 个 word 开始，一行能放下几次 sentence。同时返回下一行的开始 index。一次都放不完就是 0。这样没影响，因为一行能放下多次的话可以正确记录，一行一次都放不完的话后面总有可以放完，在后面再行数+1。
dfs 找每个 bitmask 最多可以被分成多少个和为 0 的 subgroup。在当前 bitmask 里依次去掉每个 1，然后取最大的那个。如果当前和为 0 就说明还有一个多的 subgroup。
用的 recursive dp，加一个字典 memorization。还可以优化从传数组变成传下标。
dp(i, j)表示组成到 i-th 下标为止的 key 的 substring，轮盘最终停在 ring 下标 j 的位置。dp 里面取 i - 1 元素在 ring 上的位置和 j 的差中最小的那个，就是这一步的最优方法。最后根据 key 的最后一个元素在 ring 里的位置来 dp，取这些位置里 dp 结果最小的那个。
dp，每次比较 i，j 和 i + 1， j - 1 加上头尾是否相等、i + 1， j、i， j - 1 之间的最大值。
每个 coin 有两种可能，用到或者不用到。所以对 coin 的 index 和 amount 做 dp，每次考虑用到或者不用到这个 coin 的情况。
先按结束时间排序，然后依次处理。维护到当前位置的上的最多的课，每个课的时长，和总时长。新的课来了之后，如果在当前时间直接上不超过 lastDay，就直接放进 heap 里；如果超过了，duration 大于之前的所有课的最大时长的话，不能放，否则无法维护是上的最多的课；如果小于之前的最大时长，则直接替换，可以维护是上的最多的课。因为是按结束时间排序，所以可以直接放进去替换。因为用了 heap，所以总时长和之前上的课的时长也可以快速维护。
dp[i][j]表示从 s 第 i 个到第 j 个的 substring 的最少 print 数。每有一个新的进来，如果和前一个一样 dp 就也一样。如果不一样那就有两种方法。一个直接在 dp[i][j - 1]基础上多 print 一次，一个从前一个相同字符开始覆盖到这里，然后重新 print 中间的部分。每一步对前面的所有元素都判断一次。
简单 dp，不过 edge case 弄了一会。用 dp 记录数组(l, s)，l 是以当前元素为结尾的最长递增序列的长度，s 是以当前元素为结尾的最长递增序列数。每个新元素过一遍前面的所有元素，如果前面的比当前的小那就是递增序列，根据前面的长度决定是否是最长递增序列以及是否加到现在的计数里去。
用棋盘记录每一步在每个格子上的概率。每一步更新整个棋盘所有格子的概率。最后对最后一步之后的整个棋盘上的概率求和。
第二次不用从 n-1, n-1 往回走了，直接从 0, 0 往右下出发两个路径，然后三维 dp，dp[r1][c1][r2]，然后让两个点在同一反对角线上，这样 c2 = r1 + c1 - r2。
其实是模拟，记录每个杯子里流过的总量，超过 1 就往下面倒(总量 - 1) / 2。
dp 用一个 helper function 分别返回 A 先 empty 的概率和同时 empty 的概率。注意 n 过大时因为 serve 的方式不对称所以 A 先 empty 的概率接近 1。所以 n 过大时直接返回 1 就行了。
dp 题最重要要有思路。dp[i][j]表示要放 i 首歌，有 j 个 unique 歌曲的方法数。如果第 i 个歌是新的，那么 dp[i][j] = dp[i - 1][j - 1] _ (n - j + 1)，其中 n - j + 1 表示除了已经有的 j - 1 首歌之外，剩下的 n - (j - 1)首歌。如果第 i 个歌已经放过了，那么 dp[i][j] += dp[i - 1][j] _ (j - k)，表示已经放过的里面后 k 首不能选，因为要放 k 首其他歌之后才能重新放。
基本 dp，根据在第 i 天用 1/7/30pass 来分类，取里面的最小的。另外注意 bisect.bisect_left 和 bisect.bisect，第一个是使找 a[:i] < x，a[i:] >= x 的下标 i，第二个是 a[:i] <= x，a[i:] > x 的下标 i。
用 bitmask+dp。三个 bitmask，分别表示 people_mask 当前 team 里有哪些人，skills_mask 有哪些 skill，skills_mask_of_person 一个人有哪些 skill。然后对 skills_mask 做 dp，对每一个人 i，看除了 i 的 skill 还需要哪些 skill。这个剩下的 skill 就是子问题。然后取所有 i 里 team 人数最少的一个。注意.bit_count()可以看一个数的二进制里 1 的个数。
简单 dp。text1[:i]和 text2[:j]的解依赖于 text1[:i - 1], text2[:j - 1]的关系。
直接 dp，能不能变成 palindrome 取决于变成 palindrome 的最小次数是否小于 k。dfs(i, j)如果 s 的 i 和 j 相等，则等于 dfs(i+1, j-1)。否则说明 i 或者 j 之间要去掉一个，就等于 1+min(dfs(i+1, j), dfs(i, j-1))。
直接 dp，用 recursion+lru_cache 可以直接过，用 memorization 的话就必须用二分搜索。dp(i) = dp(i+1)或者对第 i 个工作结束时间之后的所有工作 j，profit[i]+dp(j)中最大的那个。
dp[i][j]表示在 i，j 位置结束的最小 path sum。每一步在每个 j 处，dp[i][j]等于前一行除了第 j 列的最小 sum 加上 grid[i][j]。算 dp 的每一行的时候可以先处理一遍前一行，得到最小值及次小值，和他们的列下标。然后 dp 的每一列下标和上一行最小值的下标不一样的话就直接取上一行最小值，否则取次小值。
dp[i]表示从 0 到 i 需要的最少 tap 数。然后遍历每个 tap 考虑用到这个 tap 的情况下，用这个 tap 覆盖范围内的 dp[j]来更新这个 tap 的最远覆盖点处的 dp。就是每个 dp[j] + 1 里面最小的那个。
直接 dp，dp(i, d)表示从第 i 个工作开始，还剩下 d 天。dp(i, d)等于在当天安排从 i 到 j-1 的工作，然后剩下的 d-1 天做 j 之后的工作，即 dp(j, d-1)，对所有 j > i 里面最小的那一个。用 lru_cache 减少时间。
三维 dp 做的。dp[i][max_so_far][remain]表示已经放了 i 个数，到目前为止的最大值，和剩下需要放的新 max 个数。base case 就是已经放了 n 个数，和剩下的小于 0 的情况。考虑下一个数是新的 max or not。还可以对每个 max，做二维 dp，最后求和。过程中用 prefix 简化计算。
3d 的 DP。能想到 3d 的话就还好。看起来 dp 还是专门留一行空的出来比较好，这样就不用初始化了。先预处理，统计每个位置 i，j 右下方的苹果数。然后从 i，j 出发，按行和按列切，如果被切下来的部分和剩下的部分都有苹果就更新 res。
先找出每个下标上每个字母出现的次数，然后 dp。dp(t, n)对应用 word[:n]拼出 target[:t]的方法数。
dp[k][j]为在 s[:i + 1]中选择长度为 k 的挑选方法数。同时分别保存其中以'0'和'1'结尾的方法数。dp[k + 1][j]考虑是否以 s[j]结尾，不结尾直接用前一个，结尾再加上 dp[k][j - 1]里面结尾元素和 s[j]不同的方法数。更新。直接用字典记录 dp，记录每个组合的个数，每到一个新元素更新对应组合的方法数。
用 dp，相当于 max subarray 的一个变体。分别判断所有两个字母的组合，最多 25x26 种组合，每个组合花 O(n)的时间。判断当前字母并增减 max_subarray 后，根据后续是否无任何字母或两个字母都有还是其他，判断是中断本次循环还是重置窗口还是继续当前循环。
一个 budges * n 的 dp。有一些 edge case，像初始化，在有足够钱且当前收益为正的情况下才进行交易等。
DP+bitmask。几个操作 1 << n 是 bit 往左移 n 位。a & b，a ^ b。用整数表示一个组合，他的 bit 表示 1 的位置说明取到这个位置的元素。对 mask 求和里面 mask & (1 << i)表示 mask 里第 i 个位置是否为 1.然后从 bagMask 开始往下取 mask = (mask - 1) & bagMask。因为&操作只会把数变小，所以是从大往小取。每轮里面取 res = min(res, max(sum1, sum2))，因为是要取最小的最大值。sum1 = sumMask(mask)是这个 mask 单独分给一个人的和，sum2 = unfairness(k - 1, bagMask ^ mask)是 bagMask 去掉 mask 后剩下的 cookie 分给其他人的最大值。
先过一遍 nums，记录每个坐标前最近的等于 minK，等于 maxK，超出范围的值的坐标，记为 prev[0], prev[1], prev[2]。然后 dp。dp[i] = dp[i-1]，如果 nums[i]没超出范围，那么 dp[i]再加上 prev[0], prev[1]里更小的那个到 prev[2]的距离。如果是负的就不加。
用 monostack。对每一个新 i，pop 出 stack 里不满足条件的那些 index，stack 里剩下的就是有台阶的那些 index。然后对这些台阶算在每两个台阶之间取书的书数。
基础 dp，dp[i]取决于 i 之前的两个或三个数字是否满足条件以及更之前的 dp 是否 valid。
dp 检查到 i 下标之前的子串，里面长度大于 k 的回文串的最大长度。注意这里对以 i-1 结尾的子串，只用检查长度为 k 和长度 k-1 的就行，更前面的不用检查。
dp[i][j]表示在 nums[:i]中和为 j 的子集数。j 从 0 到 k - 1，dp[-1][j]就是 nums 中和为 0 到 k - 1 的所有子集数。在所有 2^n 种组合中减去第一组的和及第二组的和小于 k 的子集数。关键要能想到这么算。
切木条的变种，区别是切木条里面相应长度木条的价格都给出来了，这里要先算一下每个 nums[i:j]的 cost 并记录。
有点意思。先按除 k 的余数分组，不同组之间可以互相重合所以最终答案是所有组的乘积。每组里面排序，然后从小到大 dp，考虑是否选择第 i 个元素。如果选择，那么看他跟前一个元素的差是不是 k 决定取 dp[i - 2]或 dp[i - 2]。如果不选择，就去 dp[i - 1]。
基本 dp，从后往前 dp。每次看前一列的上下三行。
从每一个下标开始 dp。先初始化成 dp(start + 1) + 1 就是不用当前字母，当前字母就是 extra 字母了。然后 recursion 对后面每一个下标看从当前到后面在不在 dictionary 里，然后更新 res。
dp，dp[i][j]表示第 i 个 wall 用 paid 来做的情况下，完成 j 个 wall 的最低 cost。可以只用一维来记录。每个 dp[j] = min(dp[j], dp[max(j - time[i] - 1, 0)] + cost[i])，这里等号右边的 dp[j]表示上一步的结果。取这个和使用第 i 个 paid 的情况下，也就是用 cost[i]。用了 cost[i]会占用 time[i]的时间，所以可以完成当前的 wall 以及另外 time[i]个用 free 完成的 wall。去掉这么多 wall，剩下的最低 cost 再加上 cost[i]，和上一步的取更低的那一个，更新下一步。
dp 题有思路就好做。dp[i]如果是 0 就没有新的 split 方法，直接和前一个一样；如果是 1 那就可以有新的从前一个一后面的那个 0 开始一直到这个 1 前面的那个 0 那么多种方法数，这些加起来。比如 10000 后面来一个 1，那么就有 00001，0001,001,01,1 这些新的 split。
周赛的时候没思路，其实不难，按照结束的 house 分个类，然后对每个结束的 house 做 dp。先初始化成 dp[i - 1]因为可以完全不选以 i 结尾的 offer。然后对每个以 i 结尾的 offer，看 dp[start] + gold 和 dp[i]的大小。
dp[i][j]表示长度为 i 的 string，最后 j 位是元音，的组合数。对每个 i，dp[i][0]由 i - 1 的行和初始化。之后根据 j 和 i 的相对大小来判断状态转移方程。可以只保留一行作为 dp 储存，因为只用到了上一行的 dp。
dp[i][j] = 到 target 的第 i 个字母，使用的字母到所有 word 到第 j 个为止。每一个 i，j < i 为 0，j = i 等于 dp[i - 1][i - 1] _ target[i]在第 j 个位置出现的次数。j > i，等于 dp[i - 1][k] _ target[i]在第 k 个位置出现的次数，对 k 从 i - 1 到 j 求和。
先 dp，找出从 i 到 j 中间的最长 palindrome 的长度。注意 dp 是在每个对角线上 dp。然后以每个下标为分界点，求分界点左右乘积的最大值。
dp(i, j)表示第 i 个 task 时，还剩 j 个 free time 的 min cost。每次考虑 task i 放 paid 还是 free server，paid 就 cost += c[i]，j += time[i]，free 就 j -= 1 最后 i = n 的时候如果 j < 0 就说明这一列不可行，直接返回 inf。
dp[i][j]使用到 s[i]为止的 rl，到达位置 j 的不同方法数。每一步减去上一个和当前相同方向的方法数，即 dp[pre_same[i]][j +- 1]。
其实也算 bfs 吧，从每个点记录所有能跳到的点，直到碰到终点。
对于每个元素 j，要能跳到 j，需要他左边有元素 i 能跳到 j。只需要取这些 i 里面最右边的那一个，因为如果有 k < i，k 也能跳到 j，那 k 肯定也可以跳到 i。
首先可以直接排个序，然后每隔一位交换相邻数。或者可以每一位上根据奇偶看跟下一位的大小关系来决定是否和下一位交换。
先按结束时间排序，然后依次检测，如果下一个的开始时间大于等于前一个的结束时间，就不去掉，否则去掉这一个。这样相当于在两个重叠的里面保留了结束时间更早的那个，这样就给后面的留了更多空间。
先把频率最高的 task 排出来，中间放 idle 的。然后剩下的 task 依次往每个间隔里放，然后 idle 减小。如果 task 种类数超过 n 也不要紧，因为 task 必须放完，idle 只要不减到 0 以下就行了。如果其他 task 频率和最大的一样记得有一个 idle 不用减，因为频率一样的话就说明排到最后一个 task 后面去了，那里没安排 idle。
依次 push，只要 stack 末尾和 pop 匹配上就 pop，直到不匹配，然后 push 下一个。最后检测 stack 是否为空。
因为每个人都必须被分到一个 city 去，所以算一下每个人的 costA - costB 再排序，前 n 个人就去 a，剩下的去 b。
排序。0 和正数肯定要选，这之后每加一个负数，相当于增加前面所有正数的和，并减去到目前为止加进来的所有负数以及当前这个负数。所以从绝对值小到大开始对负数求和，直到减去的量大于等于正数的增量为止。记录下标，并计算从这个下标开始取的结果。
用了类似 Dijrastra 的思路，每一步把相邻没访问过的加到 heap 里，然后取当前所有 heap 里 effort 最小的那个。注意保存到状态包括 effort，不止位置，因为同一个位置可能从不同方向访问，effort 不一样。
简单，排序之后依次看每个元素是否满足要求，不满足就减小，直到最后一个。
先排序，然后把最大的 n 个电池分配出去。把剩下的加起来，然后对使用中的那 n 个电池从小到大，依次用剩余的电池把第 0 到第 i 个电池的容量补到第 i + 1 个那么多。这样电脑就可以运行 i+1 那么长时间。如果一直到最后还有剩余或者中间停住不能补到下一个，就把剩余的所有电量平均分配到所有电池或者前 i 个电池上。
只用看从末尾开始，把每个对应的字母从原始位置移动到开头的消耗就行。
最慢的人做需要时间最少的工作。
从后往前，依次把每一个比后面大的元素分拆。如果当前的整除后一个就分拆成所有都和后一个一样大，或者不能整除就分成比整除向下取整多一个，就是尽量少的分拆但是每一个都比后面的小。
greedy 的根据 lcp 依次填满 res 列表，如果用到的字符数超过 26 就返回''，如果遇到已经填过的就跳过。然后再循环一次检查生成的 res 是否符合 lcp。一个个位置对应检查太慢了，所以用 lcp[i][j]和 lcp[i + 1][j + 1]之间的关系来检查。如果 res[i] == res[j]那么 lcp[i][j] = lcp[i + 1][j + 1] + 1。最后根据 res 拼接出答案。
按结束时间排序。这样从结束时间开始往前安排 task，可以让后面的 task 最大化利用前面的时间。然后后面每次过一遍 start 到 end，去掉已经安排过的时间点，然后再从后往前把剩下的时间安排完。
总和 = sum ai + sum bj 其中 I 大小为 k = sum ai - sum bi + sum b 这里 sum b 是直接求和，所以是固定值，只需要最大化 sum ai - sum bi，就是算一下差值，取最大的 k 个就行了。
枚举所有 string 的组合，然后写一个 helper 找出两个 string 能重叠的最小 super string。然后求 super(a, b)，返回的 string 再和 c 求一次 super。返回所有这些 33super 里最小的那个。
基本 sql 语法，select join。
先找到最大值，然后以这个为条件，在小于他的值里面再找最大值。
创建函数的语法，create function 函数名（变量名 变量类型） return 返回类型，begin end，中间 return（），括号里写查询语句。limit x，y 表示从下标 x 开始取 y 个。
重命名一个叫 S1，从里面选两列，一个 score，另一个是 rank。rank 是另一个 distinct copy，S2 里面每个行大于等于 S1 的个数。
做三个 copy，选择里面 id 依次加一且 num 相等的 distinct 的 num 的个数。
建两个 copy，然后比较他们的 salary，且 e1 的 manageID 等于 e2 的 id。
where 用在输出结果之前，用来约束结果；having 用在输出结果之后，用来筛选结果。having 通常在 group by 之后。
注意用选出来的表来看 in。
从按 department id 拼起来的表里取 department name，employee name，employee salary。取的行要满足 department id 和 salary 的组合是 department 的最大 salary。
从拼起来的表里面，选出那些在同样的 id 里面，大于该项的不超过三个的那些项。
选两个 copy，删掉第一个里面的所有列，如果 email 相同且 id 大于第二个里的。
也可以用 join。另外比较日期大小应该用 DATEDIFF。
简单，用 MIN 函数。
注意别名要在括号外面。
取第几大的用 order by 之后 limit 来取。
直接用 outer join 会报错，必须 left 或者 right。
mySQL 有三个逻辑值，TRUE, FALSE, UNKNOWN。只有 TRUE 会被 where 返回。所有和 null 比较的都是 UNKNOWN，不会被返回。所以要额外加一个判断 IS NULL。
先 group 了再 order。
直接选。
join 选出 order 里面 company 为 RED 的那些的 sales_id，然后在 salesperson 里面找不在这些 id 里面的人。
可以用 union 把三个情况拼起来，也可以用 case when then 来作为选出来的那个 column。
条件语句，case when condition then result 可以多个 when then，最后 end 结束。
注意判断大小不能用连续不等号。日期函数是 DATEDIFF。
基本 select。
GROUP_CONCAT 可以返回用逗号连接的字符串。
用 LIKE 进行字符串匹配。sql 里字符串用单引号，%表示任意字符。
选出在 visit 但不在 transactions 里面的那些 visit id，然后取对应的 customer id，count，group by customer id。
CONCAT 函数连接字符串，SUBSTRING(string, startIndex, length of substring)取子串。注意 startindex 从 1 开始。
group by 可以按多个关键字 group。
简单。
select 列的时候可以直接做计算。然后求 sum。
easy，直接 select。
用字符串建立新 column。然后把三个表 UNION 起来。
用 IF(conditaion, if true, else)的函数可以直接选出一列
用 MAX。YEAR 可以取出 date 里的年份。
left join 之后用 where 筛选里面没有的 employee_id。
奇怪的问题。delete 什么都不用做其实。直接用 list 记录就行了。
初始化的时候直接过一遍 iterator 记录下来，然后之后直接对记录下来的 list 操作。
往前走，碰到墙或者已经 visit 过的就右转，四个方向都完了就返回上一个 cell。需要另外写一个 goBack 和 dfs 函数。
要用到 concurrent 包里的 futures 来做并行操作。每个 task 完成后再拿出来进行下一步 crawl。
简单。