开贴自我监督：19fall小孩每天学一点

开贴自我监督：19fall小孩每天学一点
本贴2018 .11 .14开贴，希望自己能坚持下去，直到赴美读研开始准备秋招 找实习未截至吧
每天学一点，做一点，算法，framwork，项目——全记录

寒冬已至，吾辈何以为战。

补充内容 (2018-11-17 16:03):
悟： 刷这道题不是因为“刷了它，就少一道题”  而是因为  “刷了它，我就会下一道题”

leetcode 72. Edit Distance:

这真是一道非常非常非常 棒的题， DP初学者进阶好题，代码很简单，但是就看如何理解 对三种子情况的理解了。

本题最难的一点就是理清楚 current state 的三种 sub problem （正如很多DP问题一样，最难的其实就是找清sub们）：
1.insert 其实就是抵消目标串 进而  j-1
2.delete其实就是抵消己串 进而 i-1
3.replace 其实就是二者相抵消  进而 i-1 j-1
这就是三个子问题，依赖方向搞明白，那么问题就好解了。

然后最初解体还有一个核心疑问就是，dp图从（m，n）坐标开始往（0，0）依赖，那岂不是就是说只能串与串从后往前相匹配？
其实虽然匹配的顺序是从后往前，但是其实在这个过程中，有三个sub 取min ，其实每一位 的三个情况，都是考虑进去了的

最后引一段 地里大神的话：
1. definition: dp 或者 dp[j] 表示什么含义，比如largest subarray sum ending at arr, and must include arr. 注意语言描述, 包括还是不包括arr/matrix[j]
2. induction rule: dp 的 dependency 是怎么样的，依赖于dp[i-1] 还是 dp[i+1] 还是 dp[k] for all k < i or all k > i 等等，试着过几个小例子推导一下
3. base case:  往往是dp[0]，二维往往是第一行， 第一列，也就是dp[0], dp[0][j]
4. result: 往往的dp[n], max(dp) 等等, 从definition 出发
5. filling order: 也就是你填dp表格的顺序，从induction rule 的 dependency出发 判断的从左到右 还是 从左上到右下
6. optimized: 分为时间和空间两方面。时间的比较难，因为往往需要你重新define dp state 和 induction rule。空间比较简单，可以根据induction rule看出来，比如斐波那契数列: dp = dp[i - 1] + dp[i - 2], 那么dp 只依赖于前两个元素，就不需要create 整个 dp array，两个variable即可，空间可以从O(n)优化到O(1)。

补充内容 (2018-11-15 21:02):
有一个发现不知道正不正确，用递归DP  总时间竟然不亚于  线性2重for循环DP，个人大爱递归，看得清晰点

AVL Tree：

这里想先说一下红黑树，其实我觉得红黑树的  核心数学原理和  AVL tree 是一样的，只不过  红黑树采用了一种可爱 且  事实上非常不逻辑直观的  颜色相关rule 来定性 tree invariant， 在同样的实际中，个人还是偏向AVL

AVL，红黑，都是BST 的子集， 都是优化查找  增删  数据的一种高效数据结构。   最基础的BST 的 三项  时间复杂度都是  O（n）——O（lgn），为了避免大量constant 情况出现，进而才发明了只会 O（lgn）的AVL 红黑

AVL在BST的基础上增了一个强大的功能：  旋转以 重定root ，比如左树太大 太长，那么root就左旋转，使得左树的node 来承担root 的职位，这样左右树又会平衡一些（balance factor），vice versa

这其中又出现一个  双旋转的算法： 解决 root-children-grand children 形成左右左  （右左右）的情况

以及   删节点算法：用左子树最大node 代替当前root（右子树最小node），算法结束  需要 rebalance

今天继续之前实验室CV的工作，有一个关于python图像处理的  小坑     po一个：

如果是cv2 这样的图象包，它存储图象的格式都是：H*W*C (与很多现有vision framwork都不同)，更坑的是，在 cv2 的 image reshape 那个接口中，   转换图象的shape 又得是（W，H）   （自相冲突啊。。。。
同样的  PIL.Image 这样的包中也是 HWC
但是进入tensorflow      pytorch  后 就得transpose成CHW  并且进入 网络前  如果无组队batch  还得unsqueeze  一下，  感觉以后的框架可以加个接口直接一步到位，真的麻烦额

2018.11.14
Spring作为现在java 技术后端业务非常常用的框架，据说很多实习 正职面试也会考察 并且也能做加分项

Spring 作为“最”流行框架，其简化java 业务级开发主要通过三大法宝：
1.  DI  依赖诸如：能够使得bean 之间的相互依赖性 通过 注入依赖来 解耦和，达到松耦合的效果。这一招可以大大减弱普通POJO框架下  接口和bean 绑定死的情况，使得每个单独模块的重用性增强

2.  切面AOP： 能够使得每个bean 更加专注于自己的业务，内聚增强，也是大大松耦合

3. 模板代码： spring 有一些接口直接可以替代掉很多模板代码，诸如 JDBC的数据处理模块等

完全二叉树的结构  用线性存储

补充内容 (2018-11-15 12:17):
诸如heap   segment tree

leetcode 63：

经典的 DP 解 迷宫路数：
1 建二维dp存储空间
2 递归求解从左上 到 右下，每次解检查dp，存放dp

樓主是還有多長時間準備?

NathanielNg 发表于 2018-11-15 06:53
樓主是還有多長時間準備?

你好，我是19fall 在申学生，所以真要算到美国的时间，都还有10个月吧，时间线拉的很长，就是想好好准备

刷题吗？想忙完申请的事情也开始刷题