左程云《程序员代码面试指南》第二版编程题的Python语言实现
牛客网OJ：程序员代码面试指南
LeetCode：https://leetcode-cn.com/problemset/all/
1、故下面除特殊说明，否则OJ链接均默认为LeetCode对应题目链接。因为牛客网OJ在链表、二叉树等相关题目均把题目数据以链表数据结构给出，略掉了二叉树、链表等结构的相关信息。这样不能准确评估是否已经正确解出题目。
2、✔为已在oj上测试通过的题解.
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 设计一个有getMin功能的栈 | 栈的最小值 | ✔ |
| 02 | 由两个栈组成的队列 | 用栈实现队列 | ✔ |
| 03 | 如何仅用递归函数和栈操作逆序一个栈 | 用递归函数和栈操作逆序一个栈(牛客网) | ✔ |
| 04 | 猫狗队列 | ||
| 05 | 用一个栈实现另一个栈的排序 | 栈排序 | ✔ |
| 06 | 用栈来求解汉诺塔问题 | 面试题 08.06. 汉诺塔问题 | ✔ |
| 07 | 生成窗口最大值数组 | 滑动窗口最大值 | ✔ |
| 08 | 单调栈结构 | 单调栈结构(牛客网) | ✔ |
| 09 | 求最大子矩阵的大小 | 最大矩形 | ✔ |
| 10 | 最大值减去最小值小于或等于num的子数组数量 | 最大值减去最小值小于或等于num的子数组数量(牛客网) | ✔ |
| 11 | 可见山峰对数量 |
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 打印两个有序链表的公布部分 | 打印两个有序链表的公布部分(牛客网) | ✔ |
| 02 | 在单链表和双链表中删除倒数第K个节点 | 删除链表的倒数第N个节点 | ✔ |
| 03 | 删除链表的中间节点和a/b处节点 | 删除中间节点 | ✔ |
| 04 | 翻转单向和双向链表 | 反转链表 | ✔ |
| 05 | 翻转部分单向链表 | 翻转部分单向链表(牛客网) | ✔ |
| 06 | 环形单链表的约瑟夫问题 | 环形单链表的约瑟夫问题(牛客网)、剑指 Offer 62. 圆圈中最后剩下的数字 | ✔ |
| 07 | 判断一个链表是否为回文结构 | 回文链表 | ✔ |
| 08 | 将单向链表按某值划分为左边小、中间相等、右边大的形式 | 颜色分类 | ✔ |
| 09 | 复制含有随机指针节点的链表 | 复杂链表的复制 | ✔ |
| 10 | 两个单链表生成相加链表 | 链表求和 | ✔ |
| 11 | 两个单链表相交的一系列问题 | 相交链表 | ✔ |
| 12 | 将单链表的每K个节点之间逆序 | K 个一组翻转链表 | ✔ |
| 13 | 删除无序单链表中值重复出现的节点 | 删除排序链表中的重复元素 | ✔ |
| 14 | 在单链表中删除指定值的节点 | 删除链表的节点 | ✔ |
| 15 | 将搜索二叉树转换成双向链表 | 二叉搜索树与双向链表 | ✔ |
| 16 | 单链表的选择排序 | 对链表进行插入排序 | ✔ |
| 17 | 一种怪异的节点删除方式 | 删除链表的节点 | ✔ |
| 18 | 向有序的环形单链表中插入新节点 | 向有序的环形单链表中插入新节点(牛客网) | ✔ |
| 19 | 合并两个有序的单链表 | 合并两个有序链表 | ✔ |
| 20 | 按照左右半区的方式重新组合单链表 | 按照左右半区的方式重新组合单链表(牛客网) | ✔ |
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 分别用递归和非递归方式实现二叉树先序、中序和后序遍历 | 二叉树的前序遍历、二叉树的中序遍历、二叉树的后序遍历 | ✔ |
| 02 | 二叉树的最小深度 | 二叉树的最小深度、二叉树的最大深度 | ✔ |
| 03 | 如何较为直观的打印二叉树 | ||
| 04 | 二叉树的序列化和反序列化 | 二叉树的序列化与反序列化 | ✔ |
| 05 | 遍历二叉树的神级方法（Morris遍历） | 遍历二叉树的神级方法(牛客网) | ✔ |
| 06 | 在二叉树中找到累加和为指定值的最长路径长度 | 二叉树中和为某一值的路径 | ✔ |
| 07 | 找到二叉树中的最大搜索二叉子树 | 找到二叉树中的最大搜索二叉子树(牛客网) | 只能过50％case |
| 08 | 找到二叉树中符合搜索二叉树条件的最大拓扑结构 | 找到二叉树中符合搜索二叉树条件的最大拓扑结构(牛客网) | |
| 09 | 二叉树的按层打印和ZigZag打印 | 二叉树的层序遍历 | ✔ |
| 10 | 调整搜索二叉树中两个错误的节点 | 恢复二叉搜索树 | ✔ |
| 11 | 判断t1树是否包含t2树全部的拓扑结构 | 树的子结构 | ✔ |
| 12 | 判断t1树是否有与t2树拓扑结构完全相同的子树 | 另一个树的子树 | ✔ |
| 13 | 判断二叉树是否为平衡二叉树 | 平衡二叉树 | ✔ |
| 14 | 根据后序数组重建搜索二叉树 | 二叉搜索树的后序遍历序列 | ✔ |
| 15 | 判断一颗二叉树是否为搜索二叉树和完全二叉树 | 验证二叉搜索树、二叉树的完全性检验 | ✔ |
| 16 | 通过有序数组生成平衡搜索二叉树 | 将有序数组转换为二叉搜索树 | ✔ |
| 17 | 在二叉树中找到一个节点的后继节点 | 后继者 | ✔ |
| 18 | 在二叉树中找到两个节点的最近公共祖先 | 二叉搜索树的最近公共祖先、二叉树的最近公共祖先 | ✔ |
| 19 | Tarjan算法与并查集解决二叉树节点间最近公共祖先的批量查询问题 | ||
| 20 | 二叉树节点间的最大距离问题 | 二叉树的直径 | ✔ |
| 21 | 派对的最大快乐值 | ||
| 22 | 通过先序遍历和中序遍历生成后序数组 | 从中序与后序遍历序列构造二叉树、根据前序和后序遍历构造二叉树 | ✔ |
| 23 | 统计和生成所有不同的二叉树 | 不同的二叉搜索树、不同的二叉搜索树 II | |
| 24 | 统计完全二叉树的节点数 | 完全二叉树的节点个数 | ✔ |
备注：
1、第4题牛客网的OJ测试有问题，按照书本解法，只能过40％的case
2、第5题没做优化，
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 斐波那契数列问题的递归和动态规划 | 斐波那契数 | ✔ |
| 02 | 矩阵的最小路径和 | 最小路径和 | ✔ |
| 03 | 换钱的最少货币数 | 零钱兑换 | ✔ |
| 04 | 机器人到达指定位置方法数 | 机器人到达指定位置方法数（牛客） | ✔ |
| 05 | 换钱的方法数 | 零钱兑换 II | ✔ |
| 06 | 打气球的最大分数 | ||
| 07 | 最长递增子序列 | 最长递增子序列的个数 | ✔ |
| 08 | 信封嵌套问题 | ||
| 09 | 汉诺塔问题 | ||
| 10 | 最长公共子序列问题 | 最长公共子序列 | |
| 11 | 最长公共子串问题 | ||
| 12 | 子数组异或为0的最多划分 | ||
| 13 | 最小的编辑代价 | ||
| 14 | 字符串的交错组成 | ||
| 15 | 龙与地下城游戏问题 | 地下城游戏 | |
| 16 | 数字字符串转换为字母组合的种数 | ||
| 17 | 表达式得到期望结果的组成种数 | ||
| 18 | 排成一条线的纸牌博弈问题 | ||
| 19 | 跳跃游戏 | 跳跃游戏、跳跃游戏 II | ✔ |
| 20 | 数组中最长连续序列 | 最长连续序列 | |
| 21 | N皇后问题 |
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 判断两个字符串是否互为变形词 | 判断两个字符串是否互为变形词(牛客) | ✔ |
| 02 | 判断两个字符串是否互为旋转词 | 判断两个字符串是否互为旋转词(牛客) | ✔ |
| 03 | 将整数字符串转成整数值 | ||
| 04 | 字符串的统计字符串 | ||
| 05 | 判断字符串数组中是否所有的字符都只出现过一次 | 牛客网和LeetCode OJ均找不到这个题目 | ✔ |
| 06 | 在有序但含有空的数组中查找字符串 | 在有序但含有空的数组中查找字符串(牛客网) | ✔ |
| 07 | 字符串的调整与替换 | 替换空格 | ✔ |
| 08 | 翻转字符串 | 翻转单词顺序 | ✔ |
| 09 | 完美洗牌问题 | ||
| 10 | 删除多余字符得到字典序最小的字符串 | ||
| 11 | 数组中两个字符串的最小距离 | ||
| 12 | 字符串的转换路径问题 | ||
| 13 | 添加最少字符使字符串整体都是回文字符串 | 让字符串成为回文串的最少插入次数 | ✔ |
| 14 | 括号字符串的有效性和最长有效长度 | ||
| 15 | 公式字符串求值 | ||
| 16 | 0左边必有1的二进制字符串数量 | ||
| 17 | 拼接所有字符串产生字典顺序最小的大写字符串 | ||
| 18 | 找到字符串的最长无重复字符子串 | 最长不含重复字符的子字符串 | ✔ |
| 19 | 找到指定的新类型字符 | ||
| 20 | 旋变字符串问题 | ||
| 21 | 最小包含子串的长度 | 最小覆盖子串 | |
| 22 | 回文最少分割数 | ||
| 23 | 字符串匹配问题 | ||
| 24 | 字典树（前缀树）的实现 | 实现 Trie (前缀树) | ✔ |
| 25 | 子数组的最大异或和 | 子数组最大异或和(牛客网)，数组中两个数的最大异或值 |
第5题还没做完，第6题的进阶问题还没做完。
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 转圈打印矩阵 | 顺时针打印矩阵 | ✔ |
| 02 | 将正方形矩阵顺时针转动90° | 旋转矩阵 | ✔ |
| 03 | ”之“字型打印矩阵 | 对角线遍历 | ✔ |
| 04 | 找到无序数组中最小的k个数 | 最小的k个数 | ✔ |
| 05 | 需要排序的最短子数组长度 | 最短无序连续子数组 | ✔ |
| 06 | 在数组中找到出现次数大于N/K的数 | 数组中出现次数超过一半的数字、求众数 II | ✔ |
| 07 | 在行列都排好序的矩阵中找指定数 | 二维数组中的查找 | ✔ |
| 08 | 最长的可整合子数组的长度 | ||
| 09 | 不重复打印排序数组中相加和为给定值得所有二元组和三元组 | 和为s的两个数字 | ✔ |
| 10 | 未排序正数组中累加和为给定值的最长子数组长度 | 未排序正数组中累加和为给定值的最长子数组长度(牛客网) | |
| 11 | 未排序数组中累加和为给定值的最长子数组系列问题 | ||
| 12 | 未排序数组中累加小于或等于给定值的最长子数组长度 | ||
| 13 | 计算数组的小和 | ||
| 14 | 自然数数组的排序 | ||
| 15 | 奇数下标都是奇数或偶数下标都是偶数 | 奇数下标都是奇数或偶数下标都是偶数(牛客网) | |
| 16 | 子数组的最大累加和问题 | 连续子数组的最大和 | ✔ |
| 17 | 子矩阵的最大累加和问题 | ||
| 18 | 在数组中找到一个局部最小的位置 | ||
| 19 | 数组中子数组的最大累乘积 | 乘积最大子数组 | |
| 20 | 打印N个数组整体最大的Top K | 最小的k个数 | ✔ |
| 21 | 边界都是1的最大正方形大小 | ||
| 22 | 不包含本位置的累乘数组 | 构建乘积数组 | ✔ |
| 23 | 数组的partition调整 | ||
| 24 | 求最短通路值 | ||
| 25 | 数组中未出现的最小正整数 | 缺失的第一个正数 | ✔ |
| 26 | 数组排序之后相邻数的最大差值 | 最大间距 | ✔ |
| 27 | 做项目的最大收益问题 | IPO（备注：思路没问题，但是会超出时间限制，还得进一步优化） | |
| 28 | 分金条的最小花费 | ||
| 29 | 大楼轮廓问题 | ||
| 30 | 加油站良好出发点问题 | ||
| 31 | 容器盛水问题 |
| 序号 | 题目 | OJ链接 | 备注 |
|---|---|---|---|
| 01 | 从5随机到7随机及其扩展 | ||
| 02 | 一行代码求两个数的公约数 | ||
| 03 | 有关阶乘的两个问题 | ||
| 04 | 判断一个点是否在矩形内部 | ||
| 05 | 判断一个点是否在三角形内部 | ||
| 06 | 折纸问题 | ||
| 07 | 能否完美地拼成矩形 | ||
| 08 | 蓄水池问题 | ||
| 09 | 设计有setAll功能的哈希表 | ||
| 11 | 最大的leftMax与rightMax之差的绝对值 | 最大的leftMax与rightMax之差的绝对值(牛客网) | |
| 12 | 设计LRU缓存结构 | LRU缓存机制 | ✔ |
| 13 | LFU缓存结构设计 | ||
| 14 | 设计RamdomPool结构 | 常数时间插入、删除和获取随机元素、O(1) 时间插入、删除和获取随机元素 - 允许重复 | ✔ |
| 15 | 并查集的实现 | 岛屿数量 | ✔ |
| 16 | 调整[0,x)区间上的数出现的概率 | ||
| 17 | 路径数组变为统计数组 | ||
| 18 | 正数数组的最小不可组成和 | ||
| 19 | 累加出整个范围所有的数最少还需几个数 | ||
| 20 | 一种字符串和数字的对应关系 | ||
| 21 | 1到n中1出现的次数 | 1～n 整数中 1 出现的次数 | |
| 22 | 从N个数中等概率打印M个数 | ||
| 23 | 判断一个数是否是回文数 | 回文数 | ✔ |
| 24 | 在有序旋转数组中找到最小值 | 寻找旋转排序数组中的最小值 II | ✔ |
| 25 | 在有序旋转数组中找到一个数 | 搜索旋转排序数组 | ✔ |
| 26 | 数字的英文表达和正文表达 | ||
| 27 | 分糖果问题 | ||
| 28 | 一种消息接收并打印的结构设计 | ||
| 29 | 随时找到数据流的中位数 | 数据流的中位数 | ✔ |
| 30 | 在两个长度相等的排序数组中找到中位数 | 寻找两个正序数组的中位数 | ✔ |
| 31 | 在两个排序数组中找到第k小的数 | 在LeetCode里面，30和31题都是同样一道题目 | |
| 32 | 两个有序数组间相加和的Top k问题 | ||
| 33 | 出现次数的Top k问题 | 前 K 个高频元素 | ✔ |
| 34 | Manacher算法 | ||
| 35 | KMP算法 | ||
| 36 | 丢棋子问题 | ||
| 37 | 画匠问题 | ||
| 38 | 邮局选址问题 |