第1章 技术面试的方法论 1
1.1一道亚马逊面试题的情景分析 1
1.1.1暴力枚举法 2
1.1.2分而治之法 4
1.1.3最优解法 6
1.1.4解题流程总结 7
1.2面试的流程，心态建设，相关准备 8
1.2.1面试前流程 8
1.2.2简历的制作 10
1.2.3有效的面试策略 11
1.2.4编码实现 12
1.2.5面试过程中的交流要点 13
1.3知己知彼，百战不殆——从面试官角度看面试 14
1.3.1如何进行一场良好的面试 15
1.3.2面试官如何主导面试流程 17
1.3.3面试官如何评估候选人 17
第2章 算法面试的技术路线图 19
2.1算法面试中的数据结构 19
2.1.1基础数据类型 20
2.1.2数组与字符串 21
2.1.3链表 21
2.1.4堆栈 22
2.1.5二叉树 22
2.1.6堆 23
2.1.7哈希表 23
2.2算法的设计模式 24
2.2.1排序 24
2.2.2递归 26
2.2.3分而治之 27
2.2.4动态规划 29
2.2.5贪婪算法 29
2.2.6逐步改进 29
2.2.7排除法 30
2.3抽象分析模式 30
2.3.1样例覆盖 31
2.3.2小量数据推导 31
2.3.3简单方案的逐步改进 32
2.3.4问题还原 33
2.3.5图论模拟 34
第3章 基础数据类型的算法分析 35
3.1基础数据类型中二进制位的操作算法 35
3.1.1整型变量值互换 35
3.1.2常用的二进制位操作 36
3.1.3解析一道二进制操作相关算法面试题 37
3.1.4总结 40
3.2用二进制操作求解集合所有子集 40
3.2.1题目描述 40
3.2.2算法描述 40
3.2.3代码实现 41
3.2.4算法分析 43
3.3使用二进制求解最大公约数 43
3.3.1题目描述 43
3.3.2算法描述 45
3.3.3代码实现 47
3.3.4算法分析 49
3.4素数判定 50
3.4.1题目描述 50
3.4.2算法描述 50
3.4.3代码实现 52
3.4.4算法分析 53
3.5判断矩形交集 54
3.5.1题目描述 54
3.5.2算法描述 54
3.5.3代码实现 56
3.6数字与字符串相互转化，简单题目的隐藏陷阱 58
3.6.1题目描述 58
3.6.2算法描述 58
3.6.3代码实现 59
3.6.4算法分析 60
3.7 Elias Gamma编码算法 62
3.7.1题目描述 62
3.7.2算法描述 63
3.7.3代码实现 63
3.7.4算法分析 66
3.8整型的二进制乘法 67
3.8.1题目描述 67
3.8.2算法描述 67
3.8.3代码实现 69
3.8.4算法分析 73
第4章 数组和字符串 74
4.1数组的定位排序 74
4.1.1题目描述 74
4.1.2算法描述 75
4.1.3代码实现 76
4.1.4算法分析 78
4.2在整型数组中构建元素之和能整除数组长度的子集 78
4.2.1题目描述 78
4.2.2算法描述 78
4.2.3代码实现 79
4.2.4算法分析 82
4.3计算等价类 82
4.3.1题目描述 82
4.3.2算法描述 83
4.3.3代码实现 85
4.3.4代码分析 86
4.4大型整数相乘 87
4.4.1题目描述 87
4.4.2算法描述 87
4.4.3代码实现 88
4.4.4代码分析 91
4.5数组的序列变换 92
4.5.1题目描述 92
4.5.2算法描述 92
4.5.3代码实现 94
4.5.4代码分析 96
4.6字符串的旋转 96
4.6.1题目描述 96
4.6.2算法描述 96
4.6.3代码实现 97
4.6.4代码分析 99
4.7二维数组的启发式搜索算法 99
4.7.1题目描述 99
4.7.2算法描述 99
4.7.3代码实现 100
4.7.4代码分析 101
4.8二维数组的旋转遍历 102
4.8.1题目描述 102
4.8.2算法描述 102
4.8.3代码实现 104
4.8.4代码分析 105
4.9矩阵的90°旋转 105
4.9.1题目描述 106
4.9.2算法描述 106
4.9.3代码实现 107
4.9.4代码分析 109
4.10游程编码 109
4.10.1题目描述 110
4.10.2算法描述 110
4.10.3代码实现 110
4.10.4代码分析 112
4.11字符串中单词的逆转 113
4.11.1题目描述 113
4.11.2算法描述 113
4.11.3代码实现 114
4.11.4代码分析 115
4.12 Rabin-Karp字符串匹配算法 115
4.12.1题目描述 115
4.12.2算法描述 115
4.12.3代码实现 118
4.12.4代码分析 120
4.13用有限状态自动机匹配字符串 120
4.13.1题目描述 120
4.13.2算法描述 121
4.13.3代码实现 124
4.13.4代码分析 127
4.14 KMP算法——字符串匹配算法的创意巅峰 127
4.14.1题目描述 127
4.14.2算法描述 127
4.14.3代码实现 129
4.14.4代码分析 131
4.15 正则表达式引擎的设计和实施 132
4.15.1题目描述 132
4.15.2算法描述 133
4.15.3代码实现 138
4.15.4代码分析 178
第5章 队列和链表 179
5.1递归式实现链表快速倒转 179
5.1.1题目描述 179
5.1.2算法描述 180
5.1.3代码实现 181
5.1.4代码分析 184
5.2链表成环检测 184
5.2.1题目描述 185
5.2.2算法描述 185
5.2.3代码实现 186
5.2.4代码分析 189
5.3在O（1）时间内删除单链表非末尾节点 190
5.3.1题目描述 190
5.3.2算法描述 190
5.3.3代码实现 191
5.3.4代码分析 192
5.4获取重合列表的第一个相交节点 192
5.4.1题目描述 193
5.4.2算法描述 193
5.4.3代码实现 194
5.4.4代码分析 196
5.5单向链表的奇偶排序 196
5.5.1题目描述 196
5.5.2算法描述 196
5.5.3代码实现 198
5.5.4代码分析 199
5.6双指针单向链表的自我复制 199
5.6.1题目描述 200
5.6.2算法描述 200
5.6.3代码实现 202
5.6.4代码分析 206
5.7利用链表层级打印二叉树 206
5.7.1题目描述 206
5.7.2算法描述 206
5.7.3代码实现 207
5.7.4代码分析 209
第6章 堆栈和队列 210
6.1利用堆栈计算逆向波兰表达式 210
6.1.1题目描述 210
6.1.2算法描述 210
6.1.3代码实现 211
6.1.4代码分析 213
6.2计算堆栈当前元素最大值 213
6.2.1题目描述 213
6.2.2算法描述 213
6.2.3代码实现 214
6.2.4代码分析 216
6.3使用堆栈判断括号匹配 216
6.3.1题目描述 216
6.3.2算法描述 216
6.3.3代码实现 217
6.3.4代码分析 218
6.4使用堆栈解决汉诺塔问题 218
6.4.1题目描述 218
6.4.2算法描述 219
6.4.3代码实现 219
6.4.4代码分析 222
6.5堆栈元素的在线排序 222
6.5.1题目描述 223
6.5.2算法描述 223
6.5.3代码实现 224
6.5.4代码分析 225
6.6计算滑动窗口内的最大网络流量 225
6.6.1题目描述 226
6.6.2算法描述 226
6.6.3代码实现 231
6.6.4代码分析 234
6.7使用堆栈模拟队列 234
6.7.1题目描述 235
6.7.2算法描述 235
6.7.3代码实现 235
6.7.4代码分析 236
第7章 二叉树 238
7.1二叉树的平衡性检测 238
7.1.1题目描述 239
7.1.2算法描述 239
7.1.3代码实现 239
7.1.4代码分析 242
7.2镜像二叉树的检测 242
7.2.1题目描述 243
7.2.2算法描述 243
7.2.3代码实现 244
7.2.4代码分析 246
7.3二叉树的Morris遍历法 247
7.3.1题目描述 247
7.3.2算法描述 247
7.3.3代码实现 250
7.3.4代码分析 251
7.4使用前序遍历和中序遍历重构二叉树 252
7.4.1题目描述 252
7.4.2算法描述 253
7.4.3代码实现 254
7.4.4代码分析 256
7.5逆时针打印二叉树外围边缘 256
7.5.1题目描述 256
7.5.2算法描述 257
7.5.3代码实现 257
7.5.4代码分析 259
7.6寻找两个二叉树节点的最近共同祖先 259
7.6.1题目描述 260
7.6.2算法描述 260
7.6.3代码实现 260
7.6.4代码分析 264
7.7设计搜索输入框的输入提示功能 264
7.7.1题目描述 264
7.7.2算法描述 264
7.7.3代码实现 265
7.7.4代码分析 269
第8章 堆 270
8.1使用堆排序实现系统Timer机制 270
8.1.1题目描述 270
8.1.2算法描述 270
8.1.3代码实现 273
8.1.4代码分析 279
8.2波浪形数组的快速排序法 279
8.2.1题目描述 279
8.2.2算法描述 280
8.2.3代码实现 281
8.2.4代码分析 287
8.3快速获取数组中点的相邻区域点 287
8.3.1题目描述 287
8.3.2算法描述 287
8.3.3代码实现 289
8.3.4代码分析 292
第9章 二分查找法 293
9.1隐藏在《编程珠玑》中20年的bug 293
9.1.1题目描述 294
9.1.2算法描述 294
9.1.3代码实现 295
9.1.4代码分析 297
9.2在lg（k）时间内查找两个排序数组合并后第k小元素 297
9.2.1题目描述 297
9.2.2算法描述 297
9.2.3代码实现 299
9.2.4代码分析 301
9.3二分查找法寻求数组截断点 302
9.3.1题目描述 302
9.3.2算法描述 302
9.3.3代码实现 304
9.3.4代码分析 306
9.4在双升序数组中快速查找给定值 306
9.4.1题目描述 307
9.4.2算法描述 307
9.4.3代码实现 307
9.4.4代码分析 309
第10章 图论 310
10.1地图着色问题 310
10.1.1问题描述 310
10.1.2算法描述 310
10.1.3代码实现 311
10.1.4代码分析 315
10.2迪杰斯特拉最短路径算法 316
10.2.1题目描述 316
10.2.2算法描述 316
10.2.3代码实现 319
10.2.4代码分析 326
10.3使用深度优先搜索解决容器倒水问题 327
10.3.1问题描述 327
10.3.2算法描述 327
10.3.3代码实现 329
10.3.4代码分析 333
第11章 贪婪算法 335
11.1最小生成树 335
11.1.1题目描述 335
11.1.2算法描述 336
11.1.3代码实现 339
11.1.4代码分析 344
11.2霍夫曼编码 344
11.2.1题目描述 345
11.2.2算法描述 345
11.2.3代码实现 347
11.2.4代码分析 349
11.3离散点集的最大覆盖率问题 350
11.3.1题目描述 350
11.3.2算法描述 351
11.3.3代码实现 352
11.3.4代码分析 355
第12章 动态规划 356
12.1钢管最优切割方案 356
12.1.1问题描述 357
12.1.2算法描述 357
12.1.3代码实现 358
12.1.4代码分析 360
12.2查找最大共同子串 361
12.2.1问题描述 362
12.2.2算法描述 362
12.2.3代码实现 364
12.2.4代码分析 366
12.3将最大共同子串算法的空间复杂度从O（n2）改进为O（n） 366
12.3.1问题描述 367
12.3.2算法描述 367
12.3.3代码实现 368
12.3.4代码分析 371