7月缺米的来刷题/Mock interview活动

valid number：先去掉首位空格
1. 有限状态自动机，规定状态转移表和终态
2. 匹配符号->匹配整数部分（int）->'.'->匹配小数部分（unsigned int）-> 'e/E'-> 匹配指数（int）
（记得给自己前面的三个人加米啊！）

wdk2000 发表于 2020-7-4 23:36
day4 sql 3题
同时取最大/小值--rank () over (../desc)

记得给自己前面的三个人加米啊！

慕容清 发表于 2020-7-4 22:11
打卡第三天

记得给自己前面的三个人加米啊！

Day 2 打卡 LC 8题

July day2
6 problems

Day 12, solved 6 problems.

Tips:

1. For LC 1008, use a global variable to store current index, which every recursive calls can modify, and a upper bound to mark the boundary for each subtree;
2. LC 264, assign each factor an index to mark the position of the most recent ugly number that used this factor;
3. LC 1035, uncrossed lines imply a sequence problem, which turns out to be a typical LCS.

Day 4, 0704,  三道题

117 Populating next right pointer II
用bfs queue写很容易。这里用recursion的O1 space写了一下。用一个recursion function， 每次传进来parent + 要么左右两个孩子， 能连就连一下完事pass下去， 要么是右孩子和null，通过parent去找下一个能连上的。挺难想，看着例子都有点搞不明白。。。

489 Robot Room Cleaner
这个backtracking没办法给坐标直接跳过去，所以要用robot转圈来实现。每次要传一个direction进去，然后顺时间查，完事之后要转180度回头一步，然后再180度归方向。

736 这个终于写出来了。。。
这个题逻辑很迷。。。add和mult都不用while，就是单纯实现前两个计算就完事。但是let是while循环，每遇见两个都要赋值，最后return最后一个的值。。。这个点读了很久才懂。写起来decouple做的好的话，还挺清楚的。。。用recursion把括号传下去就行。

打卡第二天~
LC403: https://leetcode.com/problems/frog-jump/
dfs + memo 实现的DP类型题，N^2的 DP解没有写出来，一开始顺着背包问题的思路去想，但是发现做不出来。

LC171:  Excel Sheet Column Number       
math 类型的题，用来练习下

LC264: Ugly Number II
一开始用的 Heap，虽然能AC,但是效率不是很高。DP解更好一些，其实也有点像 Three pointers

记得给自己前面的三个人加米啊！

刷题打卡第二天

• Game of Life 用2位bit表示当前和下次的状态，这样数字0～3可以表示transition，剩下的按规则simulation就可以了
• Ugly Number II 用一个list 记录所有的ugly number，并且维护3个指针i,j,k 分别记录2，3，5的next multiplier在list中的位置。第Kth number 一定是 Min(L1 * 2, L2 * 3, L3 * 5)
• The kth Factor of n 用一个list 记录所有的factor在范围[1, sqrt(n)], 然后iterate去找第K个。如果超出范围，因为对称的关系，最后的结果是 n / ls.get(len - k)
  

7.4 打卡第四天

1. Binary Search。求某个数阶乘的tailing zeros的个数转化成求这个数含有的5的因子的数量。
2. Binary Search。好题，求最大的average不好求，但是对于一个特定的average看满不满足容易知道。
3. DP + Greedy。这个系列的3个题建议做一做。