Python程序员面试宝典 剑指offer

《Python程序员面试宝典》是一本介绍Python程序员面试的图书宝典。这里，不仅介绍了程序员算法面试中的“万能公式”，而且通过具体的实例从多角度剖析各类算法面试题，为读者建立了一个完整的算法面试的方案数据库，让读者快速理解全书内容、做到胸有成竹应对面试的同时，也为未来的职业发展铺平道路。

《Python程序员面试宝典》共分12章，其中前两章首先引入一道面试题，并进行情景分析和解题思路，然后从技术面试的方法论和心态建设入手，介绍应对面试的基本方法和思路。后10章分别从基础数据类型、数组和字符串、链表、堆栈、二叉树、堆、二分查找法、图论、贪婪算法和动态规划等多个方面去详解各类面试题，分析算法面试中常见的各类技术问题。通过本书的学习，希望读者能够在大脑中建立起自己的解决方案数据库，面试时可以迅速地搜索出相应的解决方案，从而提高解题效率和增加通过面试的几率。

《Python程序员面试宝典》书中所有代码都采用python语言开发。其语法结构简单，易于掌握，非常适合于高校计算机相关专业毕业生求职面试前的笔试参考用书，也可以作为计算机相关专业学生学习数据结构和算法的辅助教材，所有致力于程序员职业的读者均可选择本书学习。

陈屹，海南康康饼网络科技有限公司CEO，15年开发面试经验，曾在微软、联想、realplayer等公司承担客户端和服务器开发工作。在算法设计、高并发、高性能服务器、复杂系统设计、人工智能等多个领域拥有深厚积累，其设计的编译原理、操作系统、网络协议系统等多门原厂教学视频在网易云课堂收到大量好评。

精选Facebook、Google、Microsoft和BAT等大型企业的Python算法面试题，并进行详细的剖析、分类归纳，提炼出算法面试的各种应对技巧，是一本Python程序员算法面试的图书宝典。

全面介绍Python程序员面试笔试技巧和方法，教你如何以“不变应万变”。

√ 两万多行代码，100多个知识点，全面覆盖Python程序员各类面试题型。

√ 15年开发经验、实战技巧总结，站在“巨人”的肩膀上，让学习走捷径。

√ 采用抽丝剥茧式分析，深入解释计算机科学的底层逻辑——算法及原理。

√ 包括60多个算法题目，针对性强，拿来就用。通过实战学习解题思路。

第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