Nan-Zhang

通过对该题的递归解法(yelp_package)，我们可以发现递归层数从浅到深，单个解(i到j)的范围，在逐渐减少。

我们可以发现递归时，很多(i到j)的解被重复生成，而且大解(i到j范围大)在浅层，调用深层的小解(i到j范围小)。

我们可以直接转换这个递归的结构到动态规划。即先构造小解，再构造大解。

伪代码：
第一层循环: sizeof(i到j),从1 到 sizeof(input)
第二层循环:  i动
第三层循环:  j动

Nan-Zhang

The algorithm about the conversion
----------------------------------------------
We use a stack
• When an operand is read, output it.
• When an operator is read.
– Pop until the top of the stack has an element of lower precedence.
– Then push it.
• When ) is found, pop until we find the matching (.
• ( has the lowest precedence when in the stack but has the highest precedence when in the input.
• When we reach the end of input, pop until the stack is empty.

Nan-Zhang

1. This is a repository action, so you can see the keyboard shortcut from the "Repository" menu "Commit All..." which is shift, cmd, and 'C'.
2. Shortcut to click the commit button in the commit dialog --> CMD + Return

Nan-Zhang

Say we want to generate a set of s elements and that we have already seen n>s elements.

Let's assume that our current s elements have already each been chosen with probability s/n.

By the definition of the algorithm, we choose element n+1 with probability s/(n+1).

Each element already part of our result set has a probability 1/s of being replaced.

The probability that an element from the n-seen result set is replaced in the n+1-seen result set is therefore (1/s)*s/(n+1)=1/(n+1). Conversely, the probability that an element is not replaced is 1-1/(n+1)=n/(n+1).

Nan-Zhang

We'll divide the file into chunks which are x megabytes each, where x is the amount of memory we have available. Each chunk is sorted separately and then saved back to the file system.

Once all the chunks are sorted, we then merge the chunks, one by one. At the end, we have a fully sorted file.

Nan-Zhang

Assume target string: S0S1......Sn-1; pattern string: P0P1......Pm-1
So we have: StSt+1......St+j = P0P1......Pj, and St+j+1 != Pj+1

We should then compare St+1St+2......=P0P1......, However, if P0P1......Pj-1 != P1P2......Pj, then it must be failed!
We should then compare St+2St+3......=P0P1......, However, if P0P1......Pj-2 != P2P3......Pj, then it must be failed!

We only need find a k: P0P1......Pk=Pj-kPj-k+1......Pj AND P0P1......Pk+1 != Pj-k-1Pj-k......Pj

Because St+j-kSt+j-k+1......St+j=Pj-kPj-k+1......Pj=P0P1......Pk, So next time we only need to consider St+j+1 == Pk+1 ?

Nan-Zhang

1. The upper bound of time complexity of getting Fibonacci Number in recursive way is 2 ^ n, but this is super upper bound
   assume the time complexity is 2 ^(k*n), how to derive it?
   f(n) = f(n - 1) + f(n - 2)
   2 ^(k*n) = 2 ^(k*(n-1)) + 2 ^(k*(n-2))
   2 ^(2*k) = 1 + 2^k
   assume 2^k = x
   x^2 - x - 1 = 0 (x = (-b +- sqrt(b^2 - 4ac))/(2a))
   k = log(1.6)
2. how to calculate Fibonacci Number in a way faster than O(n)
   f(n)   =     1 1  * f(n-1) = 1 1 ^ (n-1) * f(1)

Nan-Zhang

Complex Number: a + b*i (a, b are real number), i^2 = -1.
So any position in Cartesian Coordinates will represent a Complex Number: x + y*i
How to convert from Complex Number(position in Cartesian Coordinates) to Polar Coordinate:
x + yi = r * (cos(d) + sin(d) * i) = r * e ^ (i * d) (see Euler formula, and d is angular)
So, we can use Polar Coordinates to derive points rotation in Cartesian Coordinates:

1. rotate pi/2 in  anticlockwise direction
  (x, y) = x + y*i = r * e ^ (i * d + pi/2) = r * ((e ^ (i * d)) * (e ^ (pi/2))) = (x + y*i) * i = -y + x*i = (-y, x)
2. rotate pi in anticlockwise direction
  (x, y) = x + y*i = r * e ^ (i * d + pi) = (x + y*i) * -1 = -x -y*i = (-x, -y)

Nan-Zhang

TreeNode prev = null;
    public void inorder(TreeNode root, ArrayList<TreeNode> t, TreeNode prev) {
        //do sth with prev (Note: this prev is the local variable, and has nothing to do with the static prev)
    }

Nan-Zhang

^ key: Control key. This acts like a normal control key