刷题记录帖子

226. Invert Binary Tree Day 1 in June， 1/30
很经典的题目，最重要的是明白，所谓的反转一棵树其实就是每一层都左右互换

recursive 的写法有种美感，真的需要好好掌握下。

237. Delete Node in a Linked List, Day 2 in June， 2/30

这道题目就是 Brain Teaser， 提示是没有给出 head node，这样你无论什么办法都不能得到 previous node，所以其实就是直接覆盖当前 node。。。

同时给出的不是最末尾的 node 又是一个提示，告诉你必须使用覆盖方法。

这道题目做过的，但是还是陷入了固定思维，还是要温故知新。

LC 344. Reverse String 4/30 June

简单题目，主要是 O（1）space 要求

Swap with two pointers

然后就是 recursion 的写法，不过我觉得其实没必要，因为你细品，这个还是 swap，这个是由 O（1）space 带来的要求。

Let's implement recursive function helper which receives two pointers, left and right, as arguments.

Base case: if left >= right, do nothing.

Otherwise, swap s[left] and s[right] and call helper(left + 1, right - 1).

To solve the problem, call helper function passing the head and tail indexes as arguments: return helper(0, len(s) - 1).

LC 528. Random Pick with Weight， 05/30 June LeetCoding Challenge

给个差评，这个题意说的云山雾罩，其实就是转轮法的求取结果，最后的关键是利用 前缀和数组做 二分查找。

LC 406. Queue Reconstruction by Height, 6/30 June Challenge

这道题目还真是让人思考的题目，说白了很简单但是想到还是需要技巧的。最后还是看了这个视频得到了启发， https://www.youtube.com/watch?v=HKHkzKvb0J4

总结起来就是

（1） 升序排列
（2） 一次考虑升序元素，这个时候新插入元素的位置就是由其 second value 决定的，因为当前 result 里面的结果都需要比它大。
（3） 但是这里由一个前提，就是 对于相同 value 的元素必须是按照 second value 的降序排列的，原因也很简单，因为对于相同元素而言，second value 大的应该在后面。但是这个和升序排列矛盾，所以需要用到 python 的 lamda 对 second value 取负数。简直是巧妙极了。

Leetcode 231. Power of Two,  8/30 June

最简单的想法，循环做除法，TLE 了

所以想起来 Binary Representation 用 二进制做，直接把数字转换成 '0' and '1' 的字符，然后 所有 power of two 就是高位是 1，低位全部是 0 的二进制形式。

Leetcode 231. Power of Two,  8/30 June

查看了别人的视频，发现了更加高效的写法。还是基于 binary 数字，但是直接用 binary 的 AND 操作。 https://www.youtube.com/watch?v=AdvGLK43TjA&t=0s

不过，好多算法把时间复杂度打到 O（1） 还是需要钦佩的。比如这个，https://www.cnblogs.com/grandyang/p/4623394.html

这道题还有一个技巧，如果一个数是2的次方数的话，根据上面分析，那么它的二进数必然是最高位为1，其它都为0，那么如果此时我们减1的话，则最高位会降一位，其余为0的位现在都为变为1，那么我们把两数相与，就会得到0，用这个性质也能来解题，而且只需一行代码就可以搞定，如下所示：

代码：

1. return (n > 0) && (!(n & (n - 1)));

复制代码

392. Is Subsequence
经典的题目，two pointers 还可以做这个题目，点赞！

然后考虑进一步优化，主要是 T 如果固定的话，可以用 binary tree 加快搜索。

LC 1 Two sum

啊，复习老题目，发现还是不够稳啊。居然在最后的更新 dict 的部分出现低级失误，应该记住，查找的时候是看当前的数字有没有匹配了，而更新的时候，因为本数字没有匹配，所以是把自己放进去，静等有缘人。

167. Two Sum II - Input array is sorted

经典老题目了，还是需要常常复习，曲不离手。

（1） 按照 Two Sum 的 Map 来做
（2） 按照 Binary Search 来做，但是不是简单的 Binary Search 而是把 Binary Search 和 Two Pointers 结合起来。这样更加快速的找到结果。

如下图，

（3）比较笨的方法就是，循环然后binary search 找另一个 index 这样效率并不是最高的，需要几轮 binary serach。

复习下 Binary Search 的写法，还是要经常练习啊，居然在好几个地方写的特别不专业。反思，还是要稳一手，加大值得练习题目数目。