暑期算法学习&刷题打卡

July 13【104/150】
新题：LC 199（二叉树的右视图）用BFS+堆栈做的。一次accepted.
复习：94，144，145（二叉树的前序，中序，后序遍历。均采用堆栈完成。注意：后序遍历可视为NRL+堆栈的操作。可转化为前序遍历。）

July 16【110/150】
新题：LC 623（向树中插入一行，采用递归完成，一次accepted），700（二叉树中搜索元素，递归解法），701（二叉树插入元素，这里需要理解为何只需要递归写法就可以，而不用做额外的“插入”操作，需要重点复习），450（二叉树删除节点，注意这道题的算法：若根节点val=待删除val，如果没有右子树，则直接删掉头结点，将左节点返回为头结点。若有右子树，则寻找右子树的左节点（若存在）或者右节点（左节点不存在）并交换根节点和该节点，直到把该节点移除，需要重点复习），114（将二叉树展平为链表，注意算法：后序遍历，定义前驱节点，右节点等于前驱节点，左节点等于NULL，需要重点复习，仔细理解递归顺序。），66（数组元素末尾+1，利用reverse+push+pop完成，下次可选择用insert完成）

遗留：
LC 421（Hamming距离的和，为啥之前的汉明距离函数到这里产生的结果不一样？汗。。。）

July 17【113/150】
新题：LC 442（寻找数组中的重复，和之前的题目基本一样，一次accepted），189（旋转数组，和旋转链表比方便了很多，一次accepted）,652（寻找二叉树中相同的子树，感觉用C++做算难题，要重点复习。。这题感觉没有很简单的方法啊。。比较树的部分利用了之前题目中的递归做法）

July 18【116/150】
新题：48（旋转图像90°，一般方法是：reverse A, 转置上一步得到的A），832（翻转图像），867（矩阵的转置，初始化二维vector的方法：vector<vector<int>> B (A[0].size());），543（二叉树的直径，code可以再简化，直接比较深度即可）
复习：LC 450（二叉树删除节点，注意交换的节点一定是右子树的最左元素。），104（二叉树最大深度）。
中段稍微有点疲劳，希望克服will power.

July 20【121/150】
新题：LC 80（让array中的每个元素不超过2个并返回数组，采用了O(N2)的算法。。虽然accepted了还是得看看。。），231,326,342（分别判断一个数是不是2/3/4的N次方，标准解法：如果小于0，则假；否则当余数为0的时候一直除2/3/4，最后的结果为1时返回真。对于2的N次方的特别方法：return n > 0 && n & n-1 == 0, 4则要确保1都在奇数位：所以相比2要加一句：&& n & 0x55555555  == num）.

复习：LC 652（判断一个二叉树里是否有相同的子树，采用序列化的方法，将二叉树的子树转化为带括号的字符串，并记录在哈希表里。需要重点复习。）

July 23【126/150】解锁了第一道DP。。
新题：LC 98（判断一个树是否是BST。思路：除了判断左/右节点一定小/大于node->val，还要注意左/右节点的最右/左节点一定要小/大于根节点。），501（二叉树中的模式（出现最多的元素），采用哈希表，虽然超过大部分，但还可以优化：少用一个哈希表，在当前max_val<cur_val时清空数组即可），746（爬梯子的最小代价，经典的动态规划问题，采用递推），70（爬梯子的不同方法，感觉动态规划的核心就是找到递推关系。。），53（最大的子数组，同样用递推，一次accepted，开心。。）

July 24【130/150】
新题：LC 198, 213, 337（入室抢劫系列题目：第一种类型为单向数组。算法是：第二个元素应该是第一个和第二个的最大，后面的递推是v[n-1]和nums[n]+v[n-2]。第二种类型是数组的头尾相连，数组的首尾不可同时取，较为简单的方法是做两个数组，一个仅含头，另一个仅含尾。第三种类型是二叉树，比较的是当前节点+孙子孙女节点和儿子女儿节点的较大者。注意：为何解析中的ll，lr，rl，rr为0但答案仍然成立？需要重点复习。。）872（相似的叶子结点。。。直接遍历，推叶子，一次accepted。）

July 25【133/150】
新题：LC 687（二叉树中最长的单值路径，重点复习。两个条件：要么左右都有，要么仅有一边。比较的时候要比m = max(m, l+r)，以及max(l,r)，感觉这题是easy里的复杂题了。。），122（何时卖股票2，条件是可以卖多次。采用波峰波谷法，仅需一次遍历即可。）
复习：LC 121（何时卖股票1，条件是只能卖一次。这次采用Brutal Force之外的方法：定义max_profit, min，若当前值<min，则min = 当前。若num-min>max_prof, 则更新prof。好处是一次遍历）
遗留：714（何时卖股票3，条件是有交易费。。太困了动态规划没想明白。。）

July 26【135/150】工作事情多只刷了两题而且很气。。
新题：LC 219（包含重复2，采用哈希表完成。也可采用unordered_set中的erase完成。），709（大写转小写）
遗留：LC 220（包含重复3，恶心的corner case。感觉高票的几个discuss全都跪在了新补的这个test case上。明天想想怎么做。生气。生气。）
还有15题第一轮结束。暑假的基础目标胜利在望了。

July 27【140/150】今天说是大部分新题实际都是复习。。
新题：LC 559（多叉树的最大深度，类比于二叉树的最大深度，注意max函数的写法），589, 590, 429（多叉树的前，后和层序遍历，和二叉树的遍历一模一样。做题的时候还在想为啥没有中序，发现这里中序好像定义不了。下次可以用堆栈解决前后序遍历。），387（返回第一个唯一字符的索引，哈希表一次解决。）
复习：LC 104（二叉树最大深度）