描述 这是一篇针对初学者的题解，共用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. 矩形覆盖 方法一：动态规划（推荐使用） 知识点：动态规划 动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。 思路： 对于最后一级台...

#描述 此题和斐波拉契数列做法一样。也将用三个方法来解决，从入门到会做。 考察知识：递归，记忆化搜索，动态规划和动态规划的空间优化。 难度：一星 #题解 ###方法一：递归 题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。所以f[n] = f[n-1] + f[n-2]. 那么初始条件了，f[0] = f[1] = 1。 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1，目标求f[n] 看到公式很亲切，代码秒秒钟写完。 class S...

#描述 此题是非常经典的入门题了。我记得第一次遇到此题是在课堂上，老师拿来讲“递归”的（哈哈哈）。同样的类型的题还有兔子繁殖的问题。大同小异。此题将用三个方法来解决，从入门到会做。 考察知识：递归，记忆化搜索，动态规划和动态规划的空间优化。 难度：一星 #题解 ###方法一：递归 题目分析，斐波那契数列公式为：f[n] = f[n-1] + f[n-2], 初始值f[0]=0, f[1]=1，目标求f[n] 看到公式很亲切，代码秒秒钟写完。 class Solution { public: int Fibonacci(int n) { if (n<=2) return 1; return...

描述 这是一道对二分查找算法灵活运用的一道题目。二分查找算法不限于运用在有序数组上。如果能够明确二分之后，答案存在于二分的某一侧，就可以使用二分。本题就是如此。难度：二星考察知识：数组，二分查找  题解 方法一：暴力方法： 直接遍历一遍数组，即可找到最小值。但是本题的附加条件就没有用上。肯定不是面试官所期望的答案。 方法二：二分查找 这种二分查找难就难在，arr[mid]跟谁比.我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。一次比较为 arr[mid]跟谁比的问题。一般的比较原则有：  如果有目标值target，那么直接让arr[mid] 和 target 比较即可。 如果...

描述  这是一道对栈和队列之间灵活转化的题目。难度：一星考察知识：队列，栈  题解 方法：模拟 如果我知道队列是FIFO，栈是FILO，但是这道题我还是不知道怎么写怎么办？对于这种感觉不难，但是又不会写的，方法就是模拟。比如有如下操作：(pop操作确保栈中有元素） push(1);push(2);pop(3);push(4);根据队列的特性，只能pop(1),pop(2),pop之后的结果  上述是队列的操作。当push的时候，我们必须要用一个stack来存，假设用stack1来存。那么push操作解决了。那么pop操作怎么办呢？如果pop(1)，但是此时在stack1的栈底，如果要pop，必...

描述 这道题综合考察了对二叉树的前序，中序遍历算法的理解，和根据数组建立二叉树的代码考察以及对递归代码的理解与运用。题目难度：三星考察知识：树，递归  题解 本题解是初学算法的对象，一步步从不会到会的详细讲解。 方法：递归算法 前置知识： 二叉树的前序遍历：根左右二叉树的中序遍历：左根右二叉树的的后序遍历：左右根 建树的相关步骤： // 树结点 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) { } }; // ...

题目的主要信息：  输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值 返回值保存在数组中  举一反三： 学习完本题的思路你可以解决如下题目： JZ24. 反转链表 方法一：递归（推荐使用） 知识点：递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。 思路： 我们都知道链表无法逆序访问，那肯定无法直接遍历链表得到从尾到头的逆序结果。但是我们都知道递归是到达底层后才会往上回溯，因此我们可以考虑递归遍历链...