刷题记录帖子

复习一道老题目， 15. 3Sum

还是老思路，固定一个数字，然后循环另外两个，最优可以做到 N^2

LeetCode 662  Maximum Width of Binary Tree

一开始的解法非常笨拙，还是看了这个 https://www.youtube.com/watch?v=le-ZZSQRebw 连接发现了巧妙的方法，就是给每个 node 安排一个 idx，
然后就是就是对于 idx 做减法即可。当然这里的 idx 必须是 full binary tree 上的 idx。

430. Flatten a Multilevel Doubly Linked List
这道题目真是回味无穷的一道题目，精彩！～

核心思想其实就是把 一个 多个 level 的链表放在一个 level 上。核心其实很简单就是知道在 哪个 node 进入 next level node 然后把 tail of next level 链接到 current level 进入 node 的next。

如下图所示，

第一种解法，真是骚操作的一种解法，非常精彩。不用 stack 然后进入下一个 level，然后直接把该 level 全部到了最后找到 tail 在把这个 level 链接到上一层。在进入新的 next node。

过程如下，

第二种解法，用 stack， 这是最优雅的一种方法，其实就是先把 next 压入 stack，再把 child 压入 stack， 然后每次取最后一个进入 stack 的。 这样的情况下，其实就是进入下一个 stack，当然返回之后，其实就可以找到下一个 node。

论坛帖子超过 60 分钟不能编辑，真是愚蠢的设计。。。
这里还是记录下上一题的结论，想多增加下解法都不行。

第二种，用 stack 的解法，参考这个视频， https://www.youtube.com/watch?v=yjqP3kiUW28&t=132s

第三中解法，使用递归。但是需要特别注意递归的处理，其实是直接到最 bottom 的 level 然后返回。注意这里调用逻辑，

代码，

78. Subsets

参考讲解， https://www.youtube.com/watch?v=1BbeOUkUOak

第一个还是大家最熟悉的解法，就是不断 recursice 的增加。
答案示意图，

代码，

高级解法就是高德纳的 BitMask 解法，直接参考 LC 的解答，感觉可以背诵全文讲解的非常好。

https://leetcode.com/articles/subsets/
一个重要的知识点，是如何产生符合要求的 BitMask，参考下面的图。

LC 190. Reverse Bits

发现如果Leetcode 提供了他们的解答，一定要仔细研究，甚至背诵全文，这个解答写的太好了。

https://leetcode.com/articles/reverse-bits/

对于交换 bit swap， The key idea is that for a bit that is situated at the index i, after the reversion, its position should be 31-i (note: the index starts from zero).

1344. Angle Between Hands of a Clock 小学题目，简单的转换关系。

补充内容 (2020-7-15 04:00):
发现还有更加巧妙的解法，就是取 mod 直接省去了 if-else

还是接上面的题目，发现可以用mod代替 if-else，这样更加精简代码。

151. Reverse Words in a String

基础题， string 惯用法练习。

但是如果需要 O(1) Space 那么这道题目就没有这么简单了。

这个视频给出了很好的思路，https://www.youtube.com/watch?v=gnc346YTBps&t=413s

分两步做，


（1） 把整个 string reverse 过来
（2） 对于 reverse string 把里面的每一个单词再 reverse 过来

这个视频给出了很好的 找到每个 word 的方法，two pointers

151. Reverse Words in a String

还是这题，但是做的时候发现还是需要仔细啊。可以直接 用 Python， split() 默认是匹配空格和多个空格，但是你要是多此一举，写成 split( " " ) 那就变成只对一个 空格 切分，那么如果多个空格相连，就会切出来一个 空格 element。这是非常不好的。

同时别忘了 Python 的 reversed() 函数。