SwordtoOffer

经典常考必备面试算法，包括但不仅限于《剑指Offer》，《程序员面试金典》中的题目，持续更新中...

现具体包括如下问题的解法：

• 阶乘的递归和非递归解法；

• 二分查找的递归和非递归解法；

• 斐波那契数列的四种解法：经典递归法、优化递归法、循环迭代法，数组法；

• 杨辉三角的创建、存取、打印算法；

• 字符串回文判断的三种解法：递归法，循环迭代法， StringBuilder法；

• 诺比塔问题的递归解法；

• 【Offer 3】二维数组中的查找的两种解法：时间复杂度分别为O(nlgn)和O(n)；

• 【Offer 4】字符串空格置换算法；

• 【Offer 6】已知二叉树中序和前序遍历序列，重新构建二叉树；

• 【Offer 5】链表的倒序打印；

• 【Offer 7】用两个栈实现队列(一个用作插入，一个用作删除)；

• 结点为int型的二叉树及其常用算法实现；

• 【Offer 9】递归算法的数学模型(数学归纳法)、经典递归问题(斐波那契数列、变态跳台阶)、斐波那契数列的应用(跳台阶、矩阵覆盖等)；

• 【Offer 8】二分搜索算法及其应用(旋转数组的最小元素)：序列有序或部分有序；

• 【Offer 13】给定链表头结点和待删除节点，以O(1)的时间复杂度删除链表中的待删除节点：换一种思路考虑，删除当前节点就是把待删除节点的值替换成其后继节点的值，并删除其后继节点；

• 【Offer 10】位运算相关算法，核心思想：a & (a -1) 意味着将a的最右边的1变成0，其可应用于求解：一个数的二进制中1的个数问题、数m的二进制需要改变多少次才能变成数n的二进制、判断一个树是否是2的幂；判断一个数的奇偶性；

• 【Offer 15】寻找链表中的倒数第K个节点算法(双指针法)；

• 【Offer 11】幂运算算法(减少相乘次数，递归算法)；

• 【Offer 12】从1开始打印最大的n位数算法(用字符串表示大数，进位原理的掌握)；

• 【Offer 16】链表反转算法（可以见解“以O(1)的时间复杂度删除链表中的待删除节点”的算法思想，图示法(原头节点的指针指向一个初始为null的节点)、递归算法）；

• 【Offer 14】数组中奇偶数划分算法，不保证原数列奇、偶数的相对位置的解法：快排划分算法的应用，双指针法(头指针/尾指针)；保证原数列奇、偶数的相对位置的解法：双指针法(分别指向最新奇数与最老偶数)。

• 【Offer 17】合并两个排序列表：递归解法干净利落，循环解法考虑细节较多；

• 【Offer 18】树的子结构：递归算法的设计与实现；

• 【Offer 19】二叉树镜像：递归算法设计与实现，画图、找规律；

• 【Offer 20】顺时针打印矩阵(可以不是方阵)：递归算法的设计与实现，递归终止条件的考虑(只剩一行，只剩一列，只剩一个元素)；

• 【Offer 21】包含min函数的栈：利用一个额外的栈来保存存储栈中的最小值；

• 【Offer 22】栈的压入/弹出序列匹配：用一个栈来模拟给定压入和弹出序列，若最后栈变为空，则符合要求；

• 【Offer 23】从上往下打印二叉树：二叉树的广序遍历，借助于队列；

• 【Offer 24】二叉搜索树的后序遍历序列：二叉搜索树的概念(左子树 < 根结点 < 右子树)以及递归算法的设计；

• 【Offer 25】二叉树中和为某一值的路径：递归算法的设计和前序遍历的应用(两种解法)；

• 【Offer 26】复杂链表的复制：复杂问题的分解(三种解法[三种解法时间、空间复杂度不同]);

• 【Offer 27】二叉搜索树转换为双向链表：二叉搜索树的概念(左子树 < 根结点 < 右子树)以及递归算法的设计，两种解法；

• 【Offer 28】字符串全排列：递归算法的设计和前序遍历的应用(两种解法)，注意字符串中含有重复字符的情况，即是否需要去重；

• 【全排列的扩展】字符串包含字符的所有组合：分治与递归(共包括三步：1.剔除重复字符，使字符串个字符互异；2.分别获取含1...n个字符的组合(可以分为含第一个字符和不含第一个字符两种情况来考虑，分治法);3.将上一步所得到的所有组合合并)；

• 【全排列的应用领域】若题目按照一定要求摆放若干个数字(不超过9个)，那么我们可以先求出这些数字的所有排列，然后再一一判断每个排列是否满足题目要求；

• 【全排列的应用一】正方体的相对面顶点和相等：全排列的应用，列举出所有可能性，再用具体条件(满足三个等式)逐一验证，剔除不满足条件的结果；

