牛客283182957号

分类

题解(51)

/ 注册

全部文章（共52篇）

题解 | #数据流中的中位数#

传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可。但是这道题因为数组在不断增长，每增长一位便需要排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化，这个过程就让我们想到了插入排序：对于每个输入的元素，遍历已经有序的数组，将其插入到属于它的位置。 ...

C++

2022-06-24

0 307

题解 | #寻找第K大#

1.快排，就是每个元素都归位，如果某一元素刚好在k位那他就是第k大第一个元素temp 然后第1位为 i 最后一个为j 从j开始j--，如果遇到比temp大的应该在左边，放入i 然后i++，直到比temp小的应该放在右边 j的位置然后继续j--，&nb...

C++

2022-06-23

0 319

题解 | #最小的K个数#

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)O(log_2n)O(log2n)，而每次取出堆顶元素都是...

C++

2022-06-23

0 275

题解 | #滑动窗口的最大值#

我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时依次从尾部排除掉之前的小值再进入，每次有新值进入的时候，都会判断是不是比当前的值小，所以每次其实都比较判断了一次。如果新值比当前值（窗口...

C++

2022-06-23

0 364

题解 | #有效括号序列#

step 1：创建辅助栈，遍历字符串。 step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的呦括号加入栈中，期待在后续遇到。 step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。 step 4：其他情况下，如果遇...

C++

2022-06-22

0 263

题解 | #包含min函数的栈#

step 1：使用一个栈记录进入栈的元素，正常进行push、pop、top操作。s1 step 2：使用另一个栈记录每次push进入的最小值。s2 step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元...

C++

2022-06-22

0 229

题解 | #输出二叉树的右视图#

step 1：首先检查两个遍历序列的大小，若是为0，则空树不用打印。 step 2：建树函数根据上述说，每次利用前序遍历第一个元素就是根节点，在中序遍历中找到它将二叉树划分为左右子树，利用l1 r1 l2 r2分别记录子树部分在数组中分别对应的下标，并将子树的数组部分送入函数进行递归。&...

C++

2022-06-21

0 316

题解 | #重建二叉树#

数字1是根节点，并将二叉树分成了(247)和(3568)两棵子树，而子树的的根也是相应前序序列的首位，比如左子树的根是数字2，右子树的根是数字3，这样我们就可以利用前序遍历序列找子树的根节点，利用中序遍历序列区分每个子树的节点数。 1. 分别是两个数组，返回的是当前数组的个数，是装着...

C++

2022-06-17

0 310

题解 | #序列化二叉树#

采用先序遍历 1.二叉树转字符串，按要求先序转即可。注意调用是用的str的引用特别的 &(引用)==>用来传值，出现在变量声明语句中位于变量左边时,表示声明的是引用。 &(取地址运算符)==>用来获取首地址，在给变量赋初值时出...

C++

2022-06-16

0 262

题解 | #在二叉树中找到两个节点的最近公共祖先#

1.普通二叉树失去了平衡二叉树的性质，所以用平衡二叉树的法二特征无法求解，只能用有普适性的法一求解。 2.平衡二叉树的法一，可以利用左结点小于根小于有结点的性质，去减小搜索结点的区间。但是普通二叉树只能逐条分支去搜索直至找到目标结点，同时获得其路径。 3.获得路径后寻找祖先的方法与平衡二...

C++

2022-06-15

0 225