Algorithm - Patterns | chenoiLab

icon

password

Python基础逻辑常用特性数组初始化交换元素值连续不等式或等式标准算法排序二分查找和插入标准数据结构栈队列堆 HashSet，HashTable collections 库基础 - 数据结构与算法示例 1：strStr 示例 2：subsets 面试注意点二叉树知识点二叉树遍历递归模板前序非递归中序非递归后序非递归 BFS 层次遍历分治法应用常见题目示例 maximum-depth-of-binary-tree balanced-binary-tree binary-tree-maximum-path-sum lowest-common-ancestor-of-a-binary-tree BFS 层次应用 binary-tree-zigzag-level-order-traversal 二叉搜索树应用 validate-binary-search-tree insert-into-a-binary-search-tree 总结

Python基础

逻辑

进行 coding 面试时，如果不指定使用的编程语言，一般来讲考察的是做题的思路而不是编程本身，因此不需要从零开始实现一些基础的数据结构或算法，利用语言的一些特性和自带的标准库可以大大简化代码，提高做题速度。下面会总结一些 Python3 常用的特性，标准算法和数据结构。

常用特性

Python语言有很多特性可以大大简化代码，下面列举几个常用的。

数组初始化

交换元素值

连续不等式或等式

标准算法

排序

Python 中排序主要使用 sorted() 和 .sort() 函数，在官网有详细介绍，大家可以自行阅读。

二分查找和插入

Python 自带的 bisect 库可以实现二分查找和插入，非常方便。

标准数据结构

栈

Python 中的栈使用自带的 list 类来实现，可参考官方文档。

队列

使用 collections 库中的 deque 类实现，可参考官方文档。

堆

Python 中没有真的 heap 类，实现堆是使用 list 类配合 heapq 库中的堆算法，且只支持最小堆，最大堆需要通过传入负的优先级来实现，可参考官方文档。

HashSet，HashTable

分别通过 set 类和 dict 类来实现。

collections 库

Python 的 collections 库在刷题时会经常用到，它拓展了一些Python中基础的类，提供了更多功能，例如 defaultdict 可以预设字典中元素 value 的类型，自动提供初始化，Counter 可以直接统计元素出现个数等。

基础 - 数据结构与算法

数据结构是一种数据的表现形式，如链表、二叉树、栈、队列等都是内存中一段数据表现的形式。算法是一种通用的解决问题的模板或者思路，大部分数据结构都有一套通用的算法模板，所以掌握这些通用的算法模板即可解决各种算法问题。

后面会分专题讲解各种数据结构、基本的算法模板、和一些高级算法模板，每一个专题都有一些经典练习题，完成所有练习的题后，你对数据结构和算法会有新的收获和体会。

先介绍两个算法题，试试感觉~

示例 1：strStr

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串

需要注意点

循环时，i 不需要到 len-1

如果找到目标字符串，len(needle) == j

示例 2：subsets

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下

通过不停的选择，撤销选择，来穷尽所有可能性，最后将满足条件的结果返回。答案代码：

面试注意点

我们大多数时候，刷算法题可能都是为了准备面试，所以面试的时候需要注意一些点

快速定位到题目的知识点，找到知识点的通用模板，可能需要根据题目特殊情况做特殊处理。

先去朝一个解决问题的方向！先抛出可行解，而不是最优解！先解决，再优化！

代码的风格要统一，熟悉各类语言的代码规范。

命名尽量简洁明了，尽量不用数字命名如：i1、node1、a1、b2

常见错误总结

访问下标时，不能访问越界
空值 nil 问题 run time error

二叉树

知识点

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

以根访问顺序决定是什么遍历

左子树都是优先右子树

递归模板

递归实现二叉树遍历非常简单，不同顺序区别仅在于访问父结点顺序

前序非递归

本质上是图的DFS的一个特例，因此可以用栈来实现

中序非递归

后序非递归

注意点

核心就是：根节点必须在右节点弹出之后，再弹出

DFS 深度搜索-从下向上（分治法）

注意点：

DFS 深度搜索（从上到下）和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

BFS 层次遍历

分治法应用

先分别处理局部，再合并结果

适用场景

快速排序

归并排序

二叉树相关问题

分治法模板

递归返回条件

分段处理

合并结果

常见题目示例

maximum-depth-of-binary-tree

给定一个二叉树，找出其最大深度。

思路 1：分治法

思路 2：层序遍历

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路 1：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1，

思路 2：使用后序遍历实现分治法的迭代版本

binary-tree-maximum-path-sum

给定一个非空二叉树，返回其最大路径和。

思路：分治法。最大路径的可能情况：左子树的最大路径，右子树的最大路径，或通过根结点的最大路径。其中通过根结点的最大路径值等于以左子树根结点为端点的最大路径值加以右子树根结点为端点的最大路径值再加上根结点值，这里还要考虑有负值的情况即负值路径需要丢弃不取。

lowest-common-ancestor-of-a-binary-tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

BFS 层次应用

binary-tree-zigzag-level-order-traversal

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

思路：在BFS迭代模板上改用双端队列控制输出顺序

二叉搜索树应用

validate-binary-search-tree

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路 1：中序遍历后检查输出是否有序，缺点是如果不平衡无法提前返回结果，代码略

思路 2：分治法，一个二叉树为合法的二叉搜索树当且仅当左右子树为合法二叉搜索树且根结点值大于右子树最小值小于左子树最大值。缺点是若不用迭代形式实现则无法提前返回，而迭代实现右比较复杂。

思路 3：利用二叉搜索树的性质，根结点为左子树的右边界，右子树的左边界，使用先序遍历自顶向下更新左右子树的边界并检查是否合法，迭代版本实现简单且可以提前返回结果。

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。

思路：如果只是为了完成任务则找到最后一个叶子节点满足插入条件即可。但此题深挖可以涉及到如何插入并维持平衡二叉搜索树的问题，并不适合初学者。

总结

掌握二叉树递归与非递归遍历

理解 DFS 前序遍历与分治法

理解 BFS 层次遍历