• 【全排列的应用二】八皇后问题：全排列的应用，列举出所有可能性，再用具体条件(两皇后不在同一行、列和对角线上)逐一验证，剔除不满足条件的结果;

• 【Offer 29, 30】快排Parititon算法的应用(求序列的中位数，第K大元素，最小K个元素，超过序列一半的元素，时间复杂度O(n))；此外，在海量数据下，最小K个数的获取可以借用最大堆来实现，时间复杂度O(n·lgK),空间复杂度为O(K),不需要将所有数据一次性读入内存。

• 【Offer 31】连续子数组最大和：用一个值存储子数组和的最大值。若当前子数组和为整数，则继续累加；否则，从当前位置重新计算。

• 【Offer 32】从1到n整数中出现的次数(两种解法)：逐个计算每个数字中1的个数并最后累加；分治与递归；

• 【Offer 33】把数组排成最小数：先全排列再找最小数；指定新的排序规则，将所有数排序并依次连接起来(重点在于排序规则的定义，两种方法)。

• 【Offer 34】丑数：依次判断每个数是否为丑数(解法一)；根据当前丑数序列计算下一个丑数(解法二)。

• 【Offer 35】第一个只出现一次的字符：char[256]字符数组(哈希表)。

• 【Offer 36】数组中的逆序对：归并排序算法的应用。

• 【Offer 37】两个链表的第一个公共节点：单链表的性质与特征，双指针法。

• 【Offer 38】数字在排序数组中出现的次数：二分查找算法的变换与应用。

• 【Offer 39】二叉树的深度：递归算法的设计与应用。

• 【Offer 40】数组中只出现一次的数字(使用哈希表求解/使用异或运算求解)。

• 【Offer 41】和为s的两个数字、和为s的连续正数序列(双指针法求解)。

• 【Offer 42】翻转单词顺序、左旋转字符串等算法(双指针法求解)。

• 【Offer 43】n个骰子的点数，递归分治法(分为两堆，一堆1个，另一堆n-1个)，循环迭代法(利用n-1的情况求n的情况)。

• 【Offer 44】扑克牌的顺子，问题的建模与转化(1.排序 2.统计大小王的个数 3.统计所需大小王的个数 4.比较)。

• 【Offer 45】圆圈中最后剩下的数字，模拟游戏法(用单链表模拟环形链表)，递归法(找规律,发现递归公式)。

• 【Offer 46】求 1 + 2 + ... + n,可用构造函数法，递归法。

• 【Offer 47】不用加减乘除做加法，位运算，分为三步(1.求和(不处理进位)，2.处理进位 3.以上两步结果相加(递归))。

• 【Offer 48】不使用新的变量，交换两个整型变量的值，异或运算法(利用异或运算，异或运算满足交换律，且一个数与自身异或为0，一个数与0异或为自身),基于加减法。

• 【Offer 49】把字符串转换成整数,边界值的考虑。

• 【Offer 50】任意树中两个结点的最低公共祖先，特殊情形(二叉搜索树，拥有指向父节点的指针的树，普通树)，根据二者到根结点的路径求解。

• 【Offer 51】数组中重复的数字，简易哈希表法。

• 【Offer 52】构建乘积数组，分治法(找规律)。

• 【Offer 53】正则表达式匹配，递归算法的经典应用(穷举所有情形)。

• 【Offer 54】表示数字的字符串，(整数/小数)(E/e)(整数)。

• 【Offer 55】字符流中第一个不重复的字符，简易哈希表法。

• 【Offer 56】链表中环的入口点，快慢指针法的应用(确定链表是否有环(一个速度是一个的2倍)，并求出环的节点数N；在此基础上，求环的入口点(一个比一个快N步))。

• 【Offer 57】删除链表中的重复节点。

• 【Offer 58】二叉树的下一个节点，按照给定节点相对于根结点和父节点的位置进行查找下一个节点。

• 【Offer 59】对称二叉树，递归算法的应用。

• 【Offer 60】把二叉树打印成多行，借助队列，按行打印。

• 【Offer 61】按之字形顺序打印二叉树，解法基本与上一个题目类似。

• 【Offer 62】序列化二叉树，前序遍历的应用(所有的叶节点都用特殊符号(例如，"#")表示)。

• 【Offer 63】二叉搜索树的第K个节点，二叉搜索树的特性与递归算法的设计。

• 【Offer 64】数据流中的中位数，快排划分算法的应用，类似题目：第K大数，最小的K个数。

• 【Offer 65】滑动窗口的最大值。

• 【Offer 66】矩阵中的路径，递归算法 + 穷举思想，类似题目：Offer53(正则表达式匹配)、Offer66(矩阵中的路径)。

• 【Offer 67】机器人的运动范围，递归算法 + 穷举思想，类似题目：Offer53(正则表达式匹配)、Offer66(矩阵中的路径)。

Ps:源码中每个包对应一个问题。若项目中的源代码存在谬误，请不吝指出，在此拜谢！