# 《剑指offer》小结
# 前言
《剑指offer》这本书适合校招练习算法和数据结构，也可以作为工作后的算法与数据结构巩固练习。
另外，附上LeetCode上剑指offer（第二版）的在线刷题链接，可在阅读完练习使用：
https://leetcode-cn.com/problemset/lcof/
# 正文
这本书的前沿部分已经总结了全书的内容。一共50个算法题，并对这些算法题进行了思路讲解。
# 版本
2012年。
# 主要内容
第 1 章介绍流程。
第 2 章梳理基础知识。
第 3 章讨论写出高质量代码的 3 个要点。从规范性、完整性和鲁棒性 3 个方面提高代码的质量。
第 4 章总结解决难题的常用思路。用画图、举例和分解复杂问题 3 种思路来解决问题。
第 5 章介绍如何优化代码的时间效率和空间效率。学会优化时间效率及空间换时间的常用算法。
第 6 章总结各项能力。学习能力和沟通能力、知识迁移能力、抽象建模能力和发散思维能力。
第 7 章是两个案例。
# 详细
题4替换空格。测试用例需包含正常情况和异常情况，且考虑时间复杂度。
题5从尾到头打印链表。后进先出，使用栈。
题6重建二叉树。前序遍历第一个数字为根节点，中序遍历找到根节点位置，从而确定左右子树，再递归解决。
题8旋转数组的最小数字。二分法。
题9斐波那契数列。递归➕循环。
题11数值的整数次方。需考虑底数为0而指数为负数的处理。
题12打印1到最大的n位数。大数问题，用字符串模拟加法并打印。
题13在O(1)时间删除链表节点。创新；用下一个节点的内容对比被删除的节点，然后把下一个节点删除。
题14调整属于顺序使偶数位于奇数之前。双指针。
题15链表中倒数第k个节点。双指针遍历。
题17合并2个排序的链表。递归。
题18树的子结构。递归。
题19二叉树的镜像。先序遍历树，递归。
题21包含min函数的栈。借用辅助栈保存最小元素。
题22栈的压入、弹出序列。举例分析，辅助栈。
题23从上往下打印二叉树。队列。
题24二叉搜索树的后序遍历序列。找出后序遍历的规律。
题25二叉树中和为某一值的路径。栈。
题26复杂链表的复制。用O(n)的空间消耗把时间复杂度由O(N^2)降低到O(n)。
题28字符串的排列。递归。
题30最小的k个数。最大堆。
题31连续子数组的最大和。动态规划。
题35第一个只出现一次的字符。哈希表。
题37两个链表的第一个公共节点。辅助栈。
题38数字在排序数组中出现的次数。二分查找、递归。
题39二叉树的深度。递归。
题46求1+2+……+n。发散思维。