liweiwei1419 / leetcode-solutions-in-good-style Goto Github PK

二分法不是常规做法。

已经有比较好的题解了，看看是否有必要再写。

把题解都整理一下。

用 BFS，与“104. 二叉树的最大深度”比较。

首先说排序。

1、快排

2、堆

• 因为即使整型溢出，结果都能保证正确，作图解释这件事情，写代码验证这件事情。

• 把以前做过的所有练习都改一下，提交上去看看结果如何（真的有点颠覆啊）。

• 用幻灯片展示最重要的内容，现在文章的东西很多，读者容易看着厌烦。

• 提供练习的参考答案。

题解要点：

• 官方题解先想到堆，发现问题以后，再使用双向队列。

• 队列中存放的是索引的原因：左边界将要划出“滑动窗口”的时候，把它拿掉。

• “队首”永远是“滑动窗口”的最大值。

这道题要写题解了，我的 Python 答案在评论区，有一个用户已经表示看不懂了。还是得写得细一点。

二分法。

以下选自和 yao 同学的讨论。

例子：我用 [2, 5, 6, 7, 9] 试了下。

固定 2 和 5 用二分法找的第 1 个不能构成三角形的数是 7，它的下标是 3。

找到 7 是第 1 个不满足构成三角形的索引，它之前，j 之后的数都可以，所以是 k - j - 1，7（包括 7）以及之后的数都不可以。

参考资料：https://leetcode.com/problems/valid-triangle-number/solution/

参考资料：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/solution/20ms-98cshi-yong-bst-by-ygtxr1997/。

快排的那个版本，颜色分类，重新写一遍。

搞清楚“满二叉树”和“完全二叉树”的定义。

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

方法一：递归

方法二：双向队列

思路简单，但是编码上有两种写法。

动态规划还蛮有意思的。

是否是 AVL 树，用定义：$abs(left - right) > 1$ 就不符合。

• 后序遍历；
• 特殊标记：$-1$。

如题，讲清楚树状数组还是比较困难的，试试看，做一个 PPT。

旧的文章备份在自己的简书，或者自己的博客里面。

设置辅助的数据栈，有两种写法。

1、辅助栈和数据栈同步；

2、辅助栈和数据栈不同步。

二者性能差不多。

一定要画图，才能很清晰地展示这道题的思路。

• 后序遍历；
• 递归改造成循环；
• BFS（使用 queue），且要看当前 queue 的结点个数；
• DFS（到叶子结点才结算）。