暑期算法学习&刷题打卡

Aug 16【154/150】
复习（7）：LC 257（字符串打印树），113,437（Path Sum2,3），110（平衡二叉树），111（二叉树最小深度，注意两种情况：左右取得是最小值，只有一边取得是最大值。这题完全忘记了思路，重点复习。），654（最大的二叉树），814（修剪二叉树，记得把叶子剪掉之后根也得剪。。最好的方法就是写一个判断全0子树的helper function）

Aug 17【154/150】
复习（5）：LC 513（最左下角的孩子，BFS），515（每一列的最大值，BFS）, 508（最常见的子树和，后序遍历+hash table）,701（二叉树插入节点，要记得递归条件：空节点，则新节点是根节点。若比根小，则root->left = insert，反之则root->right = insert，重点复习），623（二叉树加一行，BFS，速度慢。可用递归）

跳过（2）：LC 230（第K小的元素）， 199 （二叉树的右视图）

补充内容 (2018-8-17 17:07):
遗留（1）：LC 337 (抢劫房子3，和抢劫1，2一起来吧。。)

Aug 20【157/150】做了3个新题。。
新题（3）：LC 695（最大的岛，注意递归条件，及if里的先后顺序。），463（岛的周长，感觉是数学题），888（公平的糖果交易，可以用unordered_set里的count来查找是否有相关元素，降低复杂度。）

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; 需要重点思考一下这种问题的分析方法）

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

Aug 22【160/150】
新题（3）：LC 89（n bits Gray Code，需要记忆方法：Step 1： 1<<n，Step 2: while (1 < (1<<n)) Gray code = i ^ (i >> 1).）， LC 90（Subsets 2, 为了避免重复，应该先排序，再跳过n[i] = n[i-1]的项。需要重点复习。），717（最后一位是1bit还是2bit的判断，通过观察得知：从第一位起，如果出现0一定是1位数，1一定是2位数。据此判断i == size()- 1时是0则一定是1位数。）

复习（2）：LC 78（数组的子集，回溯法），LC 1（Two Sum 1。。一定先判断互补集合再推入哈希表啊。。居然没有一次accepted。。。）

CxtxG330 发表于 2018-8-14 10:06
C艹。。。。字数字数

为啥用c++呢，刷题而言的话， 这语言是比较java有优势吗？

Aug 23【161/150】

新题（1）：LC 409（最长的回文。漏掉了奇数个情况下取偶数个补充进回文的case。）
复习（4）：LC 125，680（合理的回文1/2）， 9（判断回文数，既可以转化成字符串，又可以拆成一半的数），167（two sum 2）

不知不觉暑假最后一周了，tired.

Aug 27【164/150】

新题（3）：LC 33（打断有序序列的二叉搜索，采用取模替代）, 81（打断有序序列有重复的二叉搜索，可以用哈希表，但速度慢。这题有一个比较有意思的算法：while(start <= end)如果开始=中，中= 后，前后指针同时向前后动。否则判断左半边是否有序。如果有序则判断值是不是在里面。否则判断右边是否有序，如果有序则判断值是否在里面。需要重点复习。），704（二叉搜索）
复习（3）：LC 206（翻转链表，递归&迭代），141（链表有环判断），142（判断有环链表的起始点，注意如果是dummy开始，两个指针相遇后应分别回到dummy和ptr_fast->next）

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（删除二叉树中的元素）

Aug 30【168/150】
新题（2）：LC 50（x的n次幂计算，投机取巧的方法是直接return pow(x, n).....也可以用递归/2分算法做）, 16（Three Sum Cloest，类比three sum，注意判断条件，重点复习。）
复习（2）：LC 242（等价的字符串，两个哈希表对象可以直接比较。），15（Three Sum，这题应用2指针，完全忘了之前的做法怎么做。最优解是O(n2）