Python程序员面试算法宝典

ghs,2019-10.28

  本项目用于复现猿媛之家书籍《Python程序员面试算法宝典》中算法代码。书中代码采用Python2实现。本人参照作者思路，用Python3进行编程复现。

  ps.问题被放置在problem文件中，原理被放置在thinking文件中，便于复习、思考。

常用数据结构实现

  本块主要列举书中所涉及到的数据结构的实现。其中都用Python进行编译。

对应章节	数据结构
1	链表
2	栈、队列和哈希
3	二叉树
4	数组
5	字符串
6	基本数字运算
7	排列组合与概率
8	排序
9	大数据

链表

  在Python中，没有指针的概念，而类似指针的功能都是通过引用来实现的，为了方便理解，我仍使用指针来进行描述，而在实现的代码中，都是通过引用来建立结点之间的关系。

  单链表数据结构的定义实例

class LNode:
    def __init__(self,x):
        self.data = x
        self.next = None

  另外，Python中没有数组的数据结构，但是列表和数组很像。本书代码中均采用列表来表示有序数组。

序号	问题	难度	代码	原理
1	链表的逆序	3	1.就地逆序2.递归法3.插入法	Reverse
2	无序链表移除重复项	3	1.顺序删除2.递归法	Delete
3	计算两个单链表表示数之和	3	链表相加法	Count
4	链表的重新排序	3	中间结点逆序法	Reorder
5	找出单链表的倒数第k个数	3	快慢指针法	Find
6	检测单链表是否有环	4	快慢指针遍历法	Test
7	把链表相邻元素翻转	3	就地逆序法	Flip
8	把链表以K个结点为一组翻转	3	翻转法	Flip
9	合并两个有序链表	3	指针指向法	Merge
10	给定某结点的指针，删除该结点	4	复制数据删除法	Delete
11	判断两个无环单链表是否交叉	4	尾结点法	IsIntersect
12	展开链接列表	4	归并法	Merge

栈、队列与哈希

  栈与队列是在程序设计中被广泛使用的两种重要线性数据结构，都是在一个特定范围的存储单元中存储的数据，这些数据可以重新被取出使用。

  不同的是，栈先存进去的数据最后只能最后被取出来，是LIFO(Last In First Out，后进先出)，它将进行顺序逆序，即先进后出，后进先出；队列，先排队先买，后排队后买，是FIFO(First In First Out，先进先出)，它保持进出顺序一致，即先进先出，后进后出。

序号	问题	难度	代码	原理
1	实现栈	3	1.数组实现2.链表实现	Stack
2	实现队列	3	1.数组实现2.链表实现	Queue
3	翻转栈	4	递归	Flip
4	判断出栈序列	3	模拟入栈	Array
5	求栈中最小元素(O(1))	4	两栈结构	Double-Stack
6	用两个栈模拟队列操作	3	插入弹出栈	Double-Stack
7	设计排序系统	4	双向队列	Double-ended queue
8	实现LRU缓存方案	4	双向队列和哈希表	deque、hash
9	从给定车票找出旅程	3	哈希法	Hash
10	数组中找出条件数对	3	字典法	Dict

二叉树

  二叉树(Binary Tree)也称为二分数、二元树等，它是n个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素以及两个不相交、分别被称为左子树和右子树的二叉树组成。

  二叉树的递归定义为：二叉树或者是一棵空树，或者是一颗由一个根结点和两棵互不相交的分别称作根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

• 结点的度：结点所拥有的的子树的个数称为该结点的度。
• 叶子结点：度为0的结点称为叶子结点。
• 分支节点：度不为0的结点称为分支结点。
• 左孩子、右孩子、双亲：一个结点的子树的根结点称为这个结点的孩子，这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
• 路径、路径长度：如果一棵树的一串结点n1、n2……nk有如下关系：结点ni是ni+1的父结点，就把n1、n2……nk称为一条由n1到nk的路径。这条路径的长度为k-1.
• 祖先、子孙：如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
• 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加一。
• 树的深度：树中所有结点的最大层数称为树的深度。
• 树的度：树中各结点度的最大值称为该树的度。
• 满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称作满二叉树。
• 完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左至右的顺序进行编号，如果编号为i的结点和满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

  二叉树的基本性质如下所示：

