暑期算法学习&刷题打卡

求问楼主MIT公开课到哪可以看啊？

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).

July 3【77/150】暑假基础目标完成1/2.
新题：LC 235（最小的公共祖先1--BST）, 236（最小的公共祖先2-BT。235可用236的方法解决，递归条件：若左子树不存在任意一节点--找右子树--右子树不存在任意一节点--根节点是公共祖先）, 61（旋转链表，下次可考虑用先成环再取余的方法完成）, 448（求消失的元素，利用哈希表，或者采用位操作思想均可）.
复习：LC 538.

July 4 【81/150】
新题：LC 572 (树的子树。这题自己用的方法过于繁琐，先找相同节点，再逐次判断是否一样（借用is same tree那题的递归方法）开销大), 515（树每一层的最大元素，采用BFS层序遍历，一次accpeted）513（树最下一排最左的元素，同样采用BFS加计数的方法），814（二叉树的修剪，实际上就是判断全0子树）

TBD: 654, 107

July 5【86/150】
新题： LC 230 （BST里第k小的元素，直接采用Inorder遍历的方法）， 15（Three Sum, 三个指针，注意如何跳过重复元素以避免压如相同结果，需要重点复习），693（给定整数，判断二进制数是否是交叉位，采用取余法，占用额外空间。下次试试位操作），783（BST节点之间的最小差异，私以为题号里叫distance不太对，同样采用中序遍历），654（最大的二叉树，这题构造含有上下界的构造树函数，并进行递归。注意边界条件，以及求最大idx的方法，需要重点复习。）

同开始刷题，请问题主有组织吗？或者加下微信一起讨论也好，我的微信是miaomiaoyuwen

July 8 【89/150】
新题：LC 508（最常见的子树和，采用后序遍历+哈希表），147（插入排序链表，需要多加理解插入排序的思想，重点复习），476（反转位，Note: 为何不可直接取反？思路：做Mask：00000101的mask是：11111000，再各自取反相与）
又到周一了。。。

July 9-10【94/150】
被25题卡了很久。。。
新题：LC 24（Swap node in pairs）， 25（以k个元素为一组翻转链表。24题其实是25题k=2的特殊情况，涉及到前面写过的翻转链表1 & 2（翻转部分链表）。麻烦的地方在于记录翻转前后的插入点，并判断在剩余元素不够凑成K组时不要反转的情况。Debug时间较长，需要脑子特别清楚才可以。翻转之后记得更新入口，出口指针位置。24题可以用25题的方法，考虑到只有2个元素交换，可以用递归法），169（最多的元素，用哈希表秒杀），643（拥有最大平均值的子数组，用brutal force虽然可以但是太暴力了。。忘记了记录所有的sum和。。。）109（从链表中构建数组，用递归写法。这题和从数组中构建链表思路一样，但是未能立刻反映出来，还是要复习。）

复习：LC 92（翻转链表2）101（判断对称的树）Dummy Node是个好东西。。。

July 11【98/150】 新的主题转向堆栈。
新题：LC 225（用队列实现堆栈）, 232（用堆栈实现队列，和225很像。注意pop和top其实差不多）, 155（求堆栈中的最小数，没有仔细考虑就用了Brutal force。。。摔。。可以用一个储存最小元素的堆栈，如果有比栈顶小的元素，则入栈。最终的top则是最小栈的栈顶。注意：在弹出时，要在两边同时弹出同一个元素，或者在入栈的时候重复压入栈顶）, 103（二叉树的Zig-Zag遍历。也就是层序遍历。。不过在外写的help函数不知为什么一直没有Debug出来，只好借助内在的reverse函数了。此外，层序遍历时，如果队列头为NULL，一定要判断队列是否为空再决定是否再次推入NULL）

July 12【103/150】
新题：LC 338（计算1-n之间每一个数中1位的个数。这题的思路也是while(n){i++, n&=n-1}。注意：第i-1个数的结果可以用到第n个里。会降低复杂度（为什么可以这么写？ ）），414（第三大数。傻瓜方法是直接排序，占用O(n)额外空间），215（第k大数，同414），628（三个数的最大乘积，注意分类讨论不同情况）129（树到叶子的数字和，感觉比较难。递归思路：和=左孩子和+右孩子和+10倍根节点和）。

复习：94（二叉树的中序遍历，采用堆栈。思路：当堆栈不空，或者现节点不空的时候继续循环：如果节点不空，则继续前往左节点。若空，则取堆栈top，推入结果，堆栈弹出栈顶，当前节点变为top右节点。）