剑指offer题目思路总结
包括题目主干和思路提示，题目有思路是最重要的。
第七章
面试题68： 树中两个节点的最低公共祖先
思路一： 搜索二叉树
第一个大小介于两个节点之间的点即为所求；
思路二： 不是搜索二叉树，但有指向父节点的指针
从两个节点出发到根节点组成两个链表，求第一个公共节点；
思路三： 普通二叉树
常规思路： 当前节点树包含两个节点 && 其子树都不能同时包含两个节点
存在问题： 重复遍历
创新思维： 从根节点出发，记录到两个节点的路径，形成1个链表，最后一个公共的点。（生成链表之后逆序选择判断该节点树是否包含另一个节点）
第六章
面试题53： 在排序数组中查找数字
题目1： 数字在排序数组中出现的次数
有序， 二分查找查找这个数的第一个索引，和最后一个索引。
但是，直接count， 或者index，rindex就ok了
题目二： 0~n-1中缺少的数字
二分查找，下标和数值不等的位置。
题目三： 数组中下标和数值相等的元素
二分，如果下标 > 数值； 如果下标 < 数组 左边一半；
面试题54： 二叉搜索树的第K大节点
中序变量
面试题55： 二叉树的深度
题目1： 二叉树的深度
deepth(node.left) > deepth(node.right) ? deepth(node.left) + 1 : deepth(node.right) + 1
题目2： 平衡二叉树
思路： 左右子树相差不超过1
| if | deepth(node.left) - deepth(node.right) | return false |
else is_blance(node.left) && is_blance(node.right)
代码
优化： 记录每个节点的深度
面试题56： 数组中数字出现的次数
题目一： 数组中数字出现的次数（两个数字）
假如不重复的两个数是a和b，那其他数字以后之后是0，结果就是a ^ b的结果；
那么根据结果的二进制中一位1， 说明这个位置a或b只有一个为1， 然后以这一位二进制为不为1分成两组。
再异或就行了。
题目二： 数组中唯一一只出现一次的数字（三次）
将所有数字的二进制每一位相加，看能否被3整除
面试57：和为s的数字
题目一： 和为s的两个数字
两端res = left + right
res > s right– res < s left++
题目2： 和为s的连续整数序列
small[i] big[j] i,j初始值是0和1，就是两个游标都是从小开始 sum = 下标之间的累计和
sum > s i++
sum < s j++
面试58： 反转字符串
题目一： 反转单词顺序
str.split.reverse
算法： 先整体反转，再单词反转
题目二：左旋转字符串
这个就相当于第index是空格去切分，然后然上述的算法再
str[index..-1] + str[0…index]
面试题59： 队列的最大值(代码)
题目1： 队列的最大值
算法：维护一个最大值队列
和维护的一个最大值栈类似
#####：题目2： 队列的最大值（代码）
面试题60： n个骰子的点数（代码）
面试题61： 扑克牌中的顺子
简单
面试题62： 圆圈中最后剩下的数字
思路： 环形链表，循环
递归公式： f(n, m) = (f(n-1, m) + m) % n
面试题63： 股票的最大利润
这个题很简单，diff(i) 卖出价是第i天时的价格利润最大，找i-1天前的最小买入值；
扩展： 不止一天 (代码)
面试题64： 求1 + 2 + 3 + … + n (代码)
面试题65： 不用加减乘除做加法（代码）
面试题66： 构建乘积数组
第五章
面试题39： 数组中出现次数超过一半的数组
思路一： 排序中位数
思路二： 不必完全排序，快排 + 查找 查找的是中位数（判断下标）
思路三： 两个辅助变量a，b a是数组中的数字，b是数字出现的次数
面试题40： 最小的k个数
思路一： 排序 (按照上述题目的思路，快排，判断下标)
思路二： 红黑树 (以后可以代码)
面试题41： 数据流中的中位数（代码）
维护一个最大堆和最小堆，二者个数相差不超过1（偶数个插入最小堆，奇数个插入最大堆）
如果插入最小堆的数比最大堆的max小，就交换之后插入。
维护两个堆。
面试题42: 连续子数组的最大和（代码）
面试题43： 1~n整数中1出现的次数
暴力枚举
算法没懂，排列组合的计算， 以后可以代码。
面试题44： 数字序列中某一位的数字
简单
面试题45： 把数组排成最小的数（代码）
思路一： 全排列排序
思路二： 我记得之前做过一个最大值 largest_number
面试题46： 把数字翻译成字符串（代码）
面试题47： 礼物的最大价值（代码）
面试题48： 最长不含重复字符的子串（代码）
第四章
面试题27： 二叉树镜像(代码)
思路：
面试题28： 对称的二叉树（代码)
前序遍历 和 右子树的前序遍历一致
面试题29： 顺时针打印阵
思路：
按照左上角坐标打印（横，竖，横，竖）
考虑奇数圈和偶数圈；
最后一圈各种情况
面试题30： 包含min函数的栈
思路： 维护一下最小值栈
面试题31： 栈的压入、弹出序列
验证一个压入顺序有没有可能出现某一个弹出序列。
面试题32：从上到下打印二叉树
题目1： 不分行层次打印二叉树
层次遍历
题目2： 分行分层打印二叉树
两个辅助变量， a: 当前层数还没有打印的节点数； b:下一层节点的数目
题目3： 之字形打印二叉树
思路：奇数层和偶数层用两个栈存储；
面试题33： 二叉搜索树的后序遍历序列（代码）
面试题34： 二叉树中和为某一值的路径（代码）
面试题35： 复杂链表的复制（代码）
面试题36： 二叉搜索树和双向链表（代码）
思路： 分成三部分，根节点，左子树，右子树
因为有序所以中序遍历，当前节点node， node的左、右节点增加一个指向node的指针，（对应的分别是前一个节点，后一个节点）
递归思路解决。
面试题37： 序列化二叉树（代码）
面试题38： 字符串的排列（代码）
拓展：
1、字符串的组合
2、正方体
3、8皇后
第三章
面试题16： 数值的整数次方
主要是合法性的判断， 0做分母的负数次幂等
然后可以递归去提高效率
a^n =
a^n/2 * a^n/2 n为偶数
a^n-1/2 * a^n-1/2*a n为奇数
加分细节：
和1与运算可以判断奇偶
移位操作
面试题17： 打印从1到最大n位数（代码）
数字排列问题
面试题18： 删除链表节点
题目1： 在O(1)时间内删除链表节点
思路： 复制后一个节点，然后删除后一个节点
然后若是尾节点，只能遍历
o(1) * (n-1) + o(n) / n = O(1)
题目2： 删除链表中重复的节点
保存前置节点和后置节点，删除中间重复部分
面试题19： 正则表达式匹配（代码）
面试题20 表示数值的字符串（代码）
面试题21 调整数组顺序是的奇数位于偶数前面
思路一： 前后指针
拓展：可以把奇数偶数规则给提取出来，让这种交换可以适用于多种规则。
面试题22： 链表中倒数第k个节点
拓展： 中间节点， 一个指针走两步，一个指针走一步
面试题23： 链表中环的入口节点
1、包不包括环？ 快慢指针
2、环的入口？ 找到环中节点的个数n，然后让一个指针先走n步
3、环中节点的个数？ 两个指针相遇一定在环里，然后记住该点，走一圈。
面试题24： 反转链表
面试题25： 合并两个有序链表（代码）
递归的思路很棒
面试题26: 树的子结构
完全可以前序遍历，包括nil，然后判断是不是子数组。
递归（代码）
第二章
面试题3：数组中重复的数字
题目一： 找出数组中重复的数字
题目二： 不修改数组找出重复的数字。
二分法，1~n的中间数字
面试题4： 二维数组中的查找
面试题5： 替换空格
逆序替换
面试题6： 从尾到头打印链表（代码）
递归
面试题7： 重建二叉树
面试题8： 二叉树的下一个节点（代码）
面试题9： 用两个栈实现队列
面试题10： 斐波那契数列
面试题11： 旋转数组的最小数字
面试题12： 矩阵中的路径（代码）
面试题13： 机器人的运动范围（代码）
面试题14： 剪绳子（代码）
面试题15： 二进制中1的个数（代码）
