剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即A中有出现和B相同的结构和节点值。
例如: 给定的树A:
3 / \ 4 5 / \1 2
给定的树 B：
4 /1
返回 true，因为B与A的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]输出：true
限制：
0 <= 节点个数 <= 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
递归搜索。B为空匹配成功，A为空匹配失败。若B不为根，当且节点又匹配失败，直接返回false。若B与当前节点匹配成功，那么A的左右孩子与B的左右孩子一定匹配成功，或者B与当前节点的左右子树匹配成功。
class Solution { ...
LeetCode 529. 扫雷游戏
让我们一起来玩扫雷游戏！
给你一个大小为m x n二维字符矩阵board，表示扫雷游戏的盘面，其中：
'M'代表一个 未挖出的 地雷， 'E'代表一个 未挖出的 空方块， 'B'代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块， 数字（'1' 到'8'）表示有多少地雷与这块 已挖出的 方块相邻， 'X'则表示一个 已挖出的 地雷。 给你一个整数数组click，其中click = [clickr, clickc]表示在所有未挖出的方块（'M'或者'E'）中的下一个点击位置（clickr是行下标，clickc是列下标）。
根据以下规则，返回相应位置被点击后对应的盘面：
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。 如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。 如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。 如果在此次点击中，若无更多方块可被揭露，则返回盘面。
示例 1：
输入：board = [["E"," ...
LeetCode 517. 超级洗衣机
假设有n台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意m(1 <= m <= n)台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个整数数组machines代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回-1。
示例 1：
输入：machines = [1,0,5] 输出：3 解释： 第一步: 1 0 <-- 5 => 1 1 4 第二步: 1 <-- 1 <-- 4 => 2 1 3 第三步: 2 1 <-- 3 => 2 2 2
示例 2：
输入：machines = [0,3,0] 输出：2 解释： 第一步: 0 <-- 3 0 => 1 2 0 第二步: 1 2 --> 0 ...
LeetCode 1219. 黄金矿工
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为m * n的网格grid进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是0。
为了使收益最大化，矿工需要按以下规则来开采黄金：
每当矿工进入一个单元，就会收集该单元格中的所有黄金。 矿工每次可以从当前位置向上下左右四个方向走。 每个单元格只能被开采（进入）一次。 不得开采（进入）黄金数目为0的单元格。 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]] 输出：24 解释：
[[0,6,0], [5,8,7], [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 输出：28 解释：
[[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -& ...
复杂度高级分析技术--摊还分析
在深入浅出算法复杂度一文中，我们提到还存在一种复杂度分析策略，称为摊还分析（Amortized Analysis）。
在摊还分析中，我们主要关心某数据结构的一个操作序列中执行所有操作的平均时间，以此评价单次操作所花费的代价。摊还分析中最常用的三个技术分别是聚合分析、记账分析和势能分析。接下来我们主要讨论这三种摊还分析技术的原理以及例子。
1. 聚合分析法
1.1 原理
所谓聚合分析，就是尝试求出一个包含个操作的序列在最坏情况下花费的时间，然后将此最坏情况下每个操作的平均代价，或者说摊还代价记为。
我们考虑「二进制计数器的比特反转问题」。设有一位二进制计数器，其初值为。我们用一个长度为k的位数组count来表示这个计数器，其中count的每一位为0或1。另外我们规定，计数器值的最低位存在count[0]中，最高位存在count[k-1]中。于是，我们可以得到计数器的自增算法：
void increment(int[] count) { int i = 0; while (i < count.length && count[i]==1) count[i++] = 0 ...
Catalan数及其应用
Catalan数，即卡特兰数（英语：Catalan number），又称明安图数，是组合数学中一种常出现于各种级数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。
它是指满足以下递推关系的数列： Catalan数的递推关系很简单，乍看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。Stanley的Enumerative Combinatorics一书中就囊括了上百个最后可以归结为Catalan数的问题，所以它的重要性不言而喻。接下来我们从上述递推关系的解开始，一步步探讨Catalan数的一些经典应用。
0. 求解Catalan数
由于Catalan数的递推关系并不是线性的，所以它的求解方法比较复杂。这里我们通过生成函数（母函数）来求解Catalan数的递推关系。
根据Catalan数的递推关系，我们设。
设函数的生成函数为： 根据递推关系，有 对上式求和，有 于是得到一个关于的二次方程： 解之即得： 考虑到牛顿二项式定理： 则可以表示为： 其中的系数为： 注意到的系数应当为正，所以 其中的系数为： 这便是卡特兰数的计算公式。
1 ...
前n项平方和怎么求？
设为前项平方和： 它的通项公式我们在中学阶段已经学习过，即 但是它的推导过程却不算简单。本文主要从组合数学的角度罗列一些此级数通项公式的推导方法。要理解本文的内容，读者应当学习过一些组合数学或离散数学的知识。
方法一：求解递推关系
考虑 上式为常系数非线性递推关系。若我们尝试直接求解，则需要先求通解，再求特解，然后将他们线性组合。显然，通解为，但是特解却并不好求。所以我们换个思路，尝试消去递推关系的非齐次项。 上述两式相减，并利用替换，可得 WOW，我们成功让等式右边的降幂了！这暗示着我们可以使用这个方法，将右边的幂函数一直降至常数。当然，随之而来的就是左边的递推关系会越变越复杂。 化简之后，我们得到了一个相当复杂的递推关系，但庆幸的是它是齐次的，我们无需再考虑通解。 我们列出上式的特征方程： 先别急着解它，我断言，它一定只有这一个实数根。否则，就将会以指数级的速度增长了，这与我们的直觉不符。当然，不难发现， 所以的的确确是它的四重根。那么该递推关系的解应该是： 注意到，根据的定义： 将前四项代入，得到一个线性方程组： 容易解得： 也就是 回顾我们的求解过 ...
LeetCode 1725. 可以形成最大正方形的矩形数目
1. 题目描述
给你一个数组rectangles，其中rectangles[i] = [li, wi]表示第i个矩形的长度为li、宽度为wi。
如果存在k同时满足k <= li和k <= wi，就可以将第i个矩形切成边长为k的正方形。例如，矩形[4,6]可以切成边长最大为4的正方形。
设maxLen为可以从矩形数组rectangles切分得到的 最大正方形 的边长。请你统计有多少个矩形能够切出边长为maxLen的正方形，并返回矩形数目。
示例 1：
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]输出：3解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。最大正方形的边长为 5 ，可以由 3 个矩形切分得到。示例 2：
输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]输出：3
提示：
1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi
来源： ...
剑指Offer 14-I. 剪绳子
1. 题目描述
给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n > 1并且m > 1），每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
来源：力扣（LeetCode）
2. 解题思路
给定一个数，假设将其拆分成个因子。根据均值不等式，当且仅当时，有最大。
考虑函数 求导得 因此，当时，单减。时，取得最大值。
所以，我们的划分因子数应当为： 以上的讨论虽然找出了极值点，但局限于连续的情形下。题目的要求是分割为整数段，我们只能求出函数的极值点，然后分别尝试极值点左右的值。
比如，当时，计算出的极值点。我们自然会依次尝试它的左右整数点和，并尽可能将均分。 ...
LeetCode 1414. 和为K的最少斐波那契数字数目
1. 题目描述
给你数字k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的k，一定能找到可行解。
示例 1：
输入：k = 7输出：2 解释：斐波那契数字为：1，1，2，3，5，8，13，……对于 k = 7 ，我们可以得到 2 + 5 = 7 。
示例 2：
输入：k = 10输出：2 解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
示例 3：
输入：k = 19输出：3 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
提示：
1 <= k <= 10^9
来源：力扣（LeetCode）
2. 解题思路
对于一个给定的数字k，注意到总是存在一个可行解的。那么在最优的方案下，它的拆分数中一定有一个最大的不超过k的Fibonacci数。
只要注意到这样一个事实，越小的数，最优方案的拆分数就越少。那么原问题就变为一个减而治之的问题。设不超过的k的最大的斐波那契 ...