刷题记录贴 督促自己

这学期课不多 发帖记录刷leetcode的心得 顺便记录一下必要的模块和框架 求督促
尽量日行一帖～

补充内容 (2018-5-26 09:44):
有没有今年毕业的，找美东刷题找工作的伙伴啊。。。一个人努力真的很累

5.17 system design 101 - tinyurl，之前用mongodb+node.js做了tinyurl，现总结记录一下 535/encode - decode的算法
几种方法会想去避免出现如下几种问题
1. 能够记录多少条数据而不会出现数据的collision现象？（same dataset key, yet different data），如果我们使用Integer, 那么将受32bit max value所约束，约2亿
2. 记录在数据库里的shortUrl的长度，因为我们的目的是为了缩短网址的长度，方便记录
3. 短网址长度与原网址长度有什么关系？
1. 最简单的counter法, data structure: hashmap
        缺点: 1. 2. 因为使用integer, 所以当数据量到达max，将会collide，并且网址长度会越来越长
2. 在counter的基础上，把counter的二进制转换成62进制，
        缺点: 1. 那么短网址的长度是可变的（虽然仍然在递增，但是以62进制的级数递增），但是仍然受int range的约束， 以及数据量max仍然会出现重复数据。
3. 利用hash code： s[0] ∗ 31^​(n−1) + s[1] ∗ 31 ^ (n−2) +...+ s[n−1]
        缺点: 1. 2. hash code 仍然使用integer value来计算，所以受max value约束，且长度受
4. 使用随机数，那么问题基本和使用counter相同，
5. 使用随机X位字符串, 这里用62进制的字符组成字符串，那么就有62^6，约56亿数据，远大于前几种方法，缩小collision的概率，并且短网址长度永远是6.

5.16
昨天学了一下full stack的东西 今天back on track！
1. 发现有很多题的解法十分ad hoc， 有时候顺着逻辑做的recursion可能会达到worst case O(n), 但是运用巧妙的方法 work around可能optimize到linear
例1: LinkedList, ArrayList, Tree里的 "PathSum"类题， 会涉及到prefix sum的解法, prefix sum: 从路径起点到当前位置的路径和。在路径中想要寻找到在当前位置是否存在一条路径，是其通过它的某一条路径和为target value，等同于寻找在当前位置之前的prefix sum有没有出现过currentSum - target.
   即 1, 2, -1, -1, 2, target = 2， 有两种方法遍历，第一，以每个节点为头节点， 检查它往后延续的路径和是否为target， 第二， 沿用prefix sum的思想，例如(1, 2, -1, -1, 2, prefix sum = 3) - (1, prefix sum = 1) = 2, which is target.
但是不要忘记prefix sum永远有一个初始值0！还要记得先检查是否存在满足条件的值，再把当前值放入hashmap, 然后从每一级返回时，restore hash map

2. 需要output counter的值的时候，无论是递归还是迭代，除了设置一个global var（或者放在wrapper class）里， 还可以直接储存在return值里。

补充内容 (2018-5-17 11:00):
3. ad hoc solution two pointer 双指针法，可以是uni-directional，分为fast pointer 与 slow pointer， 一般用来找 arraylist, linkedlist中点， 也可以是bi-directional

5.18
先总结一下一些只知道是这样却不知道为什么的点：
1. java recursion takes O(n) space, because recursively invoking method will push the method on to calling stack, which takes up to O(depth of recursion) space.
2. java is using call-by-value model, which means although java manipulate object by reference, when a reference is passed into a function, it passed the reference by value. java creates a method reference other than the original reference to this object, so if you swap or manipulate the pointing direction to this reference, it will not work.
今天从tree里休息一下...开始刷数组，数组的方法不多，慢慢记录，今天遇到的方法有
1. 双指针，two pointer 也可以说是sliding window，动态窗口。 这个方法做很多array题都很实用，基本是一个指针固定遍历所有值，另一个可调指针自选位置， 或者两个自选指针动态调整位置。
注意点：
1.  基本上记录连续值个数的时候，用双指针法，但是要注意记录的位置。
2.  想清楚计数的初始值。。。。

4月15日第一帖～ 111
1. 刷到一道brain teaser的进制转换题  「 result = result + base * digit 的写法，记录一下
2. 一道很难读懂的count and say...38题 不推荐花时间
3. 不方便写return的地方可以用 「 throw new IllegalArgumentException("xxx"); 替代，记录一下
4. 二叉树的做法 简单遍历： 一般recursion或者堆栈法，recursion又分前中后三种，BFS/DFS: BFS一般用queue， DFS一般用递归或者stack

4.17 119 昨天生病了
1. dfs一般借用helper function和global var来写clean code
2. Str.indexOf() 框架

4.19 120 今天集中做一下TREE的题目
1. 刷了几道easy的dfs题，可以在利用arg来记录traverse过程中path的temporary value
注意点:
1. 在处理树转list题时，注意list可以add null value

4.23 127   接下来需要7天复习最后一门考试 但是每天零散刷一些题
1. 刷到了bloomberg学校crc面试里遇到的513， 这次轻松解决了，树的题目要每到都想清楚BFS/dfs(recursion)的写法。
2. 可以用inner class封装global var

5.7 132 学期结束了..暑假冲刺刷题！
今天刷medium tree
1. 刷了一道用parent和child list来表示tree的题，可以用hash map或者construct tree node来construct
2. 一题比较难的3 digit list运用level, position, val构建树的题

5.9 放假有点松懈！134
medium tree
1. 一直想不明白debug错在哪的时候，记得检查helper function arguments
2. in-order/pre/post traversal iterative方法，注意while loop的multiple conditions， 因为用stack并不会先push root.
3*. constant space iteratively doing inorder traversal: morris inorder traversal ***：link the predecessor to current node so that dont have to go back when traversing(按照中序遍历的顺序将tree 首尾相连)

5.10 放假第二天！ 135
medium tree
1. bitwise operation has lower precedence than add/subtract
2. 整理了pre/in/post-order traversal迭代法

5.11 141
1. tree from right hand view, clear solution with BFS level order traversal, need level info when using DFS

佩服lz的勇气，我就做不了