LeetCode 54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/spiral-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
递归处理即可。
class Solution { public List<Integer> ans = new ArrayList<>(8); int[][] ...
剑指Offer 12. 矩阵中的路径
给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的3×4的矩阵中包含单词"ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"输出：false
提示：
1 <= board.length <= 200 1 <= board[i].length <= 200 board和word仅由大小写英文字母组成
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-j ...
剑指Offer II 076. 数组中的第 k 大的数字
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4
提示：
1 <= k <= nums.length <= 104 104 <= nums[i] <= 104
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/xx4gT2 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
求一个数列中的第k大的数，将前k个数建小顶堆，后面若比堆顶元素还小，则舍去，否则将堆顶置换成该元素，然后维护堆，最后输出堆顶元素。
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> least = new Pr ...
剑指Offer II 060. 出现频率最高的 k 个数字
给定一个整数数组nums和一个整数k，请返回其中出现频率k高的元素。可以按任意顺序返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]
示例 2:
输入: nums = [1], k = 1输出: [1]
提示：
1 <= nums.length <= 105 k的取值范围是[1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的
进阶：所设计算法的时间复杂度 必须 优于，其中是数组大小。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/g5c51o 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
使用HashMap先统计数字出现的次数。然后考虑使用大顶堆来统计前频繁出现的数字。
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = ...
剑指 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 ...