刷题记录帖子

701 Insert into a Binary Search Tree

啊啊啊啊啊啊啊啊啊啊啊，居然忘记了 BST 的 insert。

其实错误就发生在写法上，最简洁的方法是 如果 遇到null node 就是插入的 node，这个时候确实是需要新建 node 但是也相应的丢掉了，新建 node 的 parent。所以解决方法就是层层 递归的时候层层赋值。

61. Rotate List

经典题，原来的想法是把 value 存在 list 里面，但是更好的方法是学习了这个 讲解 https://maxming0.github.io/2020/10/07/Rotate-List

思想是：

（1） 把 linked list 变成 cycle list
（2） 然后找到 tail，做两件事，一，把 head 移动到 tail 的next，二， 把 tail 的 next set None

return head 即可。

我原来的 code 真是渣实现，反省！

704. Binary Search

基础题，easy。注意 Binary Search， left <= right

449 Serialize and Deserialize BST

其实题目还是很经典，很实用的。但是如何简单高效地实现就是考验功力的地方。

先序遍历tree，然后存下来，注意 int 变成 str 之后必须指定 seperator 不然你不知道怎么切割。
然后，直接在建立树的时候带入，左右子树的范围，开始是 -inf 到 +inf。

具体讲解在这儿， https://maxming0.github.io/2020/ ... nd-Deserialize-BST/

452 Minimum Number of Arrows to Burst Balloons

经典的 greedy 题。

https://maxming0.github.io/2020/ ... -to-Burst-Balloons/

316 Remove Duplicate Letters AND 1081. Smallest Subsequence of Distinct Characters

真是经典题目，删除当前已经有的 char 的条件是，新加入的 char 更小，同时 后面还有想删除的字符，同时 stack 不为 空。
stack 为空，则直接加入即可。

Leetcode 会出现重复题目，比如这道题就是 316， 1081 完全是相同的题目，充分说明 核心题目在大约 500 道 左右。

859. Buddy Strings

简单题，还是要找到 base case 然后分类讨论。

148 Sort List

真是经典题，虽然是用 merge sort 做，但是还是有很多细节要记忆，比如如何找到 linked list 的中间点。

LC 1026 Maximum Difference Between Node and Ancestor

还是很经典的 BST 题目， 递归解决，在每层，都update自己这个路径上最大和最小值，然后更新下全局最大的 abs。

LC 1290. Convert Binary Number in a Linked List to Integer

其实做起来还是很简单的，我是直接用数值方法来做，就是不断 x 2，加上现在的数字。这个原理是可以把二进制写成关于2的多项式的和。然后直接 x2 就是那个多项式2的指数。

不过还有一个方法，是用到 bit operation 的特性。还是要记忆下，这个是 Python 的惯用法。