程序员代码面试指南:IT名企算法与数据结构题目最优解
Wang Yufei, 2019-9.24
本项目用于复现左程云老师书籍《程序员代码面试指南:IT名企算法与数据结构题目最优解》(第二版)中算法代码。作者使用Java作为书中代码的实现方式,并采用面向对象方式进行封装(风格类似于LeetCode)。本人参照作者思路(可能会有些许变动),使用C++进行编程复现。编写的代码均可在牛客网评测系统中成功通过测试。
请原谅:由于本人能力有限,部分难题(主要为4星)无法复现!谢谢
做题流程:
- 看清题目、输入输出等;
- 考察所有可能的情况,整理思路,将过程完整的模拟一遍,讨论细节;
- 编写代码、注意细节实现。
测试说明:
以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++ | 双指针 |