1. 一颗非空二叉树的第$i$层上最多有$ 2^{n-1} $个结点。
2. 一棵深度为$k$的二叉树中，最多具有$2 ^k -1$个结点，最少有$k$个结点。
3. 对于一棵非空的二叉树，度为0的结点总是比度为2的结点多一个，即如果叶子结点数为$n0$，度为2的结点数为$n2$，则有$n0 = n2 +1$。
4. 具有$n$个结点的完全二叉树的深度为「${log}_2 n$」+1。

  二叉树有顺序存储和链式存储两种存储结构。

class BiTNode:
    def __init__(self):
        self.data = None
        self.lchild = None
        self.rchild = None

序号	问题	难度	代码	原理
1	二叉树中放入有序整数数组	4	递归	Recursion
2	从顶部逐层打印结点数据	3	队列	Queue
3	二叉树的最大子树和	4	后序遍历	AfterOrder
4	判断二叉树相等	3	递归	Recursion
5	二叉树转换为双向链表	4	双向链表	List
6	判断数组是否是二元查找树后序遍历的序列	4	后序遍历	AfterOrder
7	找出两个结点的最近共同父结点	3	1.路径对比2.1.结点编号	Route、Number
8	复制二叉树	3	递归	Recursion
9	找出任意整数的所有路径	4	先序遍历	BeforeOrder
10	对二叉树进行镜像反转	3	递归	Recursion
11	二叉排序树中找出第一个大于中间值的结点	4	中序遍历	InOrder
12	找出路径最大的和	4	后序遍历	AfterOrder
13	实现反向DNS查找缓存	4	Trie树	Trie

数组

  数组是某类型的数据按照一定的顺序组成的数据的集合。如果将有限个类型相同的变量的集合命名，那么这个称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素。用于区分数组的各个元素的数字编号称为下标。

序号	问题	难度	代码	原理
1	找出数组中唯一重复元素	3	1.异或法2.数据映射法	xor、map
2	查找最大值、最小值	3	1.分治法2.变形的分治法	divide and conquer
3	找出旋转数组的最小元素	3	二分查找法	binary search
4	找出数组中丢失的数	4	1.累加求和2.异或法	sum、xor
5	寻找出现奇数次的数	3	1.字典法2.异或法	dict、xor
6	找出第k小的数	4	1.部分排序法2.类快速排序法	sort、quick sort
7	求出两个元素的最小距离	3	1.蛮力法2.动态规划	brute force、dynamic programming
8	求解最小三元组距离	4	最小距离法	minimum distance
9	求数组连续最大和	4	动态规划	dynamic programming
10	寻找出现1次的数	4	异或法	xor
11	不排序求中位数	4	类快速排序法	quick sort
12	对数组循环移位	3	翻转法	flip

序号	问题	难度	代码	原理
13	按要求构造数组	3	逆向遍历	Reverse Traversal
14	求解迷宫问题	4	回溯法	Backtracking
15	三个有序数组中找公共元素	4	比较法	Comparison
16	对有大量重复元素的数组排序	4	1.AVL树2.哈希法	AVLtree、Hash
17	对任务进行调度	4	贪心算法	Greedy
18	对磁盘分区	4	双重遍历	Double Traverse

字符串

  字符串是由数字、字母、下划线组成的一串字符，是最常用的数据结构之一。通过考察字符串的一些细节，能够看出求职者的编程习惯，进而反映出求职者在操作系统、软件工程、边界内存处理等方面的知识掌握能力，而这些能力往往是是否录用求职者的重要参考因素。

序号	问题	难度	代码	原理