刷题记录帖子

LC 593 Valid Square

我想到了用边长做，然后利用边长的比必须是 sqrt(2) 来检查。

但是这个其实是不太对的，因为会出现如下这个情形。

但是我的解依然是对的，因为题目要求座标是整数，integer。那就没问题了。

说到官方答案的第二个还是很好的，就是根据 x 座标排序，派完了，就只有如下个组合了，

当然还有一种解就是如下这个帖子的内容, https://maxming0.github.io/2020/11/11/Valid-Square/，还是很好，直接检测 4 个相同的 小 value，然后 两个相同的 大 value。

LC 845 Longest Mountain in Array

一开始的想法是求出差值，然后看 diff 数组的正负变化，但是这个显然不能实现 O(1) Space  和 One Pass。

其实，这个时候就应该想起 double pointers，对于数组， double pointers 是非常常用的思路。

参考这个解法，这个解法还真是巧妙，值得记忆！

382. Linked List Random Node

失误了，居然没想到  Reservoir sampling.

897        Increasing Order Search Tree

Easy 题，主要是 in order 然后 on the fly 修改 Linking of nodes

1492 The kth Factor of n
老老实实做，注意下平方数 和 1~ sqrt(n) 即可

不过在视频上发现更加巧妙的解法，这里抄录下来，https://www.bilibili.com/video/BV1ha4y1H7vz

巧夺天工，巧妙利用了对称了 k 在 Python 中反转过来的 -k 作为倒着计数的特点。

605 Can Place Flowers

啊，还是太年轻，不知道优化。这道题目这个视频讲解的很好，https://www.bilibili.com/video/BV1Uz4y1k7xU

学习了，Greedy + Adding Two Zeros to the end of the list 因为在 list end 添加比在头上添加更加快！

我的代码，

但是原作者的更加 优秀代码，

117. Populating Next Right Pointers in Each Node II

还是基本套路的变体，就是 level traverse 的变体。

59 Spiral Matrix II

还是很好的题目，学习到了很多写法，感觉这个 optimized 的解法真是高明。代码简洁，也没那么多 if else 处理。

https://maxming0.github.io/2020/12/07/Spiral-Matrix-II/

1010 Pairs of Songs With Total Durations Divisible by 60

之前暴力求解的还是 N^2 的复杂度，看了这个解答，发现了更加巧妙的解法，还是需要提高自己的水平。

https://www.youtube.com/watch?v=SAzo0a2cj1c

而且这解法还巧妙利用了 Counter 返回的 dict 对于未出现的 key 返回 0  的特性，简化了代码，同时固定了检测操作数，现在复杂度只有 N.

官网的这个解释也很不错。

173 Binary Search Tree Iterator

其实最简单的就是直接 in-order 遍历，简单方便。但是初始化效率较差。

然后的好方法就是，用 stack 来做，参考这个帖子, https://maxming0.github.io/2020/ ... arch-Tree-Iterator/。