陈屹，毕业于北京化工大学信息与计算科学专业。05年毕业后投身于计算机软件开发行业至今。多年来曾经在联想，微软，RealNetworks担任软件工程师，积累了大量的实践经验。本人在数学，算法，计算机操作系统，网络协议，编译原理，前端开发，人工智能等领域拥有一定的知识沉淀和经验积累，目前正致力于人工智能，特别是神经网络和深度学习领域的研究和开发。

章技术面试的方法论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.7EliasGamma编码算法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.12Rabin-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.14KMP算法——字符串匹配算法的创意巅峰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年的bug293
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
0章图论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
1章贪婪算法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
2章动态规划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.2算法描述367
12.3.3代码实现368
12.3.4代码分析371

本书分十二章，从十二个方面来拆解算法面试会遇到的各种难题。前两章从技术面试的方法论和心态建设入手，让读者能高层建瓴，在心态上做到游刃有余，收放自如。接下来的三到十二章，从多个角度去详解给各类面试算法题，为大家建立一个方案数据库。这九章分别从基础数据类型，