打卡做题+项目

最近主要在复习之前做过的题。。可能很多题已经做过两三遍了，但发现自己之前更多的只是追求accept而不是去思考总结。
所以现在如果做的是以前做过的题，希望自己尽量多想一想


今天做了6道String相关的题
Reorder Array
Compress String II
Decompress String II
Longest Substring Without Repeating Characters
All Anagrams
Longest Subarray Contains Only 1s

在这6道题里，我觉得Reorder Array可能算是单独一类，因为用到的方法在String相关题里比较少。用的是merge sort的逆向思考，有点tricky容易写错的地方是中间两个chunks对调位置时候，index需要多加小心。

Compress String, Decompress String可以算一类，都是要对原有的string进行改写（最好是in place），经常需要用到slow and fast pointer，而且是同向而行。fast pointer的目的是为了iterate string，而slow pointer是为了记录当前改写后的部分的最末端。对于这类问题，有个麻烦的地方是需要考虑改写string后，string会变长还是变短。如果是变短，那么直接在原有的string/array上进行改写就好了。但如果变长，在java里因为string是immutable，所以一般需要重新new一个char array来写，而且为了避免覆盖到还没有cover的部分，可以从array的最后面往前来填，避免覆盖的问题。

最后三道题应该算一类，解题方法都是用sliding window。这类题，可以算作查找、比对。每个循环都需要更新sliding window的范围，并且需要检查sliding window里的内容。sliding window也可以分成是固定长度和不固定长度的。对于固定长度，更新的时候就是一进一出。对于不固定长度，需要先移动一个pointer，再移动另外一个。


还做了Majority Element，这道题感觉有点无聊，就不说了。。

Two Sum in BST，惊讶LeetCode里竟然没有最优解。。当然我也只写了用两个stack来作为BST iterator来做。Morris Traversal还没看懂。。

Flutter tutorial跟了40min的video，自己做了3个小时

今天做的题比较少，复习了5道关于bit operation的题
Power of Two
Number of Different Bits
All Unique Characters
Reverse Bits of 32-bit Integer
Hexadecimal Representation

反思一下，bit operation最最基本的操作就是& | ^ >> << >>>，也就是bit and, bit or, xor, signed right shift, left shift, unsigned left shift，通过这5个最最基本的运算，可以创造出一些所谓的building block，比如把某一位设置成0或1（setter）或取反，或者读取某一位是0或1（getter）。通过这几个building blocks，可以实现一些目的，比如压缩信息。把一个int当成从32-bit的角度来看，其实就是一个长度为32的array，只是这个array每个position的取值只能是0或1。

在上面五道题里，power of two, number of different bits, reverse bits of 32-bit integer这三道题其实都是考查最基本的bit操作
all unique character就是把integer当成array来用
hexadecimal representation则是利用了二进制的4位对应了十六进制的1位这个性质

Flutter tutorial跟了20分钟，感觉越来越熟悉，但是缺乏很多基础知识

昨天被一些杂事干扰了。。不过晚上做了40分钟左右的flutter tutorial，做好了一个简单版的Instagram，还挺有成就感的，虽然就是照着视频抄代码。。

今天还是做了一些事情的。复习了培训班上Recursion的一些题。不过虽然是recursion，但是有些题强行用tail recursion反而增加了空间复杂度，还不如iterative直接写。
Spiral order traverse
N queens
Reverse linked list in pairs
String abbreviation matching
Store number of nodes in left subtree
LCA
Reverse binary tree upside down

spiral order traverse, reverse linked list in pairs, reverse binary tree upside down这三道题应该算是一类，都是按照三部曲base case, subproblem, recursive rule的方式来思考就好。好巧不巧，如果用recursion还都是tail recursion，用iterative写从逻辑上看会复杂一点，但是省空间复杂度

