要求空间复杂度On，时间复杂度O(nlogk)。 一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现 最大的 K 个：小顶堆 最小的 K 个：大顶堆 堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。注意！大顶堆or小顶堆并非是从大到小的序列，因此才需要堆排序！ 堆可以分为大顶堆和…

感觉面试会考 有两种常规方法，哈希表与排序。但是做不到空间复杂度O1，时间复杂度On。 投票法： 核心思想是，如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。 选择一个cnt初始化为0，选择一个res 遍历数组，如果cnt为0的时候，就选择当前数字作为res 若cnt不为0，re…

类似dfs全排列问题。 有一道相似的题目，可以参考acwing的解析：AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing，题目如下： 给定一个整数 nn，将数字 1∼n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。 算法： 用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。 …

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n^2)要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 二叉搜索树：左<根<右 法1：中序遍历将二叉搜索树进行中序遍历可以得到由小到大的…

涉及一个知识点，深拷贝与浅拷贝。 特性深拷贝 (Deep Copy)浅拷贝 (Shallow Copy)定义创建一个新对象，并递归复制所有成员及其指向的资源仅复制指针值，新旧对象共享同一块内存内存管理新旧对象完全独立，修改互不影响修改任一对象会影响另一个（可能导致双重释放或内存泄漏）性能较慢（需分配新内存并复制数据）极快（仅复制指针）使用场景需要完…

递归，用一个vector存储中间的path路径。 #include <vector> class Solution { public: // 一个存放最后结果，一个存放临时结果 vector<vector<int>> res; vector<int> path; void dfs(TreeNode* root, int ta…

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。数据范围： 节点数量 0≤n≤10000≤n≤1000 ，节点上的值满足 1≤val≤1051≤val≤105 ，保证节点上的值各不相同 要求：空间复杂度 O(n) ，时间时间复杂度 O(n2) …

法1：辅助栈 同时用两个指针i, j分别指向两个序列的头部, 每次我们先将i所指向的元素压入栈中, 然后i向后移动一步, 之后再检查当前栈顶, 若对应上了弹出序列中j所指向的元素, 则弹出元素, j向后移动, 再继续检查, 直到栈空或栈顶元素和j所指元素不等为止 class Solution { public: stack<int> s1; …