刷题记录贴 督促自己

vinsonhihi 发表于 2018-5-12 18:52
佩服lz的勇气，我就做不了

发帖为了直面自己的懒惰

5.13
medium tree
1. 记录一道递归和迭代都没写好的题 236
2. 二分法可以巧妙地用在二叉搜索树的题上，因为左右两边的value range被root分隔开，可以应用于例如kth smallest value上
3.两道比较像的树题 105/106 因为最近array + tree的题比较热，记录一下， 注意的是subarray的index要看仔细再写。

补充内容 (2018-5-14 11:39):
145

补充内容 (2018-5-14 12:12):
刷树的题的时候，经常遇到将dp思想融合进去的题，这时候如果用分情况讨论的套路去用dfs，会导致大量repeated case， 这时候比较典型用法是用array来memoization

5.14
medium tree
刷了一天westworld没怎么刷题...
把path sum的五道题刷了一下

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.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.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.  想清楚计数的初始值。。。。

5.19
继续 array

5.20 arr
数组方法2
2. prefix sum, 基本用于求和，求平均类问题， 方法变形有sum array / hash table 储存 prefix sum
3. 比较难以想到的办法是linear search然后中途记录中间值
4. 不要死死扣着顺序遍历在想，有时候用倒序处理会很简单！
5. 记得写前先注意一下长度为0， 1， 2这种特殊长度， 以及数组头，数组尾这种特殊位置。

5.23 array
1. 学到一个很牛b的求range sum方法，简答说就是在数组里，想要让一段subarray的值加上一个val， 第一种方法是遍历这个数组段的position，直接加，这里介绍的这种方法是，现在startindex加上val， 再在endindex + 1的位置减去val，最后求一遍prefix sum. 举个栗子：  [0,0,0,0,0]  我们先要在【1～3】的位置加上2，即所得为[0,2,2,2,0,0] 那么我们第一步后我们得到 [0,2,0,0,-2] 第二步求prefix sum得[0,2,2,2,0]

有没有今年毕业的，找美东刷题找工作的伙伴啊。。。一个人努力真的很累