刷题记录帖子

151. Reverse Words in a String

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

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

LeetCode 50 Pow(x, n)

通过二分法巧妙解决暴力超时问题，这个讲解很经典， https://www.youtube.com/watch?v=snOaKR2xgZg

另外就是用 helper 函数写法，

还有写法就是不写调用，直接每次除以 2 ，然后相乘起来。参考这个视频讲解， https://www.youtube.com/watch?v=Twr5TD8Fvbo

347. Top k Frequent Elements

我是用 HashMap 统计出现次数做的，通过，但是比较繁琐，参考了 LC 的官方答案，原来可以用 MinHeap 精彩！ Top K 这种题目需要有这种看齐意识，意识到可以用 Heap 解决。

https://leetcode.com/articles/top-k-frequent-elements/

当然参考下， heap 如何在 Python 中使用，

LeetCode 203. Remove Linked List Elements

现在更喜欢的写法就是设置一个 dummy node 这样解决掉开头节点需要特殊处理的 edge case

LeetCode 79 Word Search

经典题目啊，还是需要注意掌握，这个讲解很好。题目需要思路清晰，比如 触发了 DFS 的时候其实可以直接写入 条件判断，然后最后 visited 数组如果没实现，还是需要恢复的。

这个讲解，说了优化 space 的思路，还是很巧妙的把访问过的 char 换成 对应的 ord assic 编码，如果不行再换回来，这样就可以把 space 减少到 1，巧妙地使用原数组。

LeetCode 103 Binary Tree Zigzag Level Order Traversal
还是很简单的，就是 level traversdal 的变体，只要知道是正序还是倒序即可。

还有一种利用递归的方法，也很巧妙，不过我还是喜欢 level traversal 的写法。 https://www.youtube.com/watch?v=AS4VzB4Vojs

260. Single Number III

巧妙至极的 Bit Operations
两个关键点， XOR  的特性：

0^0 = 0
x^x = 0

不同就会是 1.

既然有两个数字会不同，那么找出这个不同的位，然后把数字分组即可，这两个不同的数字就会按照这位的不同分为两组，形成两个奇数组合，然后直接分别 XOR 即可。

至于找到这个 1 bit 的位数很简单， n AND (-n) 即可。

Leetcode 258. Add Digits

简单题目，直接把 int 拆成字符串做，但是 follow up 很有意思 https://leetcode.com/articles/add-digits/ LC官方的解释非常简洁精炼。

值得反复记忆。

解法 1

O(1) 的解法，其实又一个很好的发现方法，先手动尝试下么，从特殊的尝试到发现一般规律，https://www.youtube.com/watch?v=j31ZOupyrAs&feature=youtu.be。

LC 621 Task Scheduler

还是花花的这个讲解非常精髓，https://zxi.mytechroad.com/blog/ ... 621-task-scheduler/

如果任务有很高的多样性，不同的任务，那么其实不用担心 n，你直接放就行，这个时候就是 tasks 的number。
但是如果任务的多样性不是那么高，你就需要考虑怎么排列任务：

先放下高频的任务附加上 n 个 following slots 作为一个整体考虑，然后再考虑非高频的任务。

如花花的这个图，

edge case 就是上面说到的 多样性情况，只要总任务数目多于刚刚求出来的数字，我们就可以直接输出 任务总数。

代码如下

另外的解法就是做 simulation，用 heap 来模拟摆放的过程，如这个讲解， https://www.youtube.com/watch?v=wTUsb3nuOCQ

309 - Best Time to Buy and Sell Stock with Cooldown

好经典的题目，回味无穷。这个两状态转移方程的DP讲解最好，https://www.youtube.com/watch?v=Ggzbo9eVrLU

核心点都在这个截图里面

总结下
（1） 对于每一天的状态，就两种 hold 和 unhold。
（2） 对于每一个状态，都有两种途径到达：
         2.a hold
                 2.a.1 当天没买入，那就只能是 i-1 的 hold 继承下来的
                 2.a.2 当天买入了，考虑到 cooldown 那就只能是前两个时间的 unhold 加上买入付出的欠款，因为 i-1 必须是空白的 rest，i 还能买入，所以 i-2
必须是 unhold
         2.b unhold
                2.b.1 当天没有卖出，那就只能是 unhold[i-1] 继承下来
                2.b.2 当天有卖出，那就是 hold[i-1] + 当天的价格
（3） 最后的答案一定是 unhold[i-1] 因为你 hold 就相当于花出去一笔钱，但是还没收回来。

代码如下，注意下如何初始化