Math

理论

应用：

1. 随机数

   • 水塘抽样 每次新元素（下标i),随机与已知元素中任意一个互换，那么任意元素被选中的概率为1/i,则元素i进入水塘k的概率为 $\frac{k}{i}$, 前k个元素被认为进入了水塘，对于已经在水塘中的元素，遇到i个元素时人留在水塘中的概率为 $\frac{k}{i} \cdot \frac{i}{i+1}(第i+1步被抽中)\cdot \frac{i+1}{i+2}\cdot...\frac{j-1}{j}\cdot=\frac{k}{j}$

   • Knuth Shuffle 同理，产生randomized shuffle，for i in range(len(arr),-1,-1){rnd=randint(0, i),arr[rnd]<->arr[i]}

2. 数论

3. BrainTeaser/其它

Problems

1. 随机数

528. Random Pick with Weight记录cdf数组,用bisect_left查找随机数在（0，1）在cdf数组中的位置
398. Random Pick Indexcache[num]=[index list], return random.choice(cache[target])\

2. 数论

9. Palindrome Number将数字后半段组成新数字b， 直至a<=b， 判断a==b|a==b/10
29. Divide Two Integersdividend每次减去3 << x,可以满足dividend > (3 << x)的最大x
66. Plus One从最后开始找到第一个不为9的数字(同时将9设为0），若i>=0,arr[i]+=1，否则，arr=[1]+arr
69. Sqrt(x)newton method, O(lgn)，设a=x//2, a = a/2 + (x / (2 * a)),直至a的变化<10-4,返回floor(a)
50. Pow(x, n)当n>0, res *= x, if n % 2== 1; else x**=2, n // 2
326. Power of Three(lg(n)/lg(3)+eps)%1<= 2*eps
342. Power of Fourn&(n-1)==0 and n%3==1
367. Valid Perfect Square同50, Newton法，O(lgn)
172. Factorial Trailing Zeroesres += n // 5，n //= 5, 直至n == 0
1012. Numbers With Repeated Digitsfrom math import perm; 答案= n+1-无重复数字的数字个数，如87669->xxxx,xxx,xx,x, 以及1xxxx->7xxxx,80xxx->86xxx,870xx->875xx,8760x->8765x, 87660->87669；当第一个数字为0时要特殊处理
【不懂】780. Reaching Points总是令ty>tx,当tx=sx时，判断（ty-sy)%sx==0;当tx>sx时，因为ty>tx，ty%=tx,返回while loop
202. Happy Number设置seen set, 如果新数字已经在seen， 则有cycle\

3. BrainTeaser/其它

【妙】390. Elimination Game记录cnt, 方向，step, head，仅当（1）方向向右（2）方向向左且cnt为奇数时，更新head
2849. Determine if a Cell Is Reachable at a Given Time能否到达取决于x,y到目的地x方向和y方向的最大距离，max(xdist, ydist) <= t
453. Minimum Moves to Equal Array Elements给n-1个数+1等价于给剩余那个数-1， 故将每个数-最小值相加即为答案\

Count Primes Mark out multipliers from the bottom up.

Fraction to Recurring Decimal This is an unpleasant experience.

Evaluate Reverse Polish Notation Use a stack to do the work.

Largest Number Intuitively, sort the element from big to small. But 9 will still be smaller than 12. A smart comparison function is compare s1 + s2 vs s2 + s1. Finally, handle the trailing zeros.

Max Points On a Line This is sort of brute force. compute the slopes of all pair from i = 1... N, j = i + 1, ...N. and store the slope : count in a hash map. In addition, needs to add the duplicate count in the cnt.

Sparse Matrix Multiplication This is surprisingly easier than my approach. No need to compress the matrix first, since we only care about speed here, not memory usage. So simply, we just notice that if A[i][j] != 0, it must contribute to the calculation of res[i][k] (k = 0, ..., col).

valid-square

check if four sides equal and two diagonals equal.

minimum-area-rectangle-ii

每两个点的连线可以有一个中心和半径，将点的配对以此分类。每个类别之内的两个对子，一定能成矩形，找出最小矩形。

Other Others

Majority Elements This equals to draw line x-y panel, if same as current majority cnt++, else cnt--; when cnt < 0, reset majority.

Task Scheduler This is also majority count problem. The least steps is mostly decided by the count of the element appears most, lower bounded by the number of tasks(this happens when if count other than majority dominate cooldown). Also, when there is tie of majority element, the last line of task needs to handle it specifically.

Finding Celebrity The key point is to realize that there can be at most one celebrity. Acknowledging this, find the potential celebrity candidate, and verify whether it is a real celebrity. To find the potential celeb, no need to create the bool array, only maintain one celb candidate is enough, iterate i = 1...n, when find knows(celb, i), replace celb with i, continue the i ieration without reset i.

The power of Mod

mod can be applied any time before or after +/-/*/pow//(to be confirmed)

Super Pow

Combinatorial

3sum-with-multiplicity

gcd

water-and-jug-problem

The problem can be solved using following theorem.

• We can always find a and b to satisfy ax + bx = d where d = gcd(x, y)

BrainTeaser

swap-adjacent-in-lr-string

Can thing of L as people moving left, R as people moving right, they cannot cross each other. Use two pointers to compare element from left to right, skip x.

Random Number Generator

382. Linked List Random Node水塘抽样，每次以1/i的概率替换O(i)，遍历,i为当前长度\