6/3/2020

[BFS] 127. Word Ladder

  • (Breadth First Search) 广度优先搜索 queue实现

6/19/2020

[Queue] 295. Find Median

  • multiset 已经排过 TC:O(nlogn)
  • priority_queue
  • lower_bound / upper_bound

[Database] 175. Combine Two Table

  • left join

6/20/2020

[Hash Table] 299. Bulls and Cows

  • i++ & ++i
  • if (i++ < 0) 先判断后加
  • if (i++ && j++) 左判错右不运行

6/22/2020

[Merge Sort] 315. Count of Smaller Numbers After Self

6/24/2020

[DP] 375. Guess Number Higher or Lower II

6/25/2020

[stack] 394. Decode String

  • 利用stack储存分类信息；分层对齐，在stack中的位置对应括号层级

6/26/2020

[DFS] 399. Evaluate Division

  • (Depth First Search) 深度优先搜索 每个分支走到底，visited set 记录已访问分支

6/27/2020

[DP] 552. Student Attendance Record II

6/28/2020

[prefix sum] 560. Subarray Sum Equals K

  • 一开始会以为简单地用sliding window, 但是不对，integer可以小于0，sum不是单增的，以下为错解：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
      public:
        int subarraySum(vector<int>& nums, int k) {
          int l = 0;
          int intSum = 0;
          int cnt = 0;
          
          for (int r = 0; r < nums.size(); r++) {
            intSum += nums[r];
            while (l <= r && intSum >= k) {
              if (intSum == k) {
                cnt++;
              }
              intSum -= nums[l++];
            }
          }
          return cnt;
        }
    };
  • 正解prefix sum（前缀和）：核心思想是如果0~i的和与0~j的和相等（i < j）,那么[i,j]内的链表值和为零。
  • map, unordered_map的key不存在时查询到的值为0。为啥？

[DP] 562. Longest Line of Consecutive One in Matrix

  • DP的思维（2D或者3D），但注意到四个方向其实并没有什么联系，就没必要用DP，直接分开计算。
  • 看到一个小trick，map的时候通过(0,.1,.2,.3)来区分(horizontal, vertical, diagonal or anti-diagonal)，避免int对key的重复命名。以及先++再乘0或1避免写if的繁琐。
    1
    2
    3
    4
    for (int i = 0; i < M.size(); i++)
        for (int j = 0; j < M[i].size(); j++)
            for (float key: {(float)i, j+(float).1, i-j+(float).2, i+j+(float).3}) {
                    maxlen = max(maxlen, ++len[key] *= M[i][j]);
    直接用float[]转化会有double转float的问题，目前只知道这么解决。

7/2/2020

[DP] 264. Ugly Number II

  • 观察最后乘以2，3，5的三列，每列都是与当前列的pointer指向的ugly number相乘，取三列当前最小。
  • 用minheap会用到priority_queue, 自带对数排序时间。

[DFS]107. Binary Tree Level Order Traversal II

  • reverse(ans.begin(), ans.end()); 对vector
  • 标记层数traverse the tree
  • vector转tree直接用2n，2n+1查询

[DP]957. Prison Cells After N Days

  • 唯一很坑的是这是一个循环，需要找出循环避免重复运算，想不到的话就很超时。而且循环无始末，只需要长度，所以其实只用记录第一天的来看后面会不会有重复。

7/3/2020

[] 461. Hamming Distance

  • bit operator: XOR(同位异或)operator “^”; AND “&”
  • bits shift operator “<<” “>>”
  • Brian Kernighan’s Algorithm 通过”x&(x-1)”消除最右边的1，最终消除为0完成计数。

[] 66. Plus One

  • Why no push/pop in front of vector? Answer: push_front has no way to run quickly, because, in addition to a possible reallocation, all items need to be copied by one position. This gives you an amortized performance of O(n2) for n objects, which is not something that library designers wanted to encourage.

7/8/2020

[] 15. 3Sum

  • 先sort,TC只用O(logn),再用两个pointer，外层O(n)内层其实是小于O(n)的。所以总的为O(n^2)。

7/9/2020

[BFS] 662. Maximum Width of Binary Tree

  • 用queue记录每层node，记得记录每层个数。
  • 为避免overflow，可将root设置为最靠近root且没有同level节点的节点。

7/10/2020

[Data Structure] 430. Flatten a Multilevel Doubly Linked List

  • 不用考虑函数嵌套，子类的子类依然会在第一层循环中遇见。
    1
    2
    3
    for (Node* h = head; h; h = h->next) {
      ...
    }
  • 注意末端没有next。

7/11/2020

[] 78. Subsets

  • 最直接的方法是Iterative,依次加入每个数。
  • Bit Manipulation注意移位（1 << n）2的n次方，（& 1）找出奇数的好方法。
  • Recursive (Backtracking)的方法。

7/12/2020

[DP] 53. Maximum Subarray

  • Kadane’s Algorithm: 其实也是greedy的思想，因为是同时加一个数，每次只用比较i-1最大和新增的0的大小关系来判断当前最大。

7/15/2020

[] 151. Reverse Words in a String

  • reverse(s.begin(), s.end())

[recursive] 50. Pow(x, n)

  • 如果思路是从末端开始的就用recursive
  • 也可直接循环

7/22/2020

[Graph] 210. Course Schedule II

  • topological sort for directed graph
  • Kahn’s algorithm, indegree为0的一定是优先排序。这也是BFS的思想。
  • DFS

Single-Number-I-II-III

7/27/2020

[Data Structure Binary Tree] 106. Construct Binary Tree from Inorder and Postorder Traversal

  • Master Theorem
  • (a) Inorder (Left, Root, Right)
    (b) Preorder (Root, Left, Right)
    (c) Postorder (Left, Right, Root)

7/29/2020

[DP] 309. Best Time to Buy and Sell Stock with Cooldown

7/31/2020

[]70. Climbing Stairs

  • Fibonacci Number

8/9/2020

[Data Structure] 211. Add and Search Word - Data structure design

  • Trie 字典查询树

[Bits] 231. Power of Two

  • Power of two has just one 1-bit
  • x & (x - 1) sets this 1-bit to zero, and hence one has to verify if the result is zero x & (x - 1) == 0
    [Bits] 231. Power of Four
  • It is power of two first
  • then (num & 0xaaaaaaaa) == 0, 0xaaaaaaaa (8 bits) is 1010…10 (32 bits)

8/10/2020