举一反三： 学习完本题的思路你可以解决如下题目： 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 postOrder(root->...

描述 这是一篇针对初学者的题解。知识点：树，递归难度：二星  题解 题目抽象：给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) { v.push_back(pHead); 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> &array) ...

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

题目的主要信息：  统计32位整型有符号数二进制中1的个数 因负数用补码表示，故不能用连除法  举一反三： 学习完本题的思路你可以解决如下题目： JZ64. 求1+2+3+...+n JZ65. 不用加减乘除做加法 方法一：循环按位比较法（推荐使用） 知识点：位运算 计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。 思路： 我们可以检查该数字的二进制每一位是否为1，如果遍历二进制每一位呢？可以考虑移位运算，每次移动一位就可以。至于怎么统计到1呢？我们都只知道数字1与数字相位与运算，其实只是最后一位为1...

描述：   这是一道规律题。   知识点：递归，记忆递归，动态规划，递推   难度:：一星   题解：   方法一：递推      对于这种题没有思路怎么办？   那就对n 从小到大，一步步分析：      n=1时，显然只有一种方法      n=2时，如图有2种方法     n=3，如图有3中方法        n=4,如图有5种方法。      如果到这里，还没有发现规律怎么办呢？   那我们就再分析以下，从n=3到n=4，怎么来的呢？   这里有2种情况：     直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况   然后横着的显然能添加到n-2的情况上，也就是...

题目的主要信息：  对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数 n为正整数，求青蛙跳上n级台阶的方案数  举一反三： 学习完本题的思路你可以解决如下题目： JZ69. 跳台阶 JZ10. 斐波那契数列 JZ70. 矩形覆盖 方法一：动态规划（推荐使用） 知识点：动态规划 动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。 思路： 对于最后一级台...