jian_zhi_offer

剑指虐我千百遍，我待剑指如初恋 第XXX次和剑指XXX，我真的是XXX了

题目列表

第2章：面试需要的基本知识

编程语言 C++/C/Java

1. 赋值运算符函数前往
2. 实现Singleton模式（设计模式，参考）前往

数据结构

3. 二维数组中的查找（数组）前往
4. 替换空格（不使用自带函数）（字符串）前往
5. 从尾到头打印链表（栈、递归）（链表）前往
6. 重建二叉树（前序、中序、后序遍历特点、递归）（树）前往
7. 用两个栈实现对列（入队和出队）（栈和对列）前往

算法和数据操作

8. 旋转数组的最小数字（二分查找变种）（查找和排序）前往
9. 斐波那契数列（递归和循环，递归解法的弊端）前往
10. 二进制中1的个数（位运算，减1求与的次数）前往

第3章：高质量的代码

代码的完整性

11. 数值的整数次方（指数为负、数值为0等边界情况，递归解法）前往
12. 打印1到最大的n位数（数组模拟、全排列、递归）前往
13. 在O(1)时间删除链表节点（链表空、删除节点为头节点、尾节点等）前往
14. 调整数组顺序使奇数位于偶数前面（两个指针）前往

代码的鲁棒性

15. 链表中倒数第k个结点（链表空，k小于1，k大于链表长度，两个指针）前往
16. 反转链表（链表空、只有一个节点）前往
17. 合并两个排序的链表（某个链表为空）前往
18. 树的子结构（两步：根节点是否相等，是否是子结构）前往

第4章：解决面试题的思路

面试官谈面试思路

19. 二叉树的镜像（递归，交换左右节点）前往

画图让抽象问题形象化

20. 顺时针打印数组（循环条件，每圈打印数组的边界条件）前往

举例让抽象问题具体化

21. 包含min函数的栈（利用辅助栈保存最小值）前往
22. 栈的压入、弹出序列（熟悉入栈和出栈的过程）前往
23. 从上往下打印二叉树（对列，先进先出）前往
24. 二叉搜索树的后序遍历序列（二叉搜索树：左子树比根节点小，右子树比根节点大。后序遍历数组的特点）前往
25. 二叉树中和为某一值的路径（递归、栈、举例模拟计算过程）前往

分解让复杂问题简单化（题目较为复杂，需要多加理解练习）

26. 复杂链表的复制（三步：复制节点的next，复制节点的sibling，拆分链表）前往
27. 二叉搜索树和双向链表（中序遍历、递归）前往
28. 字符串的排列（全排列、递归、回溯）前往

第5章：优化时间和空间效率（题目较为复杂，需要多加理解练习）

时间效率

29. 数组中出现次数超过一半的数字（快排能改变数组O(n)、快速解法O(n)）前往
30. 最小的k个数（快排能改变数组O(n)、最大堆和额外k空间O(nlogk)）前往
31. 连续子数组的最大和（举例分析数组规律、动态规划）前往
32. 从1到n整数中1出现的次数（最高位为1、其余位1、递归）前往
33. 把数组排成最小的数（排序规则、快排、比较器）前往

时间效率与空间效率的平衡

34. 丑数（数组保存已找到的数组、四个指针）前往
35. 第一个只出现一次的字符（TreeMap保存字符及其出现次数、保证顺序）前往
36. 数组中的逆序对（归并排序、辅助数组保存排序元素）前往
37. 两个链表的第一个公共节点（辅助栈、先求长度差然后同时走直到第一次相遇）前往

第6章：面试中的各项技能（题目较为复杂，需要多加理解练习）

知识迁移能力

38. 数字在排序数组中出现的次数（二分查找得到第一个k的下标和最后一个k的下标）前往
39. 二叉树的深度+是否为平衡二叉树（递归遍历）前往
40. 数组中只出现一次的数字（异或、根据结果位1分成两个数组再求异或）前往
41. 和为s的两个数字+和为s的连续正数序列（两个指针、首尾、首首）前往
42. 翻转单词顺序VS左旋转字符串（整体旋转、部分旋转）前往

抽象建模能力

