[时间复杂度为O（n2）的解法，不足以拿到Offer](46.md)
[时间复杂度为O（n）的解法，搞定Offer就靠它了](47.md)
- 目录
- 扉页
- 版权页
- 推荐序一
- 推荐序二
- 前言
- 第1章 面试的流程
- 1.1 面试官谈面试
- 1.2 面试的三种形式
- 1.2.1 电话面试
- 1.2.2 共享桌面远程面试
- 1.2.3 现场面试
- 1.3 面试的三个环节
- 1.3.1 行为面试环节
- 1．应聘者的项目经验
- 2．应聘者掌握的技能
- 3．回答“为什么跳槽”
- 1.3.2 技术面试环节
- 1．扎实的基础知识
- 2．高质量的代码
- 3．清晰的思路
- 4．优化效率的能力
- 5．优秀的综合能力
- 1.3.3 应聘者提问环节
- 1.4 本章小结
- 第2章 面试需要的基础知识
- 2.1 面试官谈基础知识
- 2.2 编程语言
- 2.2.1 C++
- 面试题1：赋值运算符函数
- 经典的解法，适用于初级程序员
- 考虑异常安全性的解法，高级程序员必备
- 2.2.2 C#
- 面试题2：实现Singleton模式
- 不好的解法一：只适用于单线程环境
- 不好的解法二：虽然在多线程环境中能工作但效率不高
- 可行的解法：加同步锁前后两次判断实例是否已存在
- 强烈推荐的解法一：利用静态构造函数
- 强烈推荐的解法二：实现按需创建实例
- 解法比较
- 2.3 数据结构
- 2.3.1 数组
- 面试题3：二维数组中的查找
- 2.3.2 字符串
- 面试题4：替换空格
- 时间复杂度为O（n2）的解法，不足以拿到Offer
- 时间复杂度为O（n）的解法，搞定Offer就靠它了
- 2.3.3 链表
- 面试题5：从尾到头打印链表
- 2.3.4 树
- 面试题6：重建二叉树
- 2.3.5 栈和队列
- 面试题7：用两个栈实现队列
- 2.4 算法和数据操作
- 2.4.1 查找和排序
- 面试题8：旋转数组的最小数字
- 2.4.2 递归和循环
- 面试题9：斐波那契数列
- 效率很低的解法，挑剔的面试官不会喜欢
- 面试官期待的实用解法
- 时间复杂度O（logn）但不够实用的解法
- 解法比较
- 2.4.3 位运算
- 面试题10：二进制中1的个数
- 可能引起死循环的解法
- 常规解法
- 能给面试官带来惊喜的解法
- 2.5 本章小结
- 第3章 高质量的代码
- 3.1 面试官谈代码质量
- 3.2 代码的规范性
- 3.3 代码的完整性
- 1．从3方面确保代码的完整性
- 2．3种错误处理的方法
- 面试题11：数值的整数次方
- 自以为题目简单的解法
- 全面但不够高效的解法，我们离Offer已经很近了
- 全面又高效的解法，确保我们能拿到Offer
- 面试题12：打印1到最大的n位数
- 跳进面试官陷阱
- 在字符串上模拟数字加法的解法，绕过陷阱才能拿到Offer
- 把问题转换成数字排列的解法，递归让代码更简洁
- 面试题13：在O（1）时间删除链表结点
- 面试题14：调整数组顺序使奇数位于偶数前面
- 只完成基本功能的解法，仅适用于初级程序员
- 考虑可扩展性的解法，能秒杀Offer
- 3.4 代码的鲁棒性
- 面试题15：链表中倒数第k个结点
- 面试题16：反转链表
- 面试题17：合并两个排序的链表
- 面试题18：树的子结构
- 3.5 本章小结
- 第4章 解决面试题的思路
- 4.1 面试官谈面试思路
- 4.2 画图让抽象问题形象化
- 面试题19：二叉树的镜像
- 面试题20：顺时针打印矩阵
- 4.3 举例让抽象问题具体化
- 面试题21：包含min函数的栈
- 面试题22：栈的压入、弹出序列
- 面试题23：从上往下打印二叉树
- 面试题24：二叉搜索树的后序遍历序列
- 面试题25：二叉树中和为某一值的路径
- 4.4 分解让复杂问题简单化
- 面试题26：复杂链表的复制
- 面试题27：二叉搜索树与双向链表
- 面试题28：字符串的排列
- 4.5 本章小结
- 第5章 优化时间和空间效率
- 5.1 面试官谈效率
- 5.2 时间效率
- 面试题29：数组中出现次数超过一半的数字
- 解法一：基于Partition函数的O（n）算法
- 解法二：根据数组特点找出O（n）的算法
- 解法比较
- 面试题30：最小的k个数
- 解法一：O（n）的算法，只有当我们可以修改输入的数组时可用
- 解法二：O（nlogk）的算法，特别适合处理海量数据
- 解法比较
- 面试题31：连续子数组的最大和
- 解法一：举例分析数组的规律
- 解法二：应用动态规划法
- 面试题32：从1到n整数中1出现的次数
- 不考虑时间效率的解法，靠它想拿Offer有点难
- 从数字规律着手明显提高时间效率的解法，能让面试官耳目一新
- 面试题33：把数组排成最小的数
- 5.3 时间效率与空间效率的平衡
- 面试题34：丑数
- 逐个判断每个整数是不是丑数的解法，直观但不够高效
- 创建数组保存已经找到的丑数，用空间换时间的解法
- 面试题35：第一个只出现一次的字符
- 面试题36：数组中的逆序对
- 面试题37：两个链表的第一个公共结点
- 5.4 本章小结
- 第6章 面试中的各项能力
- 6.1 面试官谈能力
- 6.2 沟通能力和学习能力
- 1．沟通能力
- 2．学习能力
- 3．善于学习、沟通的人也善于提问
- 6.3 知识迁移能力
- 面试题38：数字在排序数组中出现的次数
- 面试题39：二叉树的深度
- 需要重复遍历结点多次的解法，简单但不足以打动面试官
- 每个结点只遍历一次的解法，正是面试官喜欢的
- 面试题40：数组中只出现一次的数字
- 面试题41：和为s的两个数字VS和为s的连续正数序列
- 面试题42：翻转单词顺序VS左旋转字符串
- 6.4 抽象建模能力
- 面试题43：n个骰子的点数
- 解法一：基于递归求骰子点数，时间效率不够高
- 解法二：基于循环求骰子点数，时间性能好
- 面试题44：扑克牌的顺子
- 面试题45：圆圈中最后剩下的数字
- 经典的解法，用环形链表模拟圆圈
- 创新的解法，拿到Offer不在话下
- 6.5 发散思维能力
- 面试题46：求1＋2＋…＋n
- 解法一：利用构造函数求解
- 解法二：利用虚函数求解
- 解法三：利用函数指针求解
- 解法四：利用模板类型求解
- 面试题47：不用加减乘除做加法
- 面试题48：不能被继承的类
- 常规的解法：把构造函数设为私有函数
- 新奇的解法：利用虚拟继承，能给面试官留下很好的印象
- 6.6 本章小结
- 第7章 两个面试案例
- 7.1 案例一：（面试题49）把字符串转换成整数
- 7.2 案例二：（面试题50）树中两个结点的最低公共祖先