Home - ShuweiLeung/Thinking GitHub Wiki

Welcome to wiki!

Array -> String -> Math -> Tree -> Hash Table -> Linked List -> Stack -> Two Pointers -> Heap -> Queue -> Greedy -> Dynamic Programming -> Depth-first Search -> Breadth-first Search -> Binary Search -> Backtracking -> Bit Manipulation -> Design(未全部做完)

  1. 单调栈
  2. Two pass(forward and backward): 从前向后和从后向前各一遍，通常用来求距离或DP问题（LC 821）。注意对二维数组，有从左上->右下和右下->左上两种pass的变种(LC 361)
  3. Two pointers
  4. Sliding window
  5. Dynamic programming，除了用数组进行DP状态存储以外，也可以用Map来存
  6. Greedy
  7. Stack
  8. PriorityQueue
  9. 如果原来数组中的数字为正，则将其置为负数与其他元素以作状态区分。
  10. Divide and Conquer,感觉LC 241很好，divide and conquer以及递归的结合
  11. Properties of BST. Inorder traversal.
  12. Recursive/DFS：通常都要设立一个visited数组，或者map和set也行（O(1)时间复杂度）
  13. Binary search
  14. BFS通常用来求最短距离(LC 1091)。求tree上距某个结点特定距离的结点，也需要先将树转化成无向图 LC 863
  15. Union Find
  16. Stack 先进先出特性
  17. 将数组作为水桶，访问一个元素则将对应位置的值+1或-1
  18. 对数组求和，计算missing number
  19. 用二进制的one bit作为掩码mask
  20. 用quick sort的哨兵作为分界线寻找kth largest element
  21. 当题目要求和数组index有关，且前一个change会造成数组原来后面的元素index的修改，可以从index较后的change开始处理，从而不影响前面的index改变
  22. 一种很好的利用字符串截取和hashmap并行判断subsequence的方法：792. Number of Matching Subsequences
  23. 在list中删除中间元素而不改变后面的元素索引的方法，是将其与list的最后一个元素调换，只修改最后一个元素的索引，然后删除最后一个元素即可（O(1)复杂度）
  24. Full Binary Tree如果根节点是n,左子树根节点则为2n，右子树根节点则为2n+1（一般题目若提到完全二叉树，通常会利用这个性质）
  25. 拓扑排序
  26. 从A到B以条件C访问可以看作从B到A以条件-C访问
  27. Trie字典树，TrieNode的children除了可以用int数组来表示以外，还可以用HashMap来表示，这样的话，可以表示的字符更多，不仅仅限于26个英文字母，如LC 642
  28. Two pointers滑动窗口，有时可以借用map来存储字符及该字符最后一次出现的位置索引(或者相反的关系)，从而根据读取map直接滑动左窗口边界，如LC 3
  29. 一般，word集合问题一般都要将list变成set，方便O(1)时间复杂度进行判断
  30. 多叉树的序列化需要保存孩子结点的数量，因为孩子的个数是不定的，必须得存储该信息才可以反序列化(LC 428)
  31. 用一个最大堆和一个最小堆找中点median，[1,2,3] X [4,5,6]
  32. 链表若从最后一个尾结点逆向往前进行操作，可以用stack顺序存储链表结点，然后弹栈进行链表从后往前的逆操作
  33. 若要求连续数组的和为target的k倍，则只需要用map存储subarray sum对target取的余数以及对应sum的index即可，查找同样的余数是否在之前出现来判断有没有符合条件的子数组(LC 523)
  34. Stack虽然是先进后出，但对于输入的List可以从后向前将list中元素入栈，这样在出栈过程中实际上是从前向后遍历list的元素（LC 341）
  35. Outside-in方法，从外围向中心逼近处理元素
  36. 当前后多对多关系需要concatenate时，可以在当前层直接while循环遍历重复的片段处理即可（LC 1087），对于前后没有关联的一对多关系，可以使用dfs进行处理（LC 394）
  37. 求一个字符串的所有subsequence，dfs时，遍历的路径可以选择拼接当前的字符和不拼接当前的字符两种情况。对于第一种情况，当选择拼接当前的字符且之前的path为空时，包括了以当前字符为头新起一条搜索路径的情况。
  38. 在树上找距离某个node距离最近的leaf，可以先将树转化成图，然后从target node开始BFS找距离最近的leaf（LC 742）
  39. 文件路径的题目首先要想到用Stack方法去做
  40. 滚动数组可以降低空间复杂度
  41. 二分查无限大size的数组中元素，通过移位操作去锁定上下界(LC 702)
  42. 对于已排序的数组，每个数字读出现两次除了其中一个数字只出现了一次，可以使用二分搜索，根据配对数字的下标关系(i为奇数时应为i和i+1配对)，来锁定二分查找的方向(LC 540)
  43. 反向思考，可以修改最多k个数字，就是维护窗口中不合法数字最多为k个(LC 1004)
  44. 通过bit manipulation来存储相关信息，例如字母总共有26个，那么给你一个字符串，你可以用二进制数来记录这个字符串中字符的存在情况，第i位二进制数代表从a开始算第i个字母是否存在(LC 318)
  45. 双向BFS，起点和终点都进行BFS，看有没交点，证明能否可达
  46. 树的结构也可以通过字符串(按先序中序或后序遍历的方式)来记录存储(LC 652)
  47. 稍复杂的DP都需要从片段长度为1开始累积求解，如LC video stitching和LC 813
  48. 批量比较判断subsequence的方法，将下一个要匹配的字符都存入一个list中，并不断更新每个字符串(LC 792)
  49. Djikstra's 迪杰斯特拉算法(LC 743)
  50. 有的时候math或者比较tricky的题目，需要考虑索引的奇偶性
  51. 我们可以用二进制移位操作的掩码来记录搜索过程中已visited的状态
  52. 要学会用TreeMap的API(LC 715)
  53. 在sorted list的基础上进行问题解答，如果一般的方法是O(n)时间复杂度，那么optimized的方法可能是O(logn)用二分搜索。
  54. Trie可以用来高效率的进行单词匹配及正则表达式pattern匹配，可以将目标words全部加入到Trie中从而简化后面的运算逻辑。