43. n个骰子的点数（递归求解每种情况的次数）前往
44. 扑克牌的顺子（判断大小王的数量是否不小于需要补上大小王的数量） 前往
45. 圆圈中最后剩下的数字（链表每次删除第m个元素得到最后一个元素、数学推导） 前往

发散思维能力

46. 求1+2+...+n（函数递归调用） 前往
47. 不用加减乘除做加法（位运算、异或和与运算加循环、异或实现无进位加+与运算实现求进位+再循环求两个结果的和） 前往
48. 不能被继承的类（C相关，省略） 前往

第7章：两个面试案例

49. 把字符串转换为整数（考虑字符串中存在非法字符、第一个字符为'+'或'-'或数字的情况等） 前往
50. 树中两个结点的最低公共祖先（四种场景：a. 二叉搜索树->二分搜索法; b. 普通树+指向父节点指针->两个链表第一个相交的节点; c. 普通树->递归左右子树判断 d. 普通树->辅助空间、两个链表保存根节点到指定节点的路径，最后一个相同的节点就是最低公共祖先节点） 前往

附加1：排序算法/查找算法（chapter_sort）

基本算法（时间复杂度为 n^2）

1. 冒泡排序（稳定；时间复杂度：最好为 O(n)，最差为 O(n^2)，平均为 O(n^2)；空间复杂度：O(1)，选择排序的一种）前往
2. 选择排序（不稳定；时间复杂度：最好为 O(n^2)，最差为 O(n^2)，平均为 O(n^2)；空间复杂度：O(1)）前往
3. 插入排序（稳定；时间复杂度：最好为 O(n)，最差为 O(n^2)，平均为 O(n^2)；空间复杂度：O(1)）前往

快速算法（时间复杂度为 nlogn）

4. 快速排序（不稳定；时间复杂度：最好为 O(nlogn)，最差为 O(n^2)，平均为 O(nlogn)；空间复杂度：O(logn)，基于冒泡排序 + 二分 + 递归分治）前往
5. 堆排序（不稳定；时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)；空间复杂度：O(1)，基于选择排序）前往
6. 希尔排序（不稳定；时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)；空间复杂度：O(1)，基于插入排序）前往
7. 归并排序（稳定；时间复杂度：最好为 O(nlogn)，最差为 O(nlogn)，平均为 O(nlogn)；空间复杂度：O(n)，基于递归分治）前往

高级算法（时间复杂度为 n）

8. 计数排序（稳定；时间复杂度：最好为 O(n+k)，最差为 O(n+k)，平均为 O(n+k)；空间复杂度：O(n+k)）前往
9. 桶排序（稳定；时间复杂度：最好为 O(n)，最差为 O(nlogn)，平均为 O(n+c)；空间复杂度：O(n+m)）前往
10. 基数排序（稳定；时间复杂度：最好为 O(d(n+r))，最差为 O(d(n+r))，平均为 O(d(n+r))；空间复杂度：O(r)）前往

附加2：数据结构相关算法题（chapter_ds）

1. 最长公共子序列（动态规划）前往
2. 最长公共子串（动态规划）前往
3. 链表相关的考题：单链表反转，是否有环等等 前往

附加3：面试中常问/手写的算法（chapter_freq）

1. 求一个数的平方根（二分法 t=c/t）前往
2. 微信抢红包算法（红包类的设计）前往
3. 数组分割（动态规划、S(k, i)表示前k个元素中任意i个元素的和的集合）前往
4. 0-1背包问题（动态规划）前往
5. 基于Socket的TCP通信 前往
6. 基于wait/notify的生产者消费者模式 前往
7. 基于await()/signal()的生产者消费者模式 前往
8. 基于阻塞队列的生产者消费者模式 前往
9. 1-n的数组中和等于m的所有情况（背包问题） 前往
10. 整数反转（考虑整数溢出，模十取余） 前往
11. 快速幂模算法（蒙格马利快速幂模算法） 前往

附加4：设计模式（chapter_dp）

创建型

构造型

装饰器模式：允许向一个现有的对象添加新的功能，同时又不改变其结构 前往 代理模式 前往

行为型