概述 回溯法是一种选优搜索法（试探法），被称为通用的解题方法，这种方法适用于解一些组合数相当大的问题。通过剪枝（约束+限界）可以大幅减少解决问题的计算量（搜索量）。 深度优先搜索（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到…

前言 二叉搜索树（Binary Search Tree）是一种特殊的二叉树，支持多种动态集合操作，如 Search、Insert、Delete、Minimum 和 Maximum 等。 二叉查找树要么是一棵空树，要么是一棵具有如下性质的非空二叉树： 若左子树非空，则左子树上的所有节点的关键字值均小于根节点的关键字值。 若右子树非空，则右子树上的所有节点的关键字值均大于根节点的关键字值。 左、右子树本身也分别是一棵二叉查找树（二叉排序树）。 可以看出，二叉搜索树中各个节点都不相同，且对二叉查找树进行中序遍历，可以得到…

什么是二叉堆 二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。 构建二叉堆 二叉堆一般用数组来表示。如果根节点在数组中的位置是 1，第 n 个位置的子节点分别在 2n 和 2n+1。因此，第 1 个位置的子节点在 2 和 3，第 2 …

前言 在前面两章有介绍过单链表的基本操作以及有环链表的相关问题。本章主要分析两个单链表的交点问题。 首先声明，两个单链表只能存在 Y 型交叉，不会存在 X 型交叉。因为如果是 X 型交叉，节点在交叉点之后便不知道 next 指针指向为哪一个节点。 实战分析 判断单链表是否相交存在三种情况： 两个单链表都没有环。 两个单链表中 一个有环，一个没有环。 两个链表都有环。 情况 1 对于仅判断相交不相交的话：判断最后一个节点是否相同的办法并不慢，如果两个链表长度m,n 那么复杂度O(m+n)，这是最优的复杂度。 def …

概述 单向链表 链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。 循环链表 在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的…

前言 数据结构中的线性表：分为顺序表和链表。 线性表 线性表（Linear List）是由 n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。 其中： 数据元素的个数 n 定义为表的长度 = "list".length() （"list".length() = 0（表里没有一个元素）时称为空表） 将非空的线性表（n>=1）记作：（a[0]，a[1]，a[2]，…，a[n-1]） 数据元素 a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同 一个数据元素可…

什么是拓扑排序 在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中都在 v 之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当…

问题描述： 给定两个正整数，求它们的最小公倍数。 提高要求： 三个以上数的求解。 一、两个数的情况下求解最小公倍数 1.穷举法 lcm = min(m,n) max_num = max(m,n) for i in range(2,max_num+1): if lcm*i % m ==0 and lcm*i % n ==0: lcm *= i break print(lcm) 2.公式 lcm = a*b//gcd(a, b) def lcm(a,b): gcd = lambda a, b: a if b == 0 …

关于分割问题，存在多种情况，在此进行汇总，对问题进行分析，对所用到的公式进行推导。 1.直线分割 题目：n 个点最多可以把一条直线划分成多少段 公式：A(n) = n+1 2.平面分割 题目：n 条直线，最多可以把平面分为多少个区域。 公式：B(n) = n(n+1)/2+1 分析： 假设平面上已有 n 条直线它们把平面划分成最多的区域,那么第 n+1 条直线下去的时候,为了保证获得最多的区域,那么要求这条直线和之前的 n 条直线都相交,并且新产生的交点不和之前的交点重合.显然第 n+1 条直线和之前的 n 条直线…

前言 题目来源： 记得一副有趣的对联: "雾锁山头山锁雾, 天连水尾水连天", 上联和下联都是回文的. 当然类似的还有: "上海自来水水来自海上, 山西悬空寺寺空悬西山". 回文是什么意思? 就是把内容反过来读也是和原来一样的, 譬如 abccba, xyzyx, 这些都是回文的. 然而我们更感兴趣的是在一个英文字符串 L 中, 怎么找出最长的回文子串. 例如 L = "caayyhheehhbbbhhjhhyyaac", 那么它最长的回文子串是 "hhbbbhh". 这个任务看似简单, 但是如果我告诉你 L 的长…