n queens应该是一类题的代表了，或许可以归纳成，在上一个node里做的事情，会对下一个node里能做什么事情产生一些限制。而这些限制如果记录下来，可以用来剪枝，而不是每一次根据规则去比对（这样会很慢），或者产生一堆没用的答案到最后再去过滤（这样也很慢）。但是就需要用一些数据结构来记录之前的node产生的限制是什么。可以看成是一个时间和空间复杂度之间的tradeoff。

String abbreviation matching感觉放在String的题里更合适，用two pointers分别代表两个String里待处理部分的开头，撸一遍，就行了

store number of nodes in left subtree和LCA是一类题。我觉得如果是对binary tree做操作，入手点可以是看感兴趣的是什么性质，然后可以看这些性质是和depth还是height相关。如果是depth，那可能会需要从上往下传递变量，也就是把变量放进method signature里。如果和height有关，或者需要从subtree来获得信息，那么需要把变量放在return type里，然后做一些操作，这种应该一般都是post-order traversal了。
另外我觉得LCA精简的解法不是很好讲清楚。。因为return type的含义比较复杂，是把不同的case重新组合之后再用不同的条件来表达的。

周日没怎么学习。。一直在打听学校的事。另外可以做一些production-level的project了，还是很开心的
今天复习了一些DP的题

Fibonacci number
Longest ascending subarray
Max product of cutting rope
Array hopper I & II
Largest subarray sum
Dictionary word I
Edit distance
Largest square of 1s

其实都不难，但是以前做的时候没有要求自己优化空间复杂度。今天做的时候都是直接写优化后的解法，就有些不习惯，所以写出了很多bug。

fibonacci number, longest ascending subarray, largest subarray sum是一类题，解法都是linear scan回头看一个或两个元素。所以时间复杂度是O(n)，空间复杂度可以从O(n)优化到O(1)，因为再往前记录下的元素是用不到的

max product of cutting rope, array hopper, dictionary word是一类。解法同样是linear scan，但是需要回头看所有的元素（array hopper可能是介于上一种和这一种之间吧）。这样时间复杂度就是O(n^2)，而空间复杂度是O(n)，不能优化，因为所有元素都要看

edit distance, largest square of 1s是一类题，因为都是二维DP。我还不能归纳出什么样的题是二维，什么样的题是一维。。这种题得考虑好填表的顺序。根据填表的顺序以及induction rule，可以推断是不是可以优化空间复杂度。这两道题应该都是只需要看当前这一行和上面一行的结果，所以空间可以从O(n^2)优化到O(n)。我就是这个地方很容易写错，有的时候以为只用一行就行，但是填表有可能会把需要的信息给overwrite。另外是1或者是0的情况，我都没有考虑细致，结果错了好几次。。

昨天忘记update了，复习了DP的6道题
Longest consecutive 1s
Longset cross of 1s
Largest square surrounded by one
Largest X of 1s
Largest square of matches
Largest submatrix sum

Longest consecutive 1s应该是building block的题了，和largest subarray sum的思路一模一样。
largest cross of 1s, largest square surrounded by one, largest X of 1s, largest square of matches都是建立在longest consecutive 1s的基础上的，只不过需要对每一行每一列都做同样的操作。然后可能方向会有所区别。cross或者是X都是需要4个方向。如果只是要找largest square，两个方向就够了。我觉得这类题有时候即使用DP写出来了，要写出最优的解法，还需要思考一下空间复杂度是不是可以优化，还有就是时间上，很多时候是可以做到one-pass的，这样会省一点时间。

largest submatrix sum是里面最难的一道题了。时间复杂度优化到O(n^4)不难，但是如果要O(n^3)就需要把几行或者几列给压扁成一行或者一列。另外，我即使写完了，写对了，最后发现其实是可以one-pass的，所以还是要想一想怎样可以进一步优化

今天做了几道和probability, sampling, randomization的题
Perfect shuffle
Reservoir sampling
Random 7 using random 5
Median tracker
95 percentile
Generalized reservior sampling
Random 1000 using random 5

太困了。。简单说一下，reservoir sampling我没有掌握好。最羞耻的是，自己算概率算了半天。。真的是太久没接触，自己已经晕了。。