暑期算法学习&刷题打卡

Background: EE MS 不转CS. 虽是硬件，但心仪职位有一定的coding requirement. 借暑假长草期巩固一下基础。

Plan:
May 16 ~ Jun 30: 重点刷MIT 公开课（23讲） + 算法导论相应部分 + LC部分对应题目
July 1 ~ Aug 30: 重点刷题（easy+medium）。希望一个暑假能仔细过150~200题左右。


上学期找实习的时候因为自己的原因丢掉了一些很好的机会。暑假开个帖，希望能坚持。

Aug 21【158/150】
新题（1）：LC 78（打印集合的所有子集：有趣的一道题，采用回溯法：首先推进空集合，再依次递归调用第i+1个元素以后的集合，最后Pop出。重点复习。）

复习（6）：LC 129（二叉树的数字和。类比于LC 257，采用DFS。重点复习），662（二叉树的最大宽度，采用两个队列完成），114（二叉树展平成链表，这题完全忘了思路。采用后序遍历的方法，重点复习。），450（删除二叉树中的一个节点：有两种初始条件：root == val 【删掉root，返回新root】和root != val（找左节点里的最右节点，或右节点里的最左节点），重点复习。），98（二叉树的判断，方法不好：最优解里的helper函数是怎么实现的？），236（二叉树里最小的公共祖先，带入了之前BST里最小公共祖先的思路，先找位置，但太过复杂。比较优的解法里条件三种：if(root == NULL || root == p || root== q） return root; ptr_l = (root->left, p, q); ptr_r = (root->right, p, q); (ptr_l == NULL) ? ptr_r : (ptr_r == NULL)? ptr_l : root; 需要重点思考一下这种问题的分析方法）

树的专题算是又过完了一遍。今天复习的题目都要再次复习。

July 2【73/150】
新题：LC 437 (Path Sum 3, 注意这一题和Path Sum 1/2的区别： 路径未必从根节点开始。基于1/2的解法，可以设置标记：如果涉及节点，则和1/2相同，否则继续寻找sum为total sum的路径), 538（Convert BST to Greater Tree，注意观察：应该采用反向中序遍历法，即遍历右孩子节点--改变父节点--改变左孩子节点）, 563（Binary Tree Tilt。这题同样有特点：可以分别计算每个节点的tilt，再全部相加，但遍历多次，速度很慢。可考虑后序遍历：左孩子tilt=0+左孩子val--右孩子tilt = 0+右孩子val -- 根tilt = 左孩子和+右孩子和+根val）, 671（特殊二叉树里第二小的值：这题注意应该逐次比较对孩子节点的最小值，容易漏掉情况）, 461（Hamming Distance）, 191（数中非0位的个数）461，191属于同一类型题，公式是：while(n){count ++; n &= n-1;}

前几个树的题目目测需要反复做。
复习：LC 112 (Path Sum，一次accepted).

Aug 28【166/150】

新题（2）：LC 209（最小size的子数组和。非常有意思的一道题。有以下几种做法：1. 暴力法：超过时间限制。2：滑动窗+部分暴力法：和之前的sliding window题类似，记录从0-i每一个点的当前和。记得最开始要插入0，然后再确定最小的j-i。3：滑动窗+二叉搜索：记录每一点的和，利用二叉搜索（手动/lower_bound函数）确定值是否在某一区间内。如果存在，则长度是最小的lower_bound-(sums.begin()+j)，这里要进行强制转换。重点复习。），222（完全二叉树的节点数，有以下几种做法：1. 遍历（全部超过时间限制），2. 递归：初始条件：计算层数的同时计算左右高度是否相同。如果相同则是完美二叉树。所有的节点数是2^h-1。否则则是不完美二叉树，数量1+判断左子树+判断右子树）

复习（5）：LC 144, 145, 94（二叉树的三种遍历，用堆栈完成），701（插入二叉搜索树），450（删除二叉树中的元素）

同是ece,顶楼主一下

May 16: MIT Lec 1: Intro and Algorithm Complexity

我和你一样差不多三个月时间，200道题时间足够的，另外硬件还是转CS吧。。。别为难自己。。。

刷过MIT算法，我做了一个笔记楼主有需要可以参考参考，互相学习，https://github.com/aaronoah/algorithm-cracker

Day 2: MIT Lec 2..
上班的晚上还是得努力打起精神来啊。。。master method need to be more clarified.

github新开了repo刷题，代码不行刚开始github搜索 ShiqinHuo/LeetCode_Rookie 。。我好像发不了URL   

May 20-21: Textbook chap1-3. 周末生病跳票。。这周走向正轨

虽然几乎每天都能刷题但总是忘了打卡。。。
June 19
LC 94, 144, 145. 二叉树的三种遍历。。。

补充内容 (2018-6-19 16:44):
LC 617二叉树加法，复习LC 237 （未一次accepted, 还以为是遍历中查找呢。。摔）， LC 206, 21, 83, 141

补充内容 (2018-6-20 22:54):
【44/820】

June 20 【46/820】
新题：LC 142 (有环链表2) 82（去除相同节点-仅保留出现一次的节点）
这两题corner case第一次见有点难想到
再次复习 LC 141（有环链表1）83（去除节点1）