程序员代码面试指南：IT名企算法与数据结构题目最优解

Wang Yufei， 2019-9.24

   本项目用于复现左程云老师书籍《程序员代码面试指南：IT名企算法与数据结构题目最优解》(第二版)中算法代码。作者使用Java作为书中代码的实现方式，并采用面向对象方式进行封装(风格类似于LeetCode)。本人参照作者思路(可能会有些许变动)，使用C++进行编程复现。编写的代码均可在牛客网评测系统中成功通过测试。:arrow_down:

请原谅：由于本人能力有限，部分难题(主要为4星)无法复现！谢谢

做题流程：

1. 看清题目、输入输出等；
2. 考察所有可能的情况，整理思路，将过程完整的模拟一遍，讨论细节；
3. 编写代码、注意细节实现。

测试说明：

  以Linux为例，使用g++编译源代码、gdb调试代码，并使用输入输出重定向解决测试数据问题！样例如下:

$ g++ -g test.cpp -o test   # -g表示开启调试模式, -o指示可执行文件名称:test
$ ./test < in.txt           # 重定向输入,将结果显示在命令行
# 若需要调试
$ gdb test

若程序输出较长，需要与正确输出进行逐一比较(如第一章第4题)，可以创建out.txt(保存程序输出)和ans.txt(保存正确输出)，使用Linux管道(|)、分流技术(tee)以及比较命令diff进行对比：

$ ./test < in.txt | tee out.txt   # 运行test,结果显示在命令行并保存至out.txt
$ diff out.txt ans.txt       # 比较程序输出和正确的输出,若相同则返回空!

常用数据结构的实现

  本块列举书中所涉数据结构的实现。其中部分数据结构本人尝试使用C++或python手编实现(可能并不整洁高效，为demo版)，也可直接调用C++ STL(标准模板库)实现，详见STL官方文档。

对应书中章节	数据结构	STL官方文档	实现方式(demo版)
1	栈	stack	Python
1	队列	queue	Python
1	双端队列	deque	Python
2	链表	list	C++
3	二叉树	无	C++
5	字符串	C++ String类	无
9	计算几何	无	C++(未完)

第一章：栈与队列

序号	题目	难度	完成时间	实现	标签
1	设计getMin功能的栈	1	2019-9.24	C++，Python	栈设计
2	使用两个栈模拟队列	2	2019-9.24	C++	栈设计
3	用递归函数和栈逆序一个栈	2	2019-9.26	C++	递归
4	猫狗队列	1	2019-10.3	C++	大模拟
5	用一个栈实现另一个栈的排序	1	2019-9.28	C++	栈设计
6	用栈来求解汉诺塔问题	3	2019-10.8	C++	递归
7	生成窗口最大值数组	2	2019-10.6	C++	双端队列
8a	单调栈结构--基础	2	2019-10.11	C++v1 C++v2	模拟 单调栈
8b	单调栈结构--进阶	3	2019-10.13	C++	数据组织
9	最大子矩阵	3	2019-10.15	C++	单调栈应用
10	最大值减最小值<=num的子数组数量	3	2019-10.17	C++	双端队列应用
11a	可见山峰对数--基础	2	2019-10.17	C++	数学思维
11b	可见山峰对数--进阶	4			单调栈应用

注：8b题本人C++代码超时：仅通过75%测试样例！未能找到原因。

第二章：链表

序号	题目	难度	完成时间	实现	标签
1	打印两个有序链表的公共部分	1	2019-10.17	C++	链表遍历
2	删除链表倒数第K个节点	1	2019-10.19	C++	链表遍历
3	删除链表中间节点	1	2019-10.19	C++	链表遍历
4	反转单向和双向链表	1	2019-10.19	C++	链表遍历
5	反转部分单链表	2	2019-10.21	C++	链表遍历
6a	环形链表的约瑟夫问题--基础	1	2019-10.23	C++	循环链表
6b	环形链表的约瑟夫问题--进阶	3	2019-10.25	C++	数学思维
7a	判断链表是否是回文结构--基础	1	2019-10.25	C++	栈设计
7b	判断链表是否是回文结构--进阶	2	2019-10.27	C++	跳跃指针+链表重构
8	将单链表按某值划为左边小, 中间相等,右边大形式	2	2019-10.27	C++	Partition
9	复制含随机指针节点的链表 (LeetCode 138)	2	2019-11.4	C++v1 C++v2	链表遍历+哈希表 链表遍历
10	两个单链表值相加后的链表	1	2019-10.30	C++v1 C++v2	栈设计 链表遍历
11	两个单链表相交的一系列问题
12	将单链表的每K个节点之间逆序	2	2019-11.16	C++v1 C++v2	栈设计、链表遍历
13	删除无序单链表中重复出现的节点	1	2019-11.16	C++v1 C++v2	哈希表 选择排序
14	删除单链表中指定值节点	1	2019-11.16	C++	链表遍历
15	将二叉搜索树转换为双向链表	2	2019-12.7	C++v1 ?	二叉树遍历
16	单链表的选择排序	1	2019-11.23	C++	链表遍历
17	一种怪异的链表删除方式	1	2019-11.23	C++	技巧
18	向有序的环形链表中插入新节点	1	2019-11.23	C++	循环链表
19	合并两个有序链表	1	2019-11.30	C++	链表合并
20	按照左右半区重新组合单链表	1	2019-11.30	C++	链表合并

注：13题C++v2版因算法时间复杂度高而无法在OJ上通过测试。

链表总结：

• 删除链表某一节点：需要记录该节点的前驱节点；(题目：2，6a，13)

• 反转链表片段：需要记录其中每一节点的前驱和后继节点；(题目：4，5，7b)

• 快速找到链表中间节点：记录当前节点以及对应的跳跃节点。当前节点移动一步，跳跃节点移动两步。当跳跃节点到达末尾时，当前节点就是链表的中间节点；(题目：3，7a，7b)

• 利用栈解决链表问题：可以使用栈解决链表的部分问题，如逆序、对称性、递归问题等。(题目：7a，10a，12a)

第三章：二叉树

序号	题目	难度	完成时间	实现	标签
1	递归遍历二叉树	1	2019-12.1	C++	二叉树遍历
2	打印二叉树边界节点	2	2019-12.15	C++	二叉树遍历
3	如何直观打印二叉树
4	二叉树的序列化与反序列化	1	2019-12.15	C++	序列化--二叉树遍历 反序列化--二叉树生成
5	遍历二叉树的神级方法
6	二叉树中累和为指定值的最长路径长度	2

第八章：数组与矩阵

序号	题目	难度	完成时间	实现	标签
10	未排序整数数组累加和为给定值的最大子数组长度	2	2020-3.22	C++	双指针