Tricks Summary
Greatest Common Divisor
Euclidean Algorithm. LeetCode 1071:
1 | public static int gcd(int p, int q) { |
Calculate the new letter after shifting a certain offset on a given letter
- First calculate the offset between the currLetter and letter a.
- Add the shift to the offset.
- Modulo the offset by 26 to get the new offset.
- Add the new offset to the letter a to get the new letter.
1
char newLetter = ((oldLetter - 'a') + shift) % 26 + 'a';
Given the length of the palindrome and the center, how to know the index of the palindrome start
Assume the center’s index is i and the length is l.
If l is odd, the start index is: i - (l / 2) or i - (l - 1) / 2;
If l is even and i is the first position of the second half, the start index is again: i - (l / 2);
If l is even and i is the last position of the first half, the start index is: i - (l - 1) / 2;
How many jumps we need from index i to index j (i <= j)?
(j - i) jumps.
How many elements between i and j?
If include both i and j, the number if j - i + 1. If only includes one end, the number if j - i.
Meaning of Index
Given an array, if we know the index of an element, for example i, this means, there are i elements before the current element. This is a useful property that can be used in string related problem such as determing the right bound of substring.
Convert char array to string
1 | String newString = new String(charArray); |
Very straightforward.
Palindrome problem when input is consecutive and limited
This is inspired by 1457: Pseudo-Palindromic Paths in a Binary Tree. If we would like to record how many chars that occur in odd times in a string, and the char set is limited to a small range, for example in 1457, the chars are from 1-9, then in this case, we can use an integer to record the occurrence of each char. Digit 1 for 1, digit 2 for 2… digit 9 for 9 and the remaining 23 digits are still available! If a char occurs in even times, the corresponding digit will be 0, otherwise, it will be 1. We just use bit manipulation toggle the corresponding digit in the integer when we examine a char in the string.
But how to know if there is only one single 1 in the integer’s binary representation but not multiple? A good technique is:
1 | boolean singleOne = count & (count - 1) == 0 ? true : false; |
This works because if there is only one single 1, after we minus 1 from count, all the 0s behind this single 1 becomes 1 and this single one becomes 0 and if we perform AND operation between count and count - 1, the result would be 0. But if there are multiple 1s, only the last 1 will be eliminated, the remaing 1s are still there so the result won’t be 0.
This technique can also be used to count how many 1s are there in the binary representation of an integer.
substring
If we know how long the substring is and the start of the substring is ‘start’ for example, then this substring can be obtained by:
1 | // s is the original string, substringLength is the length of the desired substring. |
When to mark visited nodes in DFS and BFS
In DFS, when we arrive at a node, we mark this node as visited while in BFS, when we put a node into the queue, we mark this node as visited.
关于递归的重要结论
受到labulaong的启发:
一种是边走边更新, 或者边走边加工, 返回前把加工的东西全部复原. 比如permutation, subsets这种. 就是先加工点儿什么, 然后调用递归, 然后再移除之前的加工. 一种是此时获得不了答案, 但是二叉树下面的子枝走完能给我们返回我们得到结果需要的东西. 比如求tree的max height这种.
Comparator
关于写comparator, 小于零代表parameter one小于parameter two; 等于0代表二者相等; 大于0代表parameter one 大于parameter two. 比较a和b(a为第一个参数, b为第二个参数)正序排列一般就是return a – b; 如果要倒序排列则返回b – a, 如果a小于b, 会返回正数也就是告诉Comparator a应该靠后, b靠前. Comparator中如果结果小于0, 那么前者会在排序中靠前, 大于0前者会靠后.
Ascii码中数字, 小写字母, 大写字母开头:
0是48, A是65, a是97
链表的技巧
快慢指针
它是的循环条件是fast不为null且fast.next不为null. 当循环结束时, 如果一共有偶数个nodes, 那么slow停在后半部分nodes的第一个; 如果是奇数个, 那么刚好停在正中间那个node.
需要注意的是slow和fast在同一起跑线也好,fast比slow往后一个位置出发也好. 如果有cycle, 二者是会碰面的. 但是如果要找到cycle出现的第一个节点, 那么fast需要和slow同一起跑线出发, 这样的话, 等到二者相遇然后把slow重新放到起跑线再让二者移动等到相遇的时候, 那时相遇的点是cycle的第一个节点. 如果一开始fast在slow后一个位置出发, 那么这相当于slow和fast在slow位置前一个位置同时出发, 那么等slow和fast第一次相遇然后把slow重制到开头, 当二者移动再相遇的时候就不是cycle的起始点了, 这里应该把slow重制到开头前一个位置(假想的slow和fast在这一点同时出发). 这点要注意. 因此此时我们应该使用do while. 因为slow和fast要同一点出发, 但我们while循环的一个条件就是slow != fast.遍历
链表中从某个node到达某个node需要的步数
假设node 1在node 2的左侧, node 1的index是i, node 2的index 是j. 那么从node 1到node 2需要走的步数是j – i步. 这个可以类推尝试, 比如node 1的index是0, 那么如果node 2的index是1, 需要1步, 是2, 需要两步, 是n, 需要n步. 类似地假设node 1的index是i, node 2的index是i + 1, 此时需要1步, 假设node 2的index是i + 2, 需要2步, 假设node 2的index是i + m = j, 那需要j – i步.
这个结论对于rotate list相关的题很有用. 比如61题. 移除后k个, 那么如果我想到达倒数k + 1个位置. 那么要从head走多少步? 前面一共有count – k个node. 那么倒数k + 1个node的index为count – k – 1(假设head的index是0), 那么从head就需要走count – k – 1步即可. for循环中i = 0, i < count – k – 1即可.
Arrays.asList()
Arrays.asList() 传数组, 变成List. 或者传进去element也行比如这样:
List
最后出来的list包含1, 2, 3.
需要注意的是:
Using this method, we can convert from an array to a fixed-size List object. This List is just a wrapper that makes the array available as a list. No data is copied or created.
Also, we can’t modify its length because adding or removing elements is not allowed.
However, we can modify single items inside the array. Note that all the modifications we make to the single items of the List will be reflected in our original array
也就是用Arrays.asList出来的东西只是在array外面包了层壳, 使我们可以用List的方式去访问, 但是我们不能添加删除东西, 同时对元素的改变也会反映在原array中.
一个例子:
如果需要新new出来一个list, 我们使用ArrayList(Arrays.asList(array))
Similar to the Arrays.asList method, we can use ArrayList<>(Arrays.asList(array)) when we need to create a List out of an array.
But, unlike our previous example, this is an independent copy of the array, which means that modifying the new list won’t affect the original array. Additionally, we have all the capabilities of a regular ArrayList, like adding and removing elements:
此时出来的arraylist, 就是全新的, 我们对新的list更改也不会改变原有的array, 我们此时也可以add和delete元素.
给一个数组, 每个元素是个数字代表一位, 从高位到低位(左到右)遍历得到这个数组表示的值
result = result * 10 + digit;
result是存最后结果的变量, 我们边遍历数组边更新result; digit则是某个位置的digit. 比如一个数字是223. 从最左边开始, result一开始为0, 此时我们可以得到0 * 10 + 2 == 2. 然后到达下一个2, 此时result变为 2 * 10 + 2 == 22. 然后到3, 此时result变为22 * 10 + 3 == 223. 非常好.
如果给的是个string, 那么digit = s.charAt(pos) – ‘0’. pos表示string中的某个index.
用*10方法从高位到低位还原数字的时候, 如何大数clamp到Integer.MAX_VALUE, 小的数clamp到Integer.MIN_VALUE
在我们进行result = result * 10 + digit之前需要进行一个判断(判断执行这个*10 + digit的语句会不会overflow):
1 | if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && currentDigit > 7)) { |
我们要判断的是现在的result在乘完10之后加digit是否会overflow. 因为有overflow的风险, 我们不能直接算这个结果再和Integer.MAX_VALUE比. 如果result是long, 那没有问题. 因为long的话就不会overflow. 此时如果比Integer.MAX_VALUE大, 并且此时这个数组表示的数字是正的, 那么肯定超过int的最大值, 于是clamp到int的最大值. 如果数组表示的数字是负数, 那么这个数的绝对值最小是|Integer.MIN_VALUE|, 那么此时虽然可能没有overflow(刚好是|Integer.MIN_VALUE|), 但是也没必要再往下加了, 此时直接返回clamp到最小值即可.
如果不让用int类型的result, 那么就看上面的那个code snippet. 分三种情况, Integer.MAX_VALUE / 10是分水岭. 第一种就是result大于Integer.MAX_VALUE / 10, 此时result * 10就肯定超过, 直接clamp到int最大值就完事儿. 第二种情况是result == Integer.MAX_VALUE / 10, 此时需要分情况. 如果result == 214748364, (提醒一下Integer.MAX_VALUE是:2147483647), 并且digit是8或9也就是大于Integer.MAX_VALUE最小的那一位7, 那么result * 10 + digit就变为2147483648或者2147483649, 此时也是大于Integer.MAX_VALUE的. 最后一种就是result < Integer.MAX_VALUE / 10, 此时result * 10 + digit肯定不会overflow, 因为在这个范围内, result最大能取到的就是214748363, 也就是比Integer.MAX_VALUE / 10少个1. 那么此时result * 10即使加个9也才2147483639, 还差一点儿.
综上, 如果能用long表示result, 直接判断是否大于Integer.MAX_VALUE, 如果不能只能用int表示, 就看results是否大于Integer.MAX_VALUE / 10或者是否result等于Integer.MAX_VALUE / 10并且digit > Integer.MAX_VALUE % 10).
一个满树, 深度是n层处有多少node
深度是0时是1个, 1时是2个, 2是是4个, 3时是8个… 可以认为每一层代表二进制数的一位. 0层是least significant bit. 越往下越大. 因此深度是n时, 这一层的node数是2^n个. 一共有多少个node呢? 如果给定了height, 那么总数就是(2^height) – 1个. 因为height是从1开始数的. 到最后一层假如是n, 那就说明深度是n – 1. 此时二进制数中0到n – 1位都是1, 于是这个值就等于(2^n) – 1.
如何遍历一个map
比如一个变量map里装的是Integer和List
1 | for (Map.Entry<Integer, List<Integer> entry : map.entrySet()) { |
如何iteratively in-order traverse a BST with DFS
看LC 230题的题解.
如何代码写的简洁
合并一些重复的代码. 就如rotated sorted array那道题. 关于target和middle是否在同一侧, 我们进行了分类讨论. 不管哪一种情况, 我们最终都要移动low或者up. 这样就会出现重复的代码. 因此有没有什么方法可以让这两种情况适用一种逻辑呢? 我们使用了一个中间变量num, 如果target和middle在同侧, num就等于nums[middle], 然后根据binary search的那一套(nums[middle]和target比)去移动low或者up. 如果不在同侧, 我们强行让num等于某个值(这个值算是一个signal, 表明出现了不同侧情况. 我们让这个值也满足我们之前写的逻辑), 然后按照binary search的那一套同样可以正确地移动low或者up.
但是这样合并的情况就会使代码的可读性和理解性变低.
思考问题的角度
有时候我们会在想自己的逻辑是否能够应对edge case. 然后我们会绞尽脑汁开始想edge cases都有哪些可能. 我们不妨换种思路, 看看有没有什么好的角度能够证明我们的逻辑都能够覆盖哪些情况. 或者用数学的方法, 假设case的一些条件, 然后用逻辑去推理, 看自己写的代码能否满足我们的要求.
Backtrack
其实就是可以提前返回的DFS. 同时backtrack要记录一些状态, 如果达到某些条件则选择继续或者直接返回. DFS则是走遍所有的路. 其实backtrack还是DFS.
递归的一般结构:
1 | private void recursion() { |
回溯的一般结构:
1 | private void backtrack(int currState) { |
这个回溯模板确实好用. 修改全局变量然后恢复全局变量就是permutation, sudoku这些的做法. 括号的组合等等也是这样的. 这种问题我们都是假设在某个条件下(比如permutation的前几位已经确定的条件下), 剩下可能的路走一遍并把所有走到头的情况下那时全局变量的状态给存起来. Permutation就是这样的, 当所有的位置都确定了是什么字符的时候, 就存起来这个.
知乎关于递归, DFS, Backtrack, 动态规划的回答:
递归就是自我调用，经常作为一种编程的实现方式，比如题主问题中的DFS 、动态规划、回溯法都可以用递归来实现，当然也可以用非递归来实现。很多时候一个概念也可以用递归的方式来定义（比如gnu）。回溯是一种通用的算法，把问题分步解决，在每一步都试验所有的可能，当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能。很多时候每一步的处理都是一致的，这时候用递归来实现就很自然。当回溯用于树的时候，就是深度优先搜索。当然了，几乎所有可以用回溯解决的问题都可以表示为树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树，那么我们就叫它dfs。很多时候没有用树我们也管它叫dfs严格地说是不对的，但是dfs比回溯打字的时候好输入。别的回答里提到了砍枝，实际上这二者都可以砍枝。至于动态规划，被题主放到这里是因为都是竞赛中经常会遇到并且学起来不容易明白吗？回溯可以用于所有用穷举法可以解决的问题，而DP只用于具有最优子结构的问题。所以不是所有问题都适合用dp来解决，比如八皇后。dp需要存贮子问题的解，回溯不需要。
作者：Jerron
链接：https://www.zhihu.com/question/266403334/answer/698464437
来源：知乎
不管是递归还是回溯, 都是假设递归函数的功能, 然后通过调用它来实现我们想要的功能, 进而完成递归函数逻辑的书写. 也就是实现一个递归函数的功能需要这个递归函数的功能.
递归函数终止条件
在DFS中就很自然了, 不能一直往下走, 总要到什么地步就停下来然后返回.
递归函数的终止条件可以是在开头写一个终止条件. 也可以在调用某个递归函数前判断是否要继续调用. 前者会有压栈pop栈的过程, 消耗较大, 后者则消耗更少. 见combination sum这道题在递归函数中for循环的判断条件作为一个例子.
putIfAbsent(key, value)
这个method好啊, 见别人用到过. 它等同于:
1 | V v = map.get(key); |
TreeMap
就是红黑树. 每个node存的是键值对构成的entry, 按照key的大小排序(或者自定义排序方法, 使用comparator来说明排序方式). 然后我们可以在时间复杂度为O(logn)的前提下取到某个给定的key对应的value. 比如那个Time Based Key-Value Store那道题. 我想的是有一个hashmap, key是timestamp, value呢是一个hashmap, 这个inner hashmap存的是某个timestamp下的string, string这样的key value pair. 现在的问题就是如果我们想要得到某个string在某个timestamp下对应的value, 那该怎么办呢? 按照我的操作, 就是先看有没有这个timestamp, 有的话再看在该timestamp下有没有该string作为key的KV pair. 没有的话, 从timestamp开始向下遍历(timestamp – 1, timestamp -2…一直找到timestamp是1的情况, 因为最小就是1)外部的map的timestamp, 去寻找每种timestamp的inner map是否包含该string作为key的KV pair. 这样就会很慢.
试着想一下另一种嵌套方式. 用String-String pair的key作为外层map的key, 外层map对应的value呢是一个hashmap, inner hashmap则是timestamp和string-string pair中的value组成的pair. 于是我们给定一个string-string key value pair以及timestamp, 我们首先看这个string key是否存在, 不存在的话, 等于是在任何timestamp下都没有插入过该string-string pair. 如果存在, 我们找到这个key对应的hashmap, 这个map中呢存的是各种timestamp下以该string key对应的value的值. 此时又有一个问题, 如果刚好我们要的timestamp存在那还好, 直接访问到返回即可, 如果没有呢? 就要遍历整个inner map来找到最接近现在timestamp值的那个entry(该entry中的timestamp最接近我们想要的timestamp, 这是题目的要求)了, 因为这个hashmap的entry不是按照timestamp排好序的.
此时TreeMap就派上用场了. TreeMap就能把给定的键值对按照键的大小(键的大小可以根据natural ordering也可以根据我们提供的comparator)来排序并且可以在log(n)时间获得某个key对应的value. 于是如果inner map存在我们想要的timestamp, 那么直接获取, 如果没有, 那么获取此时存有的最大的timestamp即可. 毕竟红黑树就是个BST, 那么获取树中最大的timestamp也就是需要log(n)时间.
除了可以使用TreeMap, 我们还有别的方法. 我们忽略了一个点, 就是这道题有说过timestamp的值是不会递减的. 也就是后插入的timestamp不会比前面小. 也就是对于某个KV pair, 我们先插入K, V1(timestamp1), 后插入K, V2(timestamp2), timestamp2是不会小于timestamp1的. 于是我们的inner map可以换成List. list中存的还是timestamp-string pair, 按照题目的说话, timestamp只会越来越大不会变小, 那么这个list就是sorted了, 因为是先来后到, 对于同一个string key后插入的就会在list的后面. 对于sorted list, 想要查找某个值, binary search就自然而然被想到了. 先使用binary search找我们想要的timestamp, 如果有的话就返回它, 没有的话返回list中最后一个element中的value即可.
Binary Search变种(1):找某个target, 找不到就找比它小的数字中最大的那个, 如果还找不到返回-1.
除了常规的binary search(找到就找到, 找不到就返回-1), 还有一个变种就是如果找不到target, 返回比它小的数字中最大的那个数字的index. 如果没有比它小的, 返回-1(因为-1不可能是index的值):
需要改变的就是有个result变量, 初始值为-1(很关键, 因为可能整个list的值都比target大, 此时result值在全程都不会被更新, 这就说明没有比target还小的值). 每当left移动时, 更新result为当前middle的值. 到最后返回result的值即可.
这个模板需要牢记. 小中大(比target小的数字中最大的)左(left移动时记录), 大中小(比target大的数字中最小的)右(right移动时记录).
这个逻辑就是result始终处于left的左侧. 只要left更新, 那它就会变为middle + 1. 此时result变为middle也就是更新后left的左侧一格. 如果right更新, 那left和result都不会变. 这样的话我们就看最后结束循环left和right的位置是如何的.
1. Left和right重合并且left移动, 此时是middle(left和right也在这里)指向的值小于target, 更新result到middle的位置(也就是此时left的位置), 然后更新left位置, 之后循环结束. 我们知道right右边的值一定比target要大. 此时left来到了right后面一格子, result在left左侧一格, 此时就出现result指向的数字小于target, left更新后指向的数字大于target. 此时的result指向的是比target小的数字中最接近target的值了.
2. Left和right重合并且right移动, 此时middle指向的值(left和right也在这里)大于target. 假设之前result由于left移动过, 那么此时result指向的值是小于target的, 然后此时left和right重合指向的值是大于target的, 于是result也一样是指向比target数字小的数字中最接近target的值了. 如果left一直没动过, result则为-1. 此时也满足我们的要求(此时所有的数字都大于target, 我们需要返回-1).
3. Left和right挨着, right更新, 此时是middle(left的所在位置)大于target和2其实是一样的道理, result指向的值小于target而left指向的值大于target, 于是result依然指向比target小的数字中最大的数字.
综上这个逻辑是正确的.
***我们也要记住这三种结束循环前的情况:
Left和right重合, 二者其中一个更新导致循环结束以及left和right挨着, right更新导致循环结束.
Binary Search变种(2): 找某个index, 指向的数字等于target, 但是左边就比target小或者出界; 类似地, 找某个index, 指向的数字等于target, 但是右边就比target大或者出界. 这两个index之间都等于target(包含两个index指向的数字)
这个方法和上面的变种类似, 也是找个变量记录当前知道的最好的答案, 直到循环结束, 我们可以得到最终的答案.
找左边起始:
找右边起始:
想知道比某个数字小的数字中, 最大的那个数字:
Binary Search变种(3) 我们知道我们想要的某个符合我们筛选条件的值一定存在于给定的array中, 此时使用left < right策略.
比如658题K closest elements. 我们知道一定有一个index作为start, 然后往后框k个数字(包括自己), 这k个数字是最小的. 于是此时我们不断地缩小范围, 直至left == right, 此时指向的数字就是我们最终的答案. 对于这道题, 我们的收缩条件是看x - A[mid]和A[mid + k] – x的大小. 最终的答案区间一定满足A[start] <= A[start + k](start + k不出界的前提下). 如果小于的话, 至少我们能找到一个元素距离K更近, 因此此时框起来的区间不是答案. 当然满足这个条件的也不一定是答案, 但答案一定满足这个条件. 我们接着看判定的条件, 如果左边大, 说明此时mid距离k更远, 此时mid肯定不能是start, 因为mid + k这个位置出现了更小的, 而我们要求的是把k个最小的都框进去, 于是我们让left更新为mid + 1. 如果左右相等, 此时的mid可能是答案因为符合我们之前讨论的答案的特征, 但不确定, 因为可能mid左侧的值始终不变, mid + k左侧一个和mid + k相等 那么框住mid左侧的一个比框住mid + k左侧的一个要好, 因为题目是说如果两个位置距离x的距离一样, 那么小的那个算距离的更近. 于是我们先保留, 让right = mid. 注意此时mid右侧肯定都不是答案, 因为往右走mid会更接近x, mid + k会距离x更远, 这样的情况虽然符合最终答案的特征, 但是我们知道还有更好的答案, 也就是现在的状态(左右相等). 于是我们应该往左走. 如果出现右边大, 那说明此时mid可能是答案, 但不确定, 需要往左走看看有没有更合适的. 因此我们的答案就出来了.
本质就是让可能是答案的位置始终在sliding window里面, 直到最后角逐出最后一个.
数字字符转对应的int值, 字母字符在长度为26的数组中被map到的位置
比如这个数字字符叫做digitCharacter, 我们直接digitCharacter – ‘0’即可. 类似地, 如果用一个长度为26的int数组存储一个字符串中遇到的字母字符的出现频率, 如何让每个字母都map到它对应的位置, 比如a的频率存在第0个位置, b的频率存在第1个… z频率存在第25个. 我们直接用该字母字符减去‘a’即可. 假设这个字母字符为letterCharacter, 那么它的频率存在该数组中的letterCharacter – ‘a’这个位置(0-indexed array).
关于数组clone的问题
实验了一波, 明白了. clone和copyOf都是对于一维数组的deep copy, 如果直接给个二维数组, 那么最后都会只是shallow copy. 因此我们需要用循环, 一行一行的copy一个二维数组. 看下面的例子:
Substring的时间复杂度:
O(n), n是substring的长度.
HashSet和Trie:
简单来说HashSet生成hash去找某个string也需要时间, 而且是和给的string的长度有关的, 而Trie可以在早些时刻终止寻找而不需要看完一个string的所有字符.
如何DFS有cycle的graph或者DFS但是避免走之前走过的node
使用一个visited set来存走过的node. 在继续DFS前, 先看即将要去的node是否被visited过, 没有再继续DFS, 否则直接换路. 就拿clone node那道题来说, DFS的时候可能会遇到neighbor被visited过的情况, 这种情况的出现就是要么这个neighbor在栈中已被调用也就是在我们所在的栈的上方, 要么是这个neighbor已经完成了添加所有neighbor的操作. 不管哪种情况, 我们都不需要再额外创建一个node, 直接返回这个创建好的即可.
DFS带cycle的graph我们需要visited这种机制来避免走走过的地方. 这有点儿像人为的划分路线. 我们边走边往visited里面更新走过的node. 当我们在某个时候遇到visited里面的node的时候, 表示这个node已经来过, 不应该再走这里, 于是我们返回再走别的neighbor.
找递归的base case如何找
我的观察是看递归函数的parameter都有哪些, 挨个去看这些parameter并试一下每个parameter不同的input, 想一想什么情况下会出现这种input, 然后决定是否是base case, 如果是的话就记录下来.
二维dp转一维dp
Unique path那道题转1D dp的思路是个好方法.
Sliding Window
在类似sliding window的题中, 不要一步到位, 让一个left和right一次走太多, 走一步看一步是比较好想思路的. 看76题.
>>和>>>
>>是signed right shift, 左侧会补之前在这个位置的值. 比如如果最左侧是1, 那么right shift一位, 最左侧还是1. 1000变为1100. >>>是unsigned就是不管最左侧是什么, 统一填0. 1000变为0100.
想要理解递归, 就要跟着递归走一遍.
有时候确实是需要跟着递归走一走才能明白为什么可以这么写, 知道后记住这么写有什么效果就行. 比如permutation那个模板, swap然后helper然后swap, 这样来得时候什么样, 回来还什么样.
Linked List快慢指针
循环的条件是fast != null并且fast.next != null. 如果最终fast == null, 表示list一共偶数个nodes; 如果fast最终它的next是null, 这表示list一共有奇数个nodes.
如果是list有偶数个nodes, slow会停在后半部分最前面的node处. 因为fast跳一次就能经历2个, 假设它跳了n次到达null, 它左侧(所经历过的)有2n个. Slow也是移动了n次, 从第一个移动到第n + 1个. 于是slow的左边有n个, 右边有n – 1个, slow也就是后半部分的头一个.
如果是list有奇数个nodes, slow会停在正中间. 一样的道理, fast最终跳了n次, 停在了最后一个node处, fast身后有2n个nodes, 一共有2n + 1个nodes. 因为slow也跳了n次, 那么slow在n + 1个node处. Slow左侧有n个, 右侧有n个.
写循环
我们写循环通常是要在某个范围内的, 比如数组范围内, 字符串范围内. 在此之上, 我们可能还有些别的条件之类的. 我们会开始思考循环停止的时候会有哪些情况. 我们可以这么想, 我们是在某个范围内去干某件事, 当循环停止时, 要么是我们想干的事情干成了, 要么就是出界了. 分成这两种大情况也许会好思考逻辑一些. 见844题. 我们找一个不能被抵消的字符, 条件首先是要在string的范围内, 其次是此时没有#可以用来抵消字符, 如果都不满足我们停止. 当循环停止无非就是两种情况, 一种是我们出界了也没找到这样的字符, 或者就是我们找到了一个字符, 此时#的count由于是0, 因此不能再抵消字符, 这两种情况也被反映在我们对ansOne和ansTwo赋值的判断上.
String array是如何被sort的
是一个一个char比较的. 先比较最左边的char按照ASCII码去比较. 如果这一位相同再比较下一位, 直到分出大小. 如果一个string下一位没了而另一个string和它前几位都相同但是后面还有, 那么前者(短的)就被认为是更小的.
String的indexOf
我们可以传入一个char或者一个string以及一个起始点, 从起始点开始找, 返回第一次我们给定的char或者string出现的位置, 如果没找到, 返回-1.
BFS的注意
就是在while q not empty进入循环后, 如果我们需要记录level的情况, 比如想知道现在是在哪个level了, 或者像1730那道题, 一个level遍历完我们要让distance + 1, 这种情况记得刚进去while循环后记录此时的length. 然后在内部循环length次从而让该level的node都被遍历到但是下一level新添加进来的nodes不会被遍历到.
Trie
我们搜索一个word中的某个字符比如第n个字符的时候, 默认前n – 1个字符都存在于prefix tree中, 也就是一路从root到某个node, 包含了前n – 1个字符, 于是当我们要判断第n个字符在不在的时候, 我们需要从第n – 1个字符对应的trie node处去看, 看看它的下一个字符中有没有第n个字符. 因此搜索一个字符都是从上一个字符对应的trie node开始的(也就是从root开始搜寻第0个字符, 搜到了然后进入第0个字符对应的node, 然后去搜寻第一个字符, 搜寻到了, 进入第一个字符对应的trie node然后搜寻第二个字符… 以此类推, 一直搜到了第n – 1个字符, 我们进入其对应的trie node然后去搜寻第n个字符).
O(nlogn)
以后看到这个的时候, 我们应该想到binary search或者sort, 因为如果n个元素, 每个元素都用binary search那就是nlogn了. 如果是sort, 更不用说了, 就是nlogn.
Anagrams
Anagrams说白了就是按频率说话. Anagrams之间, 每个字符出现的频率是固定的, 只是排列组合造成了anagrams. 比如badd和abdd互为anagrams, 它们都是a出现1次, b出现1次, d出现两次, 只是这些字母的排列组合造成了anagrams的现象. 因此如何去identify一种anagram? 看它每个字符出现的频率, 也就是用一个array去存每个字符出现的频率. 比如假设word都是小写字母, 那么我们可以用长度为26的char array去存每个字符出现的频率, 到时候直接把这个char array给到String, 这样就生成了一个该anagram专有的string, 可以存到map中, 如果后面的word有同样的key, 就说明二者互为anagrams.
如果两个word它们这样的array一模一样(每一个元素的值相同, 代表这个元素表示的字符出现的频率相同), 那么这两个word就互为anagram.
Map.values()
它可以直接扔给一个: new ArrayList<>(map.values());
想只获得key就是: map.keySet();
想只获得value就是: map.values();
Clone graph
Clone graph那道题的DFS方法就相当于DFS遍历一遍graph. 每次遇到新的node就new出来一个, 遍历的目的就是走遍每一个node, 到一个node就new一个, 如果发现某个node new过了, 那么就不再沿着这条路走该换其他, 直到所有的路都走完. 从一个node出发往其他neighbors走, 到达某个neighbor时会该neighbor会和它建立edge, 当从该neighbor返回时, 它又和自己的这个neighbor node建立edge.
每个node都是这样. 每个node都会被压入栈, 压入栈意味着执行递归函数中的内容, 该node会走向每一个neighbor, 如果neighbor被new了那就直接指向, 不用担心neighbor不会指向自己, 因为每个node都会被压入栈, 从而指向它们的neighbors. DFS回来时自己指向neighbor, DFS出发后自己的neighbors会指向自己.
循环
循环表示我们要把某些步骤重复做, 这代表着要么是一开始有个初始状态进入循环, 要么是已经循环了几次我们又进入循环. 因此每次进入循环就这两种状况. 通常再次进入循环可以看做是以现在的条件初次进入循环, 和第一种情况一样. 因此有时候不需要区分先进入循环和后进入循环的情况. 这个思想需要知道.
递归
做到decode string那道题, 发现递归的一些本质. 本质就是栈桢, 里面可以存储数据, 变量. 当我们遇到左括号时, 我们需要先知道括号里的string是什么, 于是先把目前构建好的string保存在目前的栈桢中, 然后调用递归函数来去构建括号里面的东西, 等构建完成后, 我们返回, 此时之前构建好的string还保存的好好的, 我们继续构建即可. 参照basic calculator那道题, 也是同样的道理. 递归函数就是遇到某个情况不能解决, 需要存一下当前的一些值然后继续调用递归函数来去完成subproblem, 等把subproblems解决完后回到之前的递归函数此时就能够完成任务了.
BFS
如果是在原来的矩阵上进行改变, 那么什么时候改变呢? 是压入queue之前, 还是在queue中取出来后再改变?
DFS
DFS返回值这个东西可以认为是如果下面遇到了什么特殊情况, 我们就需要把这个情况一直往上传. 于是我们在调用的递归函数后运行完毕后可以看一看传递给我们的有没有要继续向上传递的消息, 如果有要把这个情况考虑, 没有的话就不用传话, 直接返回. 1254这道题就是. 如果遇到边界情况了, flag就会是false然后返回上层, 上层看到递归函数结束后就要看是否有flag有false的情况, 如果有的话要及时把自己的flag也设置为false然后向上传递.
Priority Queue
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
也就是PriorityQueue里面的elements默认是从小到大根据natural ordering去排. 或者我们提供Comparator去排. poll(), peek()都是看头部也就是最小的或者根据我们的Comparator排在最靠前的. 注意的是如果我们获得iterator(), 它并不会按照order给我们去iterate, 想要去按顺序iterate, 就需要这样:
1 | Arrays.sort(pq.toArray()); |
什么时候用栈?
Whenever I see a problem, where past inputs affect the current input, and I can’t get to past inputs without stepping back through each step, I think of stacks.
这是735题下面bodet这个人的评论的reply里harrytheape的回答. 我觉得说得很到位. 如果之前的input对现在的结果有影响, 并且我还不能知道之前的input, 那么就会考虑使用栈把之前的inputs存起来.
矩阵的转置:
1 | for(int i = 0; i < matrix.length; i++) { |
具体见48题.
Graph中的node
Graph中的node可以看做是一个entry, 该node的value和其children构成的set组成的entry.
比较数轴上的两个数字哪个距离某个值更近
假设array[i] < array[j], 那么如果想知道二者哪个距离数字x更近, 用下面这个公式:
x – array[i] 和array[j] – x进行比较. 谁小, 谁离x更近. 假设x在array[i]的左侧, 那么肯定距离array[i]更近, 此时x – array[i]是负数, array[j] – x是正数, 我们得到左侧小, 符合我们array[i]更近的判断. 如果x在array[j]的右侧, 那么肯定距离array[j]更近, 此时x – array[i]大于0, array[j] – x小于0, 右侧小, 符合我们array[j]距离x更近的判断. 如果x在array[i]和array[j]之间, 那么此时左右都是大于0的, 看谁小就说明距离谁近.
假设array[i] == array[j], x如果在array[i]左侧, 我们认为是array[i]更近, 如果x在array[j]右侧, 我们认为array[j]距离更近, 如果x等于array[i]和array[j], 我们认为一样近. 当然我们如果不想这样认为, 比如x在array[i]左侧想认为array[j]更近, 那么我们可以加个if, 来处理array[i] == array[j]的情况.
来自658题的启发.
关于DP要声明数组长度的问题
以139题为例, 是要声明长度为s.length()的数组呢还是s.length() + 1呢? 其实我们可以看一下我们的诉求是什么. 在某个位置n, 我们想知道从第0个位置到第n个位置(两头均inclusive)是否能构成word break, 我们首先看能否直接构成一个word, 即[0, n]能否构成, 如果不能我们再看[0, 1), [1, n]能不能构成, 以此类推, 直到最后[0, n), [n, n]能不能构成, 那么[0, 1), [0, 2), [0, 3)…就代表着不同的状态. 于是我们可以规定dp[n]代表[0, n)是否能构成word break. 因此我们想要知道的是[0, s.length())能否构成, 于是为了满足下表index表示的就是[0, index)是否能构成word break, 我们声明s.length() + 1长度. 那么问题来了dp[0]应该给true还是false呢? 不妨看一下我们判定一个位置是否构成word break需要走的流程, 某个位置n对应的dp[n]先看是否[0, n)自己就是word, 如果不行, 那么看dp[1] && dict.contains(s.substring(1, n))是否满足, 如果不行再看dp[2] && dict.contains(s.substring(2, n))是否满足以此类推. 此时最开始可以看做是dp[0] && dict.contains(s.substring(0, n)), 由于我们此时只看后者, 前者默认为true就行了. 这样我们可以让这个判定式保持consistent, 不必在一开始的时候单独判断dict.contains(s.substring(0, n))而不是dp[0] && dict.contains(s.substring(0, n))这种形式.
StringBuilder的toString()
Returns a string representing the data in this sequence. A new String object is allocated and initialized to contain the character sequence currently represented by this object. This String is then returned. Subsequent changes to this sequence do not affect the contents of the String.
也就是toString()会生成一个新的string, 我们再对StringBuilder的改变不会影响这个新的string的content.
Backtrack标记的原则
Backtrack常用的就是标记, 或者给一个东西添加东西. 比如permutation, parentheses, 我们都要维护一个StringBuilder, 我们在某一个递归函数中给这个StringBuilder添加一个char然后进入下一个递归函数, 我们会担心返回来的时候的StringBuilder里面的内容还是我们刚添加完char的样子吗? 在向下调用的过程中会不会把这个StringBuilder给污染了. 我们可以这么想, 递归函数的功能包含了在接到是什么样子的StringBuilder那么在返回的时候还是什么样子. 比如permutation, 我们在某个level确定了某个位置是哪个字符, 此时的StringBuilder的状态假设为A, 然后继续向下, 等到又回来的时候, StringBuilder还是在A的状态. 我们秉承这个假设, 在对StringBuilder进行修改的时候, 认为递归函数是不会对StringBuilder进行改动的, 然后确保在递归函数返回之前把我们的修改撤销.
另一个例子就是word search那道题.
第18行我们对visited进行了修改, 中间19行到28行进行了递归函数的调用, 我们假设它们不会修改visited(其实是修改了但是返回的时候又把修改撤销了). 等我们到达29行的时候, visited只是进行了我们在18行的修改, 为了满足我们对递归函数的假设也就是返回前要把修改撤销, 我们在29行把18行的修改撤销即可.
找到给定的intervals中, 最多有多少个intervals互相会有交集
253题. 思路就是sort start和sort end得到两个arrays. 看最早结束的meeting前有多少个meeting会开始, 那么room数字就是多少, 等到有个meeting在最早结束meeting结束后开始, 那么这个最早结束的meeting占用的room就可以给这个新的meeting了, 此时room. 后续的meeting去看是否比第二早结束的meeting之前开始还是之后开始, 如果之前开始, 那么需要加room, 如果之后, 那么第二早结束的meeting所占用的room就可以给这个新的meeting了.
String的大小是如何被比较的
逐位比较ASCII码的大小. 第0位相等就接着比较第1位, 以此类推, 直到比出大小. 如果一个string短, 一个string长, 比较到短的string的每位都和长的相等, 此时短的没东西和长的string比较了, 那么短的更小. 比如hello和hel, hel会排在hello前面. Hel和Hal比较, Hal在前面(更小).
String类型的题的常用技巧
- Sliding window
- DP
Sliding Window
写sliding window的精髓在于两个pointer标记的地方是否属于window中, 我们的写法就统一都属于. 其次是包含新元素和pop走老元素的过程是如何体现的. 比如424题, include一个新元素的体现就是让count数组中对应位置的值 + 1. Pop走一个元素的体现就在于把count数组中对应位置的值 – 1. 这个include和pop的体现是sliding window的精髓, 而非是看此时的left或者right的位置. 只有完成了include我们才认为包含了right指向的元素, 只有pop走了, 我们才认为left可以移动到下一个位置, 在pop前, window一定包含left指向的元素. 在include前, 一定不包含right指向的元素.
DP
DP是个很大的话题, 需要很多总结. 首先就是一些初始条件的确定. 比如416题, partition equal subset sum这道题. dp[0][0]是true. 也就是[0, 0]包含的元素中, 可以凑到0. 为什么这么规定? 假设有一个元素刚好等于我们的sum, 那么我们按照逻辑就会看前面的元素是否能凑到, sum – 该元素, 如果可以, 那么凑好的数字带上当前元素就能凑成sum. 于是我们让dp[m][0]是true即可(m >= 0).
写dp有时候不知道初始条件怎么写, 此时可以先试着写出状态转移方程. 写完后根据我们的要求去看如果遇到初始条件, 初始条件等于什么的时候满足我们的逻辑. 比如518, coin change 2. dp[i][j]表示前i + 1个元素凑j时有多少种凑法. 那么我们首先先想状态转移方程:
假设i和j都很大(这样可以让我们不用考虑出界等等一些边界条件, 这些等到后面再考虑), 那么dp[i][j] = dp[i – 1][j] + dp[i][j – nums[i]], 也就是如果不带前i个元素最后一个元素时能凑成j的种类, 或者是带最后一个元素, 于是就是前i个元素凑成j – nums[i]的种类. 那么dp[0][0]是什么呢? 由于第0行没有i – 1行, 我们不妨直接看看前1个元素能凑成每个数字的种类最多肯定就是1. 假设第0个元素为3, 那么dp的第0行3的位置一定是1. 也就是前1个元素凑3最多只有一种方式. 那么看我们的转移方程, dp[0][3] = dp[-1][3] + dp[0][0] == 1, dp[-1]可以是假想的上一行, 那么自然而然上一行每一个位置都是0, 因为没有元素的话, 什么都凑不成. 于是dp[0][0]就自然而然是1了.
dp[0]不知道给什么值? 想一想什么情况下会取到dp[0]. 一般这种情况我们都知道答案, 不需要状态转移方程, 但是电脑需要状态转移方程计算. 那么接下来就是求未知数dp[0]了. 比如coin change. 如果目前是拿2凑2, 我们需要看凑0需要最少多少硬币, 再 + 1就是2凑2的个数. 我们知道拿2凑2只有一种, 那么凑0个最少硬币 + 1 = 1, 于是凑0的最少硬币就是0, 因此dp[0] = 0;
给一堆数字凑数
感觉越写越乱. 一大类型就是给一堆数字去凑另一个数. 直接记住这个类型的不同情况, 本质就是凑0是可以凑到的.
1. 若是求用最少个数个数字去凑成target的, dp[i]表示的是凑成i需要最少的数字. 那么dp[0]就是0, 因为凑成0不需要任何数字, 直接就是0. (322题, coin change)
2. 若是求凑target有多少种凑法, dp[i][j]表示前i + 1个元素凑j一共的凑法, 那么dp[0][0]为1, 这表示前1个元素凑0有一种凑法, 那就是不给元素. (518题, coin change 2)
3. 若是求能否凑成target, dp[i][j]表示前i + 1个元素能否凑成j, 那么一样, dp[0][0]是true, 也就是前i + 1个元素可以凑成0. (416题)
DP数组长度怎么定?
如果是string类型的就定为string.length() + 1.
如果是凑数类型的就定为target + 1.
如果还要牵扯到前多少个元素的, 就定为nums.length.
DP的初始条件
dp的初始条件的确定比如dp[0], dp[1]是多少, 我们可以带入一些例子来看看我们把它们初始化多少符合我们的逻辑. 比如第96题, 我们把dp[0]初始化为1而不是0. 尽管0个nodes能组成0个BST也说得过去, 但是为了符合我们的逻辑(某个node作为root, 它左侧nodes组合BST个数乘上它右侧nodes组成的BST个数就是该node作为root能组成的BST的总个数), 我们需要让dp[0]等于1.
关于compare的正反比较
return 里的东西如果小于0, one排在前面, 否则two排在前面, 于是上面的写法就是按lexicographical order排序. 如果这样写:
一样的return那个东西如果小于0, one在前, 否则two在前. 假设one的lexicographical order小于two, 那么return的是大于0, 于是two排前面, 于是这样排是倒序排.
通过给一些例子进去, 来看什么样的元素会被排在前面. 第一种是lexicographical order靠前的会被排在前面, 第二种则是倒序, 也就是lexicographical order大的靠前.
总结一下, 给的两个元素one和two. 如果就是return one – two或者one.field – two.field, 或者one.field.compareTo(two.field), 那么就是按照某个标准升序排列. 如果出现第二个参数在前的情况比如two – one或者two.field – one.field这样的, 那么就是按照某个标准倒序排列.
关于缩2D DP到1D DP
模板就是dp长度和列数相同. 第0行的dp单独用一个循环来初始化. 然后之后每行更新dp的时候, 遇到边界要单独处理. 比如第64题. 开始时dp的长度是grid的列数. 然后第0行单独拎出来初始化dp. 之后每次到dp[0]的时候, 拎出来单独处理.
或者我们专门多新建一列一行来accommodate边界的情况. 见1143题. 由于我们需要用到右下对角的值, 因此需要用变量来存这个值.
Palindrome题, 从某个center扩张获得该center能到达的最长长度是多少或者该center有多少个palindromes
647题以及longest palindrome那道题. 模板一定要记好.
Recursion到Recursion + memoization的过程
首先想到recursion的解法, 然后发现有些情况是重复去做的, 于是想到用memoization. 用memoization时, 之前写好的递归函数不需要改, 唯一要加的就是传入一个memo数组或者map用来访问和存结果. 当我们想要的某个结果不在memo中时, 我们就去计算, 计算好后存到memo中.
因此recursion + memo的模板就是, 先看memo中有答案吗, 没有的话去计算, 计算好把答案存到memo中然后返回答案. 如果memo有答案, 那直接返回这个答案.
Recursion + memoization到dp的过程
一般来说helper function被传入不同的参数就代表dp中的不同状态. 我们观察helper function的signatrue来确定dp数组是一维的还是二维的. 比如1143这道题. 两个参数pos1和pos2标记着text1和text2要被截取的起始点, 也就是pos1和pos2标记着一种subproblem, 不同的subproblem拥有不同的(pos1, pos2)pair. 因此我们自然联想到dp用二维, dp[i][j]表示text1从i这个位置往后截取, text2从j这个位置往后截取, 这两个substring的LCS长度就是dp[i][j]. 因此观察helper function的signature. 接下来, 状态转移方程观察helper function的内容, 看当前传入的参数构成的subproblem是依赖哪些其他subproblem. 还是以1143这道题为例, 我们发现如果pos1和pos2指向的char相同, 那么就是取pos1 + 1和pos2 + 1构成的subproblem的答案 + 1; 如果不同, 那么就是取(pos1, pos2 + 1)和(pos1 + 1, pos2)构成的subproblem的最大的那个. 因此很自然得出:
如果pos1和pos2指向的char相同: dp[pos1][pos2] = dp[pos1 + 1][pos2 + 1] + 1
否则: dp[pos1][pos2] = Math.max(dp[pos1][pos2 + 1], dp[pos1 + 1][pos2])
写循环的技巧
写循环首先就是要明确, 注意是明确重复干的事情是什么, 其次就是什么时候这个循环会停止. 就这两步. 比如763题. 我们从头开始, 看第0个字符的最右侧能达到多少, 和rightBound比较更新, 然后让pos + 1, 如果此时pos + 1后小于等于rightBound, 我们继续看此时pos指向字符的最右端能达到多少, 然后和rightBound比较更新. 于是我们就发现重复做的事情就是看当前位置的字符右侧最远能到达哪里, 然后更新rightBound. 什么时候停? 当pos超过rightBound的时候, 此时leftBound和rightBound之间的字符不会再在后面出现, 于是停止. 这个循环的过程我们也要循环做. 即此时pos指向的又是一个新的partition的开始. 那么外循环什么时候停止? 当pos == s.length()的时候.
明确重复做的事情是什么, 明确循环停止的条件.
获取一个int的每一个digit的方法
不用加减号计算a和b的sum
a ^ b是当前a和b二进制数字相加后得到的值(不带进位, 只是0 + 0得0, 0 + 1或1 + 0得1, 1 + 1得0).
a & b是当前a和b二进制数字相加后得到的进位, 比如某一个位是1 + 1, 那么进位就是1. 由于这个进位要加在左边一位上, 因此需要(a & b) << 1.
当没有进位出现的时候, 这就是答案. 题目见371题
给定的数组中duplicates, missing number等等, 并且数字的范围有限制
Array index标记法.
BST level traversal
很多题都可以套用这个模板. 也就是遇到一个level, 首先看该level是否是第一次来(level == levelList.size() ?). 102题.
Monotonic Deque or stack
它的作用是给定一个数组, 我们能够知道任意位置比如i, 在i左边比nums[i]大的数字中index最大的那个是谁(previous greater), 同理也能知道i左边比nums[i]小的数字中index最大的那个是谁.
用排队来类比, 一个队从后面排, 如果你能打得过前面的人, 前面的人被踢出, 你能往前走一步, 一直到你打不过前面的人, 你就待在这里排队就行了.
类似地, 我们用一个deque, 存数组中数字的index. 从头(左边)开始遍历, 当我们来到index为i的位置时, 我们先看deque中比nums[i]小的数字都有谁, 有的就都出去, 直到deque是空的或者遇到比nums[i]大的数字了, 此时deque中last的那个index就是i左侧比nums[i]大的数字中index最大的那个index. 之后把i压进deque中走下一个位置.
这是decreasing deque(从左往右看是decreasing).
如果是构建increasing deque, 那么就是比nums[i]大的数字出去, 直到deque空或者有比nums[i]小的数字出现, 之后把i压进去即可.
为什么往deque中压index而不是index对应的数字? 因为我们可以通过index获取对应的数字, 同时我们也能知道这个数字在数组中的什么位置, 一举两得.
以上是Sliding window max收获.
至于是构建deque还是stack, 我们根据需要, 像是sliding window max, 我们需要每次都知道比某个数字大的的数字中index最大是多少并且也要及时清理window之外比该数字大的index对应的数字, 也就是两头都要操作. 那么用deque, 像是581, 我们不需要知道最大值或者最小值, 那么用stack也就够了.
一句话就是monotonic stack是为previous greater, next greater, previous smaller和next smaller问题而生的. Trapper rain water也是类似的. 我们到达一个地方后, 知道左侧max是多少, 但是不知道next greater有没有, 于是想到了monotonic stack.
关于monotonic stack最新的感想(这个结论十分重要)
我在床上睡醒想这个monotonic stack, 总感觉少理解点儿了啥, 这是因为我做了862这道题, 有些不解它的逻辑. 然后一直在想我对monotonic stack/queue的理解哪里出现了疏漏, 之后我得出了一个结论, 这个结论不知道对不对, 但我感觉应该是对的, 如果是对的, 那就理解了mono stack了. 现在我来说明. 以increasing stack为例, 我们在某个位置时, 我们按照规则是先把stack中比自己大的都pop出去, 如果pop到最后stack还有元素, 那么栈顶的这个数字就是在我们左侧, 距离自己最近的并且比自己小的数字的index. 意思就是对于index是i, i < pos(pos是我们现在的位置), 那些满足nums[i]小于nums[pos]的值中, 最大的那个就是栈顶的值. 问题就是此时stack装的index可能不止一个, 除了栈顶的, 下面被压的index是什么? 我们以栈顶为开始, 标记为0, 此时的值假设表示为stack[0]/(当然stack不能用index访问), 这里只是方便表达, 我们研究的数组假设为nums, 此时我们所在的位置是i. 那么stack[1]就表示栈顶下面这个数字. 我们就有nums[stack[1]] < nums[stack[0]]并且stack[1]是比nums[stack[0]]的previous smaller的index. 那么如果stack[1]下面还有元素, 那么stack[2]就是nums[stack[1]]的previous smaller的index, 如果stack[2]下面还有元素, 那么stack[3]就是nums[stack[2]]的previous smaller的index. 以此类推, 直到我们到达栈底, 假设这个位置是n, 那么nums[stack[n]]没有previous smaller.
感觉有些难以理解, 我们举个例子吧.
注意stack里压的是index, 我们维持的是increasing stack.
nums = [3, 5, 7, 35, 24, 27, 16, 29, 1, 4, 7]
stack一开始为空.
当i = 0:
stack是空的, 也就是到达了栈底, 那就说明没有比nums[0]小的数, 这也对应nums[0]确实没有previous smaller. 目前均满足我们的结论.
push 0进栈.
stack[0]
当i = 1:
此时nums[i] > nums[stack.peek()]于是不pop. 那么nums[i]的previous smaller的index就是栈顶的值也就是0. nums[0]的previous smaller没有, 因为0在栈底, stack中0之前没东西了, 这也对应nums[0]确实没有previous smaller. 目前均满足我们的结论.
push 1进栈.
stack[0, 1]
当i = 2:
此时nums[i] > nums[stack.peek()]于是不pop. 那么nums[i]的previous smaller的index就是1. nums[1]的previous smaller我们之前得出是0, 这也对应stack中1下面的0. 然后对于0, 因为stack中0之前没东西了(处于栈底), 所以nums[0]的previous smaller没东西, 也对应nums[0]确实没有previous smaller. 目前均满足我们的结论.
push 2进栈.
stack[0, 1, 2]
当i = 3:
此时nums[i] > nums[stack.peek()]于是不pop. 那么nums[i]的previous smaller的index就是2. 然后nums[2]的previous smaller是1也对应stack中2下面的那个1. nums[1]的previous smaller是0也对应stack中1下面的0, nums[0]没有previous smaller刚好也对应stack中0下面没东西(处于栈底). 目前均满足我们的结论.
push 3进栈.
stack: [0, 1, 2, 3]
当i = 4:
此时就有意思了, 栈顶是3, 此时nums[i] < nums[3]. 我们要把3给pop出去. 然后再看, 发现nums[i]比nums[2]大, 于是不再pop. 此时nums[i]的previous smaller就是nums[2]也就是nums[stack.peek()], nums[i]的previous smaller的index是2. 然后看栈顶的2对应的nums[2]的previous smaller是nums[1](这是我们之前得到的结论), 这也对应stack中2下面的是1. 然后看nums[1]的previous smaller是nums[0](这也是我们之前得到的结论), 也完美对应stack中1下面那个0. nums[0]没有previous smaller, 也对应0处于栈底. 目前均满足我们的结论.
push 4进栈.
stack: [0, 1, 2, 4]
当i = 5:
nums[i] > nums[stack.peek()], 此时nums[i]的previous smaller就是nums[stack.peek()], 也就是4是nums[i]的previous smaller的index. 然后看栈顶的4, nums[4]的previous smaller就是nums[2](我们之前得到的结论), 这刚好对应stack中4下面的那个2. 然后nums[2]的previous smaller是nums[1]刚好对应stack 2下面的1. nums[1]的previous smaller是nums[0], 刚好对应stack中1下面的那个0, nums[0]的previous smaller没有, 刚好对应0在栈底. 以此类推.
….
我们都能以这样的逻辑去走下去, 发现每一次都满足我们之前下的结论.
总结一下就是,
我们到某个位置i时, 我们想知道nums[i]的previous smaller是谁呢? 于是我们把stack中比nums[i]大的pop出去, 此时剩下的那个栈顶的值stack.peek()就是nums[i] previous smaller的index. 假设stack.peek()是j. j就是nums[i]previous smaller的index. 那nums[j]的previous smaller的index是谁呢? 如果stack中j下面还有东西, 那么nums[j]的previous smaller就是nums[栈中j下面的值], 假设stack中j下面的数字是z. 那么nums[z]就是nums[j]的previous smaller, z就是nums[j]就是previous smaller的index. 那nums[z]的previous smaller是谁呢? 假如stack中z下面还有数字假设是x, 那么nums[x]就是nums[z]的previous smaller. x是nums[z]的previous smaller的index. 那么nums[x]的previous smaller呢?… 我们还可以按照同样的逻辑去找. 直至我们遇到栈底. 假设栈底的值是m, 那么此时nums[m]没有previous smaller.
希望这个结论是对的.
精简代码背后蕴藏着复杂的思考
有时候精简的代码蕴含着复杂的思考迭代过程. 比如581最后一种解法, 为什么有的元素sort后的位置就是最后一次pop出来的index, 而有的不是. 有些写法是考虑到所有情况后总结出来的能cover所有情况的精简写法, 是复杂思考过程的高度简化. 因此我们一开始看不懂是太正常不过了, 我们从简单一点点复杂深入思考, 分类讨论, 来理解这些写法.
首先要记得我们要找的是最靠左的leftBound和最靠右的rightBound.
一开始如果一直是递增或者出现平台, 那么从0开始的每一个index都会被压进栈里面, 如果一直是这样, 那么说明array已经sorted了, 此时
返回0即可. 如果遇到到某个位置出现递减, 那么就要看左侧比它小的元素的对应的index都有谁, 于是我们开始pop, 当pop到某个位置,
发现栈顶的index对应的element比自己小, 那么这个index + 1就是我们sort后应该在的位置. 但是注意刚才我们pop的时候,
每一个从0开始的index都按顺序被push进栈, 因此每一个index都是互相相邻的,
于是我们最后一次pop的那个index比当前栈顶的index大1, 因此就是sort后我们应该待的位置.
记录下这个leftBound. 然后我们把自己的index压入栈中. 如果之后的数字始终没有把我们pop出来或者刚好把我们pop出来,
我们之前的index都没出栈,那么leftBound往左最远到达的, 就是我们第一次记录的那个leftBound.
如果出现不仅把我们pop出去也pop出了一个或多个我们之前的index, 那么一样的道理, 之前的index都是相邻的,
最后一次pop出来的值比栈顶的index大1, 那个值应该在的index. 当然也可能pop到栈里没东西了, 但这种情况也满足sort后在的位置
应该是最后一次pop的index.
这是当时581那道题的思考, 为什么可以写成l = Math.min(l, stack.pop()), 难道不应该是pop不动时栈顶的index + 1才是该元素sort后应该待的位置吗? 这个解释就解决了我们的疑惑.
需要知道多少元素满足条件, 哪些没有满足条件
395题, 我们需要知道window中的char的count是否都超过K, 只有这样, 此时的window包含的substring才是满足题意的. 我之前使用Set来存哪些char的count没有超过K, 然后每次看set是否为空来判断window中的char的count是否都超过K. 更聪明的做法就是用一个变量记录window中count超过K的cha的个数, 因为我们不需要知道具体是哪些char的count超过了K, 只需要知道数量就行, 当这个数量和window中的unique chars的个数相同时, 我们就知道所有的char的count都超过了K. 这个思路很常用. 当我们不需要知道特定哪些元素满足某个条件但是又想知道是不是在某个范围内所有的元素都满足条件的时候, 我们就用变量记录满足条件的元素的个数, 然后当满足条件的元素的个数和范围内元素的个数相同时, 说明此时所有的元素都满足了条件.
ArrayList的constructor可以直接扔进去个set
实际上只要是collection就行. 具体见官方文档.
BFS打标签
其实是在level order traversal中比较好用的一个点. BFS无非就是pop出该level的所有的node, 把下一个level的node添加进来. 我们用一个变量记录我们当前的level是多少. 在开始该level的BFS前(该level的BFS就是把该level的node从queue中pop出来, 再把下一个level的node添加进来的过程), 变量记录的值表示现在queue中node属于哪个level, 在我们BFS过后, 我们让变量 + 1. 此时变量记录的值表示现在的queue中node属于哪个level. 切记这两个判定点, 一个是BFS前, 一个是BFS结束更新完level变量.
Bucket Sort
这个是在给定一个array, 想知道每个元素出现的频率从大到小排是什么样的时候, bucket sort就起作用了. 先统计每个元素的频率, 并得到
出现最多次数的频率是多少, 之后再分配一个长度为最多频率 + 1长度的list, 每个位置放一个list来存对应的元素. 元素根据自己的频率到这个
list中相应index的bucket, 也就是这个list中装了许多list(bucket), 元素的频率就对应着应该在这个list中哪个index的bucket.
然后反着遍历即可按照频率从大到小找到元素.
log1 + log2 + log3… + logn也就是log(n!)是多少
O(log(n!)) = O(nlogn)
下面这个网页是证明过程.
https://math.stackexchange.com/questions/482860/how-to-calc-log1-log2-log3-log4-log-n
Prefix sum
对于那种prefix sum凑数的题, 首先看自己是否能凑到, 再看我是不是要减去前面某个prefix sum来凑到target. 这个先看自己再看别人的思路很重要.
BigDecimal
记得如何使用BigDecimal
Cyclic sort
把数字放到它应该在的位置. 比如给定一个nums. 假设长度为n, 那么在1到n的范围内的数字, 1的位置是index 0, 二的位置是index 1, 三的位置是index 2…以此类推. 我们从左开始遍历, nums[0]如果不在应该在的位置, 那么把它放到它应该在的比如x这个位置, 那么nums[x]的值就被交换到了0这个位置, 可能nums[x]也不应该在0这个位置, 于是继续放. 直到我们交换来一个nums[m], nums[m]应该去的位置发现就是nums[m], 这就说明我们把尽可能多的数字放到了它们该去的位置, 再继续下去没有意义了, 因为就是相同数字开始反复互相交换. 于是我们到nums[1]开始继续这个过程. 前提就是nums中的数字必须是在1到n的范围内. 像是41题找first missing positive. 有些数字可能出界, 那么这些数字我们就不考虑. 到最后遍历完数组后, 在范围内的数字就能在它们该在的位置, 我们再从头遍历, 看哪个数字没有在该在的位置, 这就说明这个位置该有的数字missing了, 于是就返回它即可.
这应该也是给定nums, 长度为n, 假设nums中的数字就是1到n, 想出O(n) sort的方法.
旋转矩阵
顺时针转: 先转置, 再左右reverse.
逆时针转: 先转置, 再上下reverse.
Sliding Window其实就是剪枝
突然感觉sliding window就是把brute force所有substring都试一遍的升级版, 也就是有些substring我们通过逻辑判断就知道不可能是答案, 因此直接排除, 没必要再看.
比如当right达到某个位置不满足题意的时候，以现在的left为start，以right现在的位置以及右侧的位置为end来界定的substrings都不会满足题意或者不会是答案，于是我们没必要遍历，提前剪枝, 直接让left右移，发现sliding window框起来的还不满足题意，那一样的以当前left为start的所有substring都不满足题意或者说都不够好来成为答案，可以直接继续移动left。
sliding window是capture了一个substring。我们根据一些判断逻辑只研究有可能是答案的substring并且不研究哪些被逻辑排除掉的substring。
比如424题, 我们初始化left为0, right为0, 然后让right开始走. 当走到一个位置发现sliding window里的除了拥有最大frequency的其他char的数目大于k的时候, 此时以left为start的substring最长满足题意的就是[left, right)框起来这个区间, 左闭右开. 为什么? 如果right继续移动, 假设之后window里的freq最大的char没有改变, 那不用说, 本来剩下的char的数目就大于K, 往后只可能剩下的越来越多, 最好情况也就是剩下的数目不变, freq最大的char的个数一直在增加, 因此不满足题意; 如果后面在某个时刻freq最大的char改变了, 此时我们来证明一下. 首先我们假设在之前right停止的位置, 最大freq char假设是‘a’, 个数为x个, 下一次将成为max freq char现在的count是y, 其余剩余的char个数为z个, 此时总个数为x + y + z个, 我们把总数记为S1. 此时有S1 - x > k. 那么到了某个时刻, 最大freq char换成比如说‘b’了, 假设‘a’增加了m1个, 此时count是x + m1, ‘b’增加了m2个变为了, 此时count是y + m2, 其余的char的总增量是m3, 因此现在就是z + m3. 我们要判断的就是x + z + m1 + m3是否大于k. 我们知道此时的y + m2 > x + m1. 于是我们有:
S1 + m1 + m2 + m3 – (y + m2) > S1 + m1 + m2 + m3 – (x + m1)的
不等式右边又有:
S1 + m1 + m2 + m3 – (x + m1) == S1 -x + m2 + m3
我们知道S1 – x大于k并且m2 + m3是大于等于0的, 因此不等式右边是大于k的. 由于左侧大于右侧, 那么左侧也是大于k的, 而左侧正是此刻除了b以外, 其他char的total count. 至此, 我们证明完毕.
所以sliding window能成的重要原因就是可以通过逻辑排除.
到这里, right不满足题意, 以left作为start, 以right及其它之后的位置作为end的所有substring都不行, 于是我们记录此时的left和right界定的长度 – 1, 因为不包括right. 然后移动left一格. 此时如果pop走的不是max freq, 此时window里的非max freq char就满足题意了, 我们可以继续走, 至于为什么移动一步left就满足, 见我之前写的注解. 简单来说就是来到right前一定满足非max freq小于大于等于k. 来到了right发现大于k了, 说明引入了非max freq char, 我们左侧如果移走一个, 那window就valid了. 如果pop走的是max freq对应的char, 那么我们就要看pop完后的maxFreq是谁, 再看剩下的其他char的count是否满足题意, 如果是那right可以继续走了, 如果不是那继续移动left. 我们是在right走不动的时候计算maxLength.
网友给的答案很巧妙. 当right走不动的时候, 说明right上一步在的地方框起来的window还满足题意, 现在不行了. 于是我们会计算此时的substring length就是right – left因为我们不包含right. 但是网友不这么干, 它此时先让left右移一位, 此时right – left + 1和之前的right – left一个长度. Left向右移动一位后, 我们记录此时的大小并且和maxLength比较. 目前为止, 不管是移动left前right – left还是移动left后的right – left + 1. 得到的值都是一样. 然后这里就面临了一个问题, 刚才pop出去的是max freq对应的char吗? 如果不是, 那么此时的window已经valid了, right可以继续走; 如果是, 那么此时的window可能是valid, 也可能不是, 常规操作就是去缩left, 然后等到window valid之后再去移动right. 但其实不用缩. 因为我们是求最长的, 那么此时我们的window扩展到了这个地步, 我们就按照这个window size走, 如果后面还能扩, 我们继续更新maxLength, 如果不行我们就维持这个size一直到结束. 不缩window size是这道题的关键.
Quick sort和quick select的口诀
升序, 大小小大, 对应第一个if的两个判断条件和后面两个if的判断条件.
降序, 小大大小, 同样是对应那四个条件.
如果想不出答案, 想一想答案的特征是什么
寻找最后答案的特征 然后遍历所有拥有这个特征的情况 从中找出我们的答案. 比如histogram那道题 答案的特征就是总会有一个bar作为minimum，遍历所有bar做minimum的情况，计算每个bar做minimum时的largest rectangle，最后得出全局最大.
求两个数字谁距离某个数字近
比如给定两个数字x, y并且x < y. 再给我们的数字n, 求谁距离n近.
比较n - x和y - n的大小即可. 此时必须满足x小于y, 如果x大于y, 那么用这个不等式判断得出的结果是不对的. 毕竟如果x特别大, y等于n等于1, 不等式左边则是很小的数字, 而不等式右侧为0, 此时我们会认为x距离n更近其实不是. 这个结论的启发来自于658题.
Binary Search搜索平方数的用法
就是比较mid的平方和target(因为这里我们搜索的范围是1到某个值, 中间是连续的, 而不是去在某个数组里面搜索, 因此我们直接用mid). 问题就是mid的平方可能会出界. 于是我们想到使用mid和target / mid比较. 如果mid < target / mid. Target / mid可能会带小数, 然后舍弃掉, 即使这样也比mid大, 那说明mid太小的, 应该让right = mid + 1. 如果mid > target / mid. Target / mid可能带小数舍弃掉, 舍弃掉后, mid比target / mid大, 那说明二者整数部分mid就比target / mid大, 即使target / mid带上小数部分, mid也是更大的, 因此此时让left = mid – 1. 如果mid == target / mid, 我们要分两种情况, 一种是target / mid没有小数部分, 刚好整除, 那么此时mid就是target的平方根; 如果target / mid带小数, 那么说明这个mid是小, 从而让target / mid拥有了小数部分, 因为mid和target / mid就是此消彼长. 因此我们要让right = mid + 1, 但其实此时已经可以判断target的平方根不是整数了. 因为mid + 1的平方肯定大于target. 因为现在是mid * (mid + target / mid的小数部分)刚好等于target, 那么mid + 1乘上mid + 1则是让两个乘数都变大了, 那结果一定大于target.
总结就是, 如果mid < target / mid或者mid > target / mid不需要考虑小数舍弃这种, 就按实际生活里的计算对待, 此时就是mid比较小或者mid比较大. 等到mid == target / mid时, 再去考虑小数的舍弃问题.
什么时候想到用prefix sum
Subarray凑数的时候. 或者说看到有subarray出现的时候.
brute force优化
从brute force进行优化其实用的就是我们是否能用逻辑排除一些情况, 从而不需要让程序去走这些情况节省时间. 只让程序去走可能的情况, 从而告诉我们这些可能的情况中我们想要的答案. 重点就在于逻辑推理. 可以看84, 632以及424题我的逻辑推理, 如何排除一些不可能的情况.
使用Java提供给我们的Pair<K, V>这个class
有时候, 我们需要用到Pair, 也就是自己创建一个inner class来存两个field, 比如vertical traversal那道题, 要存每个node的col是多少, 此时我们可以使用java提供给我们的Pair这个class, 它的用法就是直接Pair<K, V>就完事儿. 具体看314题的演示. 获取第一个field就是getKey(), 第二个field就是getValue().
Combination, subsets题的想法
其实就是找谁当开头的问题. 答案就是在pos及以后的范围内, 轮流当开头. 走遍所有情况. 如果有出现不允许duplicates出现的, 那么先sort一下nums, 然后让当过开头的数字不能重复当即如果某个数字和它前一个数字一样, 那它就不能当开头了.
做树的题的时候, 一路返回因为路线是固定的, 也能构建东西
2096题就是这样的. 找到一个node后, 返回的时候一步步记录怎么走.
Sweep-line algo
关于intervals的题很好用. 我们记录一个score, 我们认为到一个interval的start, score加1, 到一个interval的尾, score – 1. 当然要按时间线从前往后遍历各个interval开始和结束的点. 在遍历的过程中, score不可能为负, 如果为负, 表示遇到的start比遇到的end少, 这是不可能的, 因为interval的start一定小于等于end. 这样我们能够得到这些intervals间的空隙(空隙是指没有任何一个intervals覆盖到的范围). 具体见759题.
如何确定某个元素的初始值
如果不好确定的时候, 看看我们下面写的循环, 找到某个条件符合我们初始值所在的情况后要把某个元素更新成什么值. 我们假设当前的状态是满足了这个条件, 那么按照这个条件的逻辑去更新值. 举个例子, 第759题, 开始时freeTimeStart初始为什么好? 我也不知道, 我不知道一开始的freeTime从哪里开始, 于是我看下面的while循环, 里面一个是当前的interval和之前merge好的大interval有交集, 此时更新freeTimeStart为end大的那个, 要么就是此时interval和上一个end没有交集, 也就是在我们这个interval的start处休息完毕, 那么此时让freeTimeStart初始化为当前interval的end, 也就是假设这个interval干完就能歇. 于是我们一开始可以认为我们是歇好了, 于是也是假设当前interval干完就能歇, 于是让freeTimeStart初始化为pq顶的interval的end. 但其实一开始这么想也行, 这个顶部的interval是最早开始的, 假设它完成就能歇, 当然如果之后能merge, 这个歇的时间可能要一直往后延伸.
String到char array以及char array到String
String到char array就是toCharArray()即可, char array到string就是new String(charArray)即可.
对递归的新想法
递归的用处其实就是某个问题能够转化为subproblem, 我们知道了subproblem的答案就知道了现在问题的答案. 最重要的是subproblem的形式和我们当前problem的形式是一样的. 比如斐波那契. 我想知道第100个数字是什么, 那么我需要知道第98和99个是谁, 我们发现得到第100个数字转化为了得到第99个数字和第98个数字. 此时我就想要知道第99和数字和第98个数字是什么? 那么这两个subproblem和原始的problem的形式是一样的. 都是想知道某个斐波那契数字是多少.
因此这就是为什么可以调用递归的原因了. 都是解决相同的问题, 只不过每一次解决的问题是给的参数不同. 于是我们定义递归函数功能的时候就要注意. 要有普适性. 我们默认递归函数能够完成我们要求它完成的任务, 然后以这个前提去写递归函数的逻辑. 递归函数的base case就是给定我们一个参数后, 我们能快速知道答案, 不需要再转化为subproblem. 但是有些时候, 答案很tricky, 需要我们根据需要去决定. 比如给一堆硬币凑数, 问凑成这个数有多少种凑法. 那么如果我们写dp, 就会有凑0有多少种? 1种, 为什么呢? 我们可能会说所有数字都不用不就凑到了, 但我也可以说用现有的数字就没法凑到. 我感觉更好的解释方式就是这个subproblem的答案是被谁用了? 我们可能会想知道凑成某个数比如dp[i]有多少种凑法. 那么我们会遇到一种情况就是如果凑数最后一个数字是i, 那么此时有多少种呢? 我们就需要知道dp[i – i]有多少种, 在能凑成它的前提下在每一种后面加个i即可. 但其实此时我们不需要转化为subproblem即求dp[0]有多少种, 我们知道此时如果i结尾只能一种. 但是如果硬要按照我们这个逻辑去转化subproblem, 为了让这个逻辑成立, 帮助我们得到正确答案, 我们让dp[0]等于1, 这样我们知道dp[i – i]的凑法只有1种, 那么我们在这唯一一种的后面加上i即可, 此时就是i结尾的时候凑i有多少种凑法.
综上来看, 递归函数解决的是相同的问题, 但是给的参数不同. 有些参数给定后, 我们知道答案, 无需转化为subproblem. Base case值的确定需要看哪些problem需要base case的答案, 通常需要base case的problem, 我们也能直接知道答案, 为了满足我们的逻辑(这根据题目的不同而不同, 也就是如何利用subproblem的答案来得到此时problem的答案), 我们让base case的答案认为设置为能符合我们逻辑的值, 来返回给需要它的problem, 从而让该problem得到的答案也是正确的. 正如我上面举例的凑数.
LC 256题讲解. 关于DP和Greedy Algorithm. 只能说Hai_dee yyds
Justifying why this is a Dynamic Programming Problem
Many dynamic programming problems have very straightforward solutions. As you get more experience with them, you’ll gain a better intuition for when a problem might be solvable with dynamic programming, and you’ll also get better at quickly identifying the overlapping subproblems (e.g. that painting the 3rd house green will have the same total cost regardless of whether the 2nd house was blue or red). Thinking about the tree structure can help too for identifying those subproblems, although you won’t always need to draw it out fully like we did here.
Remember that a subproblem is any call to the recursive function. Subproblems are solved either as a base case (in this case a simple lookup from the table and no further calculations) or by looking at the solutions of a bunch of lower down subproblems. In dynamic programming lingo, we say that this problem has an optimal substructure. This means that the optimal cost for each subproblem is constructed from the optimal cost of subproblems below it. This is the same property that must be true for greedy algorithms to work.
If, for example, we hadn’t been able to choose the minimum and know it was optimal (perhaps because it would impact a choice further up the tree) then there would not have been optimal substructure.
In addition this problem also had overlapping subproblems. This just means that the lower subproblems were often shared (remember how the tree had lots of branches that looked the same?)
Problems that have optimal substructure can be solved with greedy algorithms. If they also have overlapping subproblems, then they can be solved with dynamic programming algorithms.
link: https://leetcode.com/problems/paint-house/solution/
关于dp倒着解
在解house paint那道题的时候, 最后的dp是倒着往上走的. 这样会觉得很奇怪, 但是其实并不是什么大事儿. 如果真想从前往后走, 那么可以这么想. 我们的想法是第0个房子确定一个颜色后, 我们需要知道后面房子不是该颜色的情况下最小是多少; 然后看第0个房子涂三种颜色, 每种颜色后面房子的minimum各是多少. 那么我们反转一下, 这个第0个房子是不是可以看成最后一房子呢? 就跟我们从正面看这个array, 我们走到array后面也是同一个, 但是顺序反了. 这并不影响答案. 正反只是我们主观的认为, 不改变它客观的最小值. 一样的思路, 如果最后一个房子涂了某个颜色, 我们需要知道之前上一个房子不涂该颜色的情况下的minimum, 同样地三种情况取最小即可. 此时dp就得出来了.
规定dp[i][j]是在i个房子涂j的前提下, 从j到第0个房子minimum是多少.
dp[i][0] = Math.min(dp[i – 1][1], dp[i – 1][2]) + costs[i][0].
dp倒着解还有哪个edit distance那道题, 其实也可以认为字符串的开头是字符串的结尾. 这样也可以让dp从左往右解了.
尽量避免否定
dp中, 尽量避免某个状态定义为不怎么怎么. 通常我们尽量避免不…., 这样会让逻辑变复杂. 比如上面的, 第0个房子涂红色, 我们需要之后下一房子不涂红色的前提下, 从下一个到最后一个房子涂墙最小值, 那其实就是下一个房子涂蓝色和涂绿色哪一个更小. 因此我们dp[i][j]可以设计为, 从第i个房子开始, 涂j颜色, 从i到之前第0个颜色最小刷墙值是多少. 这样把不转化为它的相对面, 这样就会好思考一些.
看labuladong的感想
用计算机解决问题就是穷举. 当然如果能发现规律, 找到公式直接计算更好, 但是一般都很难. 我们之前的数学思维告诉我们如果是穷举找答案, 那大概率是思路出问题了, 但是计算机思维恰恰相反, 如果能穷举所有情况并且在时间复杂度允许的条件下, 这为什么不行呢? 毕竟这是计算机啊, 它可比我们大脑运行速度快太多了.
当然穷举也不容易, 需要做到不遗漏, 不冗余. 我们不能走极端, 不能说要么找到一个公式直接得出答案, 要么穷举所有, 即使那些不可能的也穷举. 我们应该找到一个平衡, 找不到一个好的公式, 那我就穷举, 但是穷举也不是所有情况都穷, 而是我能至少用逻辑推理来排除一些不可能的情况, 从而在该情况下的之后的子情况都不可能. 这样的穷举是高效的, 也是明智的.
因此当我们遇到一道题要穷举时, 我们需要想怎么样能保证不遗漏任何一种可能是答案的情况(不遗漏), 同时如何避免取穷举我们知道肯定不是答案的情况(不冗余).
一般比较难想到最普通穷举方法的问题就是递归类问题, 经典的就是动态规划. 其实动态规划的本质就是数学归纳法. 如果知道某某某, 我就知道现在的答案, 而知道某某某又需要知道再之前的一个某某某, 一直到某个时刻, 此时的答案我们可以轻松知道获得, 那么我们再一路向上就只能知道我们想要的答案了.
一般比较难想到的聪明地穷举方法的问题是非递归算法的技巧, 比如union find. 这一种高效计算连通分量的技巧. 我们普通使用BFS/DFS肯定能解, 但是UF直接把操作复杂度干到O(1)你敢信.
因此对于一般的穷举方法, 我们要多练, 找到数学归纳的关系, 建立递归, 然后引入memo, 最终实现自下而上的dp方法. 而对于聪明地穷举, 我们需要学习其他高人总结出来的算法, 学习它们如何聪明地穷举.
回溯(递归)问题都可以认为是树的结构. 这么想非常有道理, 继续调用递归就是树往下走一个level, 返回就是往上走一个level.
二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。这句话和我之前想的也是类似, 有时候当前不能知道答案, 但是返回后可以告诉我们答案. 比如clone graph和那个house robber III, 都是返回来的时候, 我们知道子情况的答案, 从而可以完成我们当前的操作.
递归两种形式
现在来看分解问题计算答案就是给递归函数设置功能, 明确指出它能告诉我们什么信息, 我们利用递归函数得到我们的信息然后来计算我们想要的结果. 而回溯则是我之前说的所谓的加工, 走一层加工一层, 返回前把加工的东西都复原, 来的时候什么样, 回去的时候还是什么样, 这和我之前的总结一模一样!
怪不得我走回溯的时候很自然, 其实就是走一步加工一步; 但是我走分解问题的时候就要考虑递归函数的功能. 这样看来这是两种不同的类型.
回溯就是recursion + memorization而分解问题其实就是DP.
labuladong二叉树的解题思维模式
先在开头总结一下，二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。这是关键.
二叉树问题应该思考什么
你只需要思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会对所有节点做相同的操作。
遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历.
DP
首先，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。而且，你需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素.
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。
有时候我们把问题到最坏考虑, 比如凑硬币, 无非就是个树的结构, 然后一步步延伸,
354和1996的启发
就是关于给一个array, array里的元素是一个pair, 我们要找某个pair是不是有比自己两个field都大的pair. 以及找longest increasing pair sequence, 也就是sequence中除了第0个pair, 每一个pair的每一个field都比前一个pair的每一个field要大. 这里就需要用到先在一个pair的field按照顺序去, 另一个field按照倒序去sort这个array. 这个trick很好用. 比如354套娃这个, 我们先把width按照顺序sort, 然后找height的LIS, 但是我们担心sequence会取一样的width的pair, 于是我们把height再倒序排, 这样我们就能保证最长sequence中的每个pair的width都不会相同. 1996也是类似, 我们要找比自己attack和defense都大的pair, 那么我们先把attack倒序排, 然后从左到右记录最大的defense, 如果遇到pair的defense小于它, 那该pair就是weak. 但我们担心如果贡献这个最大defense的pair和当前pair有一样的attack呢? 于是我们让defense顺序排, 这样相同的attack的pair的defense左边的一定小于等于右边, 我们边走边记录最大的defense, 如果发现某个defense的值小于我们记录的defense值, 那么贡献这个我们记录的defense的值一定和当前的pair不具有相同的attack值.
穷举, 让每个元素都成为一次最终答案
这个点很难明说, 举个例子吧. 比如largest histogram那道题. 什么叫做让每个元素都当一次最终答案? 这道题最后的答案肯定是一个或多个构成的rectangle面积最大, 那么肯定会至少有一个bar是最低的. 那么我们就轮流让每个bar当最低的, 在每个bar当最低时, 求此时最大能组成的rectangle的面积是多少, 当我们知道每个bar当最低的时候最大的rectangle的面积是多少的时候, 取全局最大即可.
另一个例子比如2013这道题, 给一个点, 看能和之前添加的其他点凑成多少个正方形. 我们想最终的凑法里面, 肯定有个点是当和我们给定点相对对角线的那个点的. 于是我们让所有加入的点做给定点的对角线(如果能做成的话), 然后看此时能凑成多少个正方形, 然后把所有的凑法加在一起就可以了.
于是我们多想一想最后的答案的特征有哪些, 然后让所有元素都做一遍, 取我们想要的即可.
index计算
给一个index, 如何知道该index前有多少数字(不包含该index指向的数字)? Index个, 如果包含那就是index + 1个. 记住之前有index个即可. 如果知道某个index前有x个数字, 那么该index就是x.
做1235的感想 避免让递归函数进入多次重复的情况
在决定递归逻辑的时候, 我们要好好想想. 取某个区间的max profit, 我们让区间内每个period当开头, 看这样每一个构成的区间的max是多少. 求全局最大即可. 这样会重复很多次考虑同样的情况, 即使用memo记录也会TLE. 于是需要一个更好的思路. 其实就是要么该区间第1个period被选, 要么不被选, 就这两种情况, 看哪个max更大即可.
跳bug那道题1654
必须先往后跳, 再往前, 因为先往前再往后会漏情况.
比如此时我在m我先往前x, 再往后y. 就到了x + m和 m - y处. 按queue的顺序, 我会开始看x + m这个位置, 我还是先往前再往后, 于是到x + 2m, x + m - y.
然后从queue中poll出m - y处, 我们此时只能往前到x + m -y处, 此时由于之前到过, 我们会不再往queue中压这个地点. 然而这是不对的, 之前是往前跳一步再往后跳到达x + m - y, 此时不能往后. 然而如果是先往后, 再往前到达的x + m - y, 此时是可以往后的, 于是先往前后往后的走法就走不到x + m - 2y这种情况. 于是就漏了情况了.
BFS要考虑两点
一个是是否需要严格按照level去BFS, 也就是给每个level打标签. 还有就是是否需要防止装进queue的东西被重复装入, 比如解决grid类型的题, 我们要防止同一个位置被重复装入queue中.
遇见数组和string
尝试sort; 正着看, 反着看; 看有没有范围.
关于取mod
(a + b) % c = ((a % c) + (b % c)) % c
(a - b) % c = ((a % c) - (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c
等于是取mod的位置很灵活.
优化的一个思路(有没有重复计算一些东西)
优化的一个思路就是看我们有没有重复计算一些什么东西. 如果有, 想办法把之前计算出来的结果记下来, 或者间接记下来然后能用O(1)的方式去计算获得. 比如prefix sum, 比如recursion + memorization.
一说到等价就得联想到UF
等价关系其实就可以抽象为graph的问题. 使用并查集就很方便.
Quick find:
Array存的是每个node的root node而不是parent node. Find的话直接返回array中对应index的值即可. 这是O(1)操作. 而union的话, 比如x和y合并, 我们假设y合并到x. 那么所有node中, root是y的node都需要把它们的root改为x的root. 这是O(N) 因为我们要遍历数组, 让每个元素等于y的root的地方都变为x的root的值.
这种方式可以想象成一个只有两个level的tree. 第0个level是root node, 而剩下的只要是root是该root node的node都直接和root node相连. 如果两个不同的tree合并, 那么就要把一个tree中的所有node的parent指向改为指向另一个tree的root.
Quick union:
这个则是array中存的是每个node的parent. 对于find, 我们需要看node的parent是否是自己, 如果不是, 那么就看parent node的parent是否等于parent node, 如果不是我们继续找. 直到找到某个node的parent是自己, 那么这个node就是root node. 很显然这个操作是O(n)因为可能disjoint set是一个链表. 对于union, 我们想合并x和y两个node, 首先, 我们要找到x和y的root node是谁, 当二者的root nodes不同的时候, 我们让一个root node并入到另一个, 比如让y的root并到x的root, 那就是改变y的root node在array中的parent的值变为x的root node. 由于我们有找·root这个操作, union也是O(N)复杂度.
这里可以认为find就是从leaf一直往上找, 此时的树的level可以有多层而不是像quick find那样只有两层. Union则是让某个tree的root成为另一个tree的root的一个child.
Quick union比quick find更高效, 这是因为quick union只有在最坏情况, union才是O(N), 因为union的操作依赖find, find的最坏情况是O(n). 而quick find的union每次都要遍历整个array, 因此是固定O(N). 那么如果进行n次union操作, quick union的复杂度是小于等于O(n^2)而quick find则是恒等于O(n^2).
上述说的两种方式效率都不是很高.
对quick union的优化
当我们union两个node的时候, 我们是先找二者的root, 然后选一个root作为新root, 再把两个root归到这个新root之下. 这样有可能导致树是skewed的, 也就是形成链表. 于是我们再用一个数组来存储每个node的height. 如果要合并的两个node的root中有一个root的height更小, 那么它就不能当新的root而是要合并到另一个root之下, 因为如果height小的root成为新root, 合并完后的root将会变得比此时两个root本来的height都大, 而小的height的root合并到大的height的root下, 此时合并完后的tree的height还是合并前height比较大的那个. 如果两个tree的height相同, 那么随意挑一个成为新root即可, 此时我们需要更新rank里面新root的height, 需要让它的height + 1. 因为另一个tree的height归到了该root之下, 那么高度也就自然 + 1了. 这样可以让tree尽可能balanced.
Path compression
如果是个skewed tree. 比如:
1 -> 2 -> 3 -> 4 -> 5
那么如果想知道箭头由child指向parent, 也就是node 1在parent array中记载的它的parent是2, node 2在parent array中记载的它的parent是3…以此类推. 那么如果我想知道1的root, 我要遍历整个tree, 如果想知道2的root, 同样要从2遍历到开头, 这个path我们在获得1的root的时候也走过. 那么有什么方法利用已经走过的路吗? 那就是用递归找root, 在找到后把自己的parent设置为root. 这样本来是skewed tree就变为了更矮的tree. 比如我想找1的root, 那么我一路向下到了5, 发现5的parent是自己, 此时找到root返回到4这一层, 4找到自己的root是5后让自己在parent array中对应的位置设置为5, 然后返回到3这一层, 3知道root是5后让自己在parent array中对应的位置的值变为5, 然后返回2这一层…以此类推. 这样的话, tree就变成了以5为root; 1, 2, 3, 4为child的两个level的tree. 这样就充分利用了找1的root的计算结果. 等于是把tree给compress了. 当然我们不一定要找一个leaf node的root, 比如我们可能找3的root, 那么我们就会把4的parent设置为5(本来也就是), 然后3的parent设置为5, 但是1和2的parent不变, 这样高度为5的tree就变为了高度为4的tree. 这就非常好.
然后把union by rank以及path compression合并就是我们最终union find的模板了.
把连续挨着的字符先count再append该字符
比如aaabbbc写为3a3b1c, 对标题目是count and say. 用一个变量记录当前在重复的char是谁, 用count记录重复了多少次. 然后遍历即可, 如果和currChar相等, count += 1, 如果不等, 更新currChar, count重置为1. 一开始currChar是string的第0个元素, count初始化为1, 从第1个字符(而非第0个字符)开始遍历, 因为第0个字符我们手动遍历了. 在循环结束后, 我们手动把结尾重复的字符给算上. 因为结尾重复的那几个字符是没有计算上的, 它们的信息只是存在count和currChar中.
两个字母间的距离(取二者直接的距离或者wrap around的距离的最小值)
这个好像用的地方也很多. 其实就是Math.min(Math.abs(letterOne - letterTwo), 26 – Math.abs(letterOne - letterTwo));
这个公式是简化后的样子. 正常思考时看哪个letter靠后(ascii码大), 然后得到直接的距离是letterBig – letterSmall. 如何得到wrap around? 先让letterBig到0的位置, 0的位置可以认为是25后一个位置26, 那么就是26 – letterBig. 然后再加上从0到letterSmall的位置也就是letterSmall, 于是合在一起就是26 – letterBig + letterSmall = 26 – (letterBig – letterSmall).
上面用的letterBig, letterSmall是字母的index, a是0, b是1以此类推. LetterOne和letterTwo可以是本来的字符因为只牵扯到字符减去字符.
