描述 这是一篇针对初学者的题解。共用三种方法解决。知识点：数组，堆，快排难度：二星 题解 题目抽象：求给定数组的topK小问题。 方法一：排序 直接排序，然后去前k小数据。 代码 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> ret; if (k==0 || k>input.size()) return ret; sort(input.b...

描述 这是一篇针对初学者的题解。共用三种方法解决。知识点：数组，排序，哈希难度：一星 题解 题目抽象：给定一个数组，找出数组中的众数，若有，返回众数，若没有，返回0众数定义：数组中出现次数大于数组一般的元素 方法一：哈希法 根据题目意思，显然可以先遍历一遍数组，在map中存每个元素出现的次数，然后再遍历一次数组，找出众数。 代码 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { unordered_map<int,int> mp; ...

题目的主要信息： 给定一棵二叉树的根节点，求这棵树的最大深度 深度是指树的根节点到任一叶子节点路径上节点的数量 最大深度是所有叶子节点的深度的最大值 叶子节点是指没有子节点的节点 举一反三： 学习完本题的思路你可以解决如下题目： JZ82. 二叉树中和为某一值的路径（一） JZ28. 对称的二叉树 JZ27. 二叉树的镜像 JZ79. 判断是不是平衡二叉树 JZ37. 序列化二叉树 方法一：递归（推荐使用） 知识点：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要...

举一反三： 学习完本题的思路你可以解决如下题目： JZ77. 按之字形顺序打印二叉树 JZ78. 把二叉树打印成多行 方法一：层次遍历（推荐使用） 知识点：队列 队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。 思路： 二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助： 因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一...

题目的主要信息： 给定两个序列，第一个表示入栈顺序，第二个表示出栈顺序 序列中没有重复的数字 判定第一个入栈顺序能否得到第二个出栈顺序 举一反三： 学习完本题的思路你可以解决如下题目： JZ9. 用两个栈实现队列 JZ30. 包含min函数的栈 方法一：辅助栈（推荐使用） 知识点：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 思路： 题目要我们判断两个序列是否符合入栈出栈的次序，我们...

描述 这是一篇针对初学者的题解。知识点：栈难度：一星 题解 题目抽象：要求实现一个O(1)时间复杂度的返回最小值的栈。正常情况下，栈的push，pop操作都为O(1),但是返回最小值，需要遍历整个栈，时间复杂度为O(n)，所以这里需要空间换时间的思想。 方法：使用辅助栈 首先需要一个正常栈normal,用于栈的正常操作，然后需要一个辅助栈minval，专门用于获取最小值，具体操作如下。 push操作就如图片上操作。 pop操作直接对应弹出就好了。 top操作就返回normal的栈顶 min操作就返回minval的栈顶 因此，代码如下： class Solution { public: ...

题目主要信息: 题目给定一个n∗mn*mn∗m的矩阵，需要将其按照顺时针螺旋输出 举一反三： 学习完本题的思路你可以解决类似的矩阵遍历的问题。 方法：边界模拟法（推荐使用） 思路： 这道题就是一个简单的模拟，我们想象有一个矩阵，从第一个元素开始，往右到底后再往下到底后再往左到底后再往上，结束这一圈，进入下一圈螺旋。 具体做法: step 1：首先排除特殊情况，即矩阵为空的情况。 step 2：设置矩阵的四个边界值，开始准备螺旋遍历矩阵，遍历的截止点是左右边界或者上下边界重合。 step 3：首先对最上面一排从左到右进行遍历输出，到达最右边后第一排就输出完了，上边界相应就往下一行，要判断上...

描述 这是一篇适合初级学者的题解。这里提供2种方法。知识点：树，递归难度：一星 题解 题目抽象：给定一颗二叉树，将二叉树的左右孩子进行翻转，左右孩子的子树做相同的操作。 方法一：递归版本 根据题意，如果我们知道一个根节点的左孩子指针和右孩子指针，那么再改变根节点的指向即可解决问题。也就是，需要先知道左右孩子指针，再处理根节点。显然对应遍历方式中的后序遍历。后序遍历的模板： void postOrder(TreeNode *root) { if (!root) return; postOrder(root->left); // left child postOrd...

描述 这是一篇针对初学者的题解。知识点：树，递归难度：二星 题解 题目抽象：给2棵树A，树B，判断B是否是A的子结构。子结构定义：树A和树B的根结点相等，并且树A的左子树和树B的左子树相等，树A的右子树和树B的右子树相等 方法：递归求解 第一步：根据题意可知，需要一个函数判断树A和树B是否有相同的结构。显然是个递归程序。可考察递归程序3部曲。 递归函数的功能：判断2个数是否有相同的结构，如果相同，返回true，否则返回false 递归终止条件： 如果树B为空，返回true，此时，不管树A是否为空，都为true 否则，如果树B不为空，但是树A为空，返回false，此时B还没空但A空了，显...

描述 这是一篇针对初学者的题解，共用2种方法解决。知识点：单链表，递归难度：一星 题解： 题目要求：给两个非递减单链表l1, l2，合并为一个非递减的单链表。 方法一：迭代版本求解 初始化：定义cur指向新链表的头结点操作： 如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值 否则，让l2指向下一个结点值 循环步骤1,2，直到l1或者l2为nullptr 将l1或者l2剩下的部分链接到cur的后面 技巧 一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。 代码 class Solutio...

描述 这是一篇针对初学者的题解，共用2种方法解决。知识点：单链表难度：一星 题解 方法一：构造链表 如果此类型的题出现在笔试中，如果内存要求不高，可以采用如下方法：可以先用一个vector将单链表的指针都存起来，然后再构造链表。此方法简单易懂，代码好些。###代码： class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) return nullptr; vector<ListNode*> v; while (pHead) { ...

描述 这是一篇针对初学者的题解。用2种方法解决。知识点：链表，链表的快慢指针难度：一星 题解 方法一：普通解法 很显然，求倒数第k个，可以转换成求正数第多少个呢？看个例子：假设有5个节点，序号1表示第1个节点，假设求倒数第K个，那么正数就应该是从头结点开始往后推（n-k）个，n自然代表所有节点的个数（不包含空节点），也可以说n代表指针的个数，为啥这么说呢？因为一个节点后面跟着一个指向下一节点的指针。这里n=5，所以需要从头结点往后经过n-K = 3个指针。 有了上面的过程，还需要考虑2个细节 k<=0 或者头结点最开始就为空，也就是没有节点 节点的总个数 < K 代码 cl...

描述 此题解是针对初学者的全面讲述，用三种方法来解决。知识点：数组难度：一星 题解 方法一：使用辅助数组 函数的类型为void func_name(array&)，想让我们不开辟额外数组来解决，使用in-place就地算法。但是如果空间要求不高的话，我们还是可以开挂的。也就是开辟个额外数组，接下来的做法就非常简单了，遍历一次数组，遇到奇数直接放入新开的数组中，再遍历一次数组，遇到偶数就继续放入新开的数组。最后再进行一次copy。代码如下： class Solution { public: void reOrderArray(vector<int> &arr...

题目的主要信息： 求一个浮点数的整数次方 整数有正有负 不可以使用库函数，也不需要判断大数问题 举一反三： 学习完本题的思路你可以解决如下题目： JZ83. 剪绳子（进阶版） 方法一：直接运算（推荐使用） 思路： 既然是求次方，那我们做不断累乘就可以了，重点是处理负的次方数，因为x−n=(1x)nx^{-n}=(\frac{1}{x})^nx−n=(x1​)n，因此我们将底数转换为相应分数，就可以将次方数变回正数。 if(exponent < 0){ base = 1 / base; exponent = -exponent; } 具体做法： step 1：先处理...