简介

每刷过一道题目，把对于题目的分析记录在此，本篇不追求系统，做到什么想到什么都写在这里。好记性不如烂笔头，主要原因是本人记性比较差。

果然每接触一道就得记一道，昨天刷了好多不想记，隔了一天之后绝对不会主动回去找那些题了。

我发现一篇文章记录下刷过的有趣的题目实在是太长了，还是拆分为多篇文章，以题目类型作为分类吧。

分类

哈希等价多米诺骨牌的数量字符串：力扣题型笔记 - 字符串类图岛屿数量由斜杠划分区域保证图可完全遍历最小体力消耗路径树二叉树的右视图集合等式方程可满足性查找：力扣题型笔记 - 查找类其他数组中的逆序对提示除非题目提示是原地算法，否则不要修改传入的数据。对于传入的引用类型数据，除非题目提及，不得对该数据进行修改，即使很多官方题解也这么做，但不值得学习。这一点不是对于刷题而言，而是对于开发而言。规范的开发必须保证数据的安全性，作为参数传进来的数据应当作为数据源而不应当作为中间数据。

在开发中，如果你的 API 对传入的数据进行了修改并且你的接口文档没有提及，调用方依照惯例把一个不可变的数据传入 API，得到正确的结果，但该数据的结构或者内容发生改变，整体系统就出现了隐患。

尤其是将对象的私有数据域或者 final 域传入 API 时，虽然这样做传入者本身操作有引用泄露的嫌疑，但是开发者必须秉持考虑一切情况的理念进行开发。因此，请不要为了节省内存而牺牲系统的健壮性。看题目第一步读题意，第二步问范围，第三步看要求。一切没有告知范围的题目，都应该以最大程序可以接受的量级来考虑。对一切数组或集合类型参数，第一步是进行 null 判断和空元素判断。同理，null 判断是对于开发而言而非对于刷题而言，而空元素判断则是刷题也需要注意的。虽然对参数判 null 对于刷题可有可无，但是出于养成好习惯的目的，基本上我都会习惯带上的。对于需要用到比较整型规则的题目，请使用 Integer.compare(o1, o2)因为整型存在溢出问题，Integer.MIN_VALUE - Integer.MAX_VALUE 本应为负数，但是溢出后结果为 1。

Integer.MIN_VALUE = 0b10000000_00000000_00000000_00000000Integer.MAX_VALUE = 0b01111111_11111111_11111111_11111111~ (MAX_VALUE) + 1 = 0b10000000_00000000_00000000_00000001 // 负数补码等于原码取反加一。+                 = 0b00000000_00000000_00000000_00000001 = 1

因此，如果使用(o1, o2) -> o1 - o2 的方式判断顺序，将会发生错误。取反或者取绝对值请考虑 Integer.MIN_VALUE。由于整型溢出，-Integer.MIN_VALUE 或 Math.abs(Integer.MIN_VALUE) 的结构都将是它自身。题目难度进阶数组变更为无限流对于数组统计类型的题目，通常进阶难题都可以思考：将数组转化为内存无法放下的无限流，该如何处理。哈希

利用映射解决问题的题目。

题目等价多米诺骨牌对的数量

等价多米诺骨牌对数量：本质上就是求相同无序偶对的数量。思路非常简单，分为两步：

如何将无序偶用相同的元素表示。

由于无序偶中的元素都是 1 ~ 9，所以无序偶可以直接转化为一个相同的数，例如对于 [1,2] 和 [2,1]，转化为 12 表示该无序偶 (1,2)(1,2)，规则是小的在前大的在后，小的做十位。记录无序偶对出现的次数。

无序偶的唯一表示确定了，可以做 Key，所以之前出现过的次数做 value 记录起来即可。每遍历到某无序偶，此前该元素出现的次数即是当前元素可以组成的无序偶对的数量。数组数据结构：一维整型数组，大小为 100100，因为所有无序偶中的元素都是 1 ~ 9，因此最小的无序偶可以表示为 11，最大的无序偶为 99。时间复杂度：O(n)O(n)空间复杂度：O(1)O(1)注意点：没必要用哈希表做，Key 都是唯一的，且范围小于 100，无需映射。图

图类算法题

提示对于 Flood Fill 操作，推荐使用深度优先搜索DFS 相较于 BFS，可以写成递归的形式，更为美观。对于调用栈而言，一般都会有优化，注意不要造成 StackOverFlowError。对于二维矩阵图的遍历，上下左右可以使用方向数组的方式实现通常我们遇到要上下左右探索的矩阵，我们往往需要写四个 if，如：

if (y + 1 < graph[x].length && needToSearch(graph[x][y + 1])) dfs(graph, x, y + 1);if (x + 1 < graph.length    && needToSearch(graph[x + 1][y])) dfs(graph, x + 1, y);if (y - 1 > -1              && needToSearch(graph[x][y - 1])) dfs(graph, x, y - 1);if (x - 1 > -1              && needToSearch(graph[x - 1][y])) dfs(graph, x - 1, y);

如果需要加入其他判断情况，会导致代码重复比较多，可以使用方向数组的方式简化该操作：

int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};for (int[] direction: directions) {    int tmpX = x + direction[0], tmpY = y + direction[1];    if (tmpX > -1 && tmpX < graph.length && tmpY > -1 && tmpY < graph[tmpX].length && needToSearch(graph[tmpX][tmpY]))        dfs(graph, tmpX, tmpY);}

题目岛屿数量

岛屿数量：开局一张图，0、1 做字符，1 代表陆地，0 代表海水，求岛屿数量。

因为岛是连在一起的陆地，所以思路很简单，和玩迷雾类游戏一样，每找到一块陆地，就遍历它的周围，将与它连着的土地找出来，就算找到一座岛。

深度优先搜索数据结构：二维布尔数组，记录已经访问过的陆地。时间复杂度：O(n \times m)O(n×m)，深度优先搜索相当于遍历所有结点一次。空间复杂度：O(n \times m)O(n×m)，一个 n \times mn×m 的二维布尔数组，还有深度优先搜索用到的栈深度。注意点：两个 for 循环终止条件不要写成一样的，这不是正方形矩阵。广度优先搜索数据结构：二维布尔数组，记录已经访问过的陆地。时间复杂度：O(n \times m)O(n×m)空间复杂度：O(n \times m)O(n×m)，一个 n \times mn×m 的二维布尔数组，还有广度优先搜索用到的队列。注意点：不知为何，这道题广度优先搜索的非本地方法写法会超出时间限制。并查集数据结构：并查集时间复杂度：O(n \times m \times \alpha(n \times m))O(n×m×α(n×m))，遍历一遍图以初始化并查集，对于每一对接壤的陆地进行 union 操作时，需要使用 find 查询所属集合根节点，查询次数由反阿克曼函数 \alpha(n \times m)α(n×m) 决定。空间复杂度：O(n \times m)O(n×m)，并查集中的维护所有集合根节点的 parent 数组。注意点：不需要 visited 二维布尔数组记录访问过的元素，不需要对 grid 进行操作记录合并过的陆地，不需要上下左右四个方向进行 union 操作，只需要对右、下两个方向接壤的陆地进行 union 操作，即可保证不会漏掉未合并的土地。

class Solution {    public int numIslands(char[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0)            return 0;        UnionFind unionFind = new UnionFind(grid);        for (int i = 0; i < grid.length; i++) {            for (int j = 0; j < grid[0].length; j++) {                if (grid[i][j] == '0')                    continue;                if (j + 1 < grid[i].length && grid[i][j + 1] == '1')                     unionFind.union(i * grid[0].length + j, i * grid[i].length + j + 1);                if (i + 1 < grid.length    && grid[i + 1][j] == '1')                     unionFind.union(i * grid[0].length + j, (i + 1) * grid[i + 1].length + j);             }        }        return unionFind.count;    }    private static class UnionFind {        int count;        int[] parent;        public UnionFind(char[][] grid) {            count = 0;            int col = grid.length, row = grid[0].length;            parent = new int[col * row];            for (int i = 0; i < grid.length; i++) {                for (int j = 0; j < grid[0].length; j++) {                    if (grid[i][j] == '0') continue;                    count++;                    parent[i * row + j] = i * row + j;                }            }        }        private int find(int n) {            return parent[n] == n ? n : find(parent[n]);        }        public void union(int a, int b) {                        int aSet = find(a), bSet = find(b);            if (aSet == bSet) return;            parent[aSet] = parent[bSet];            count--;        }    }}

由斜杠划分区域

由斜杠划分区域：非常有意思的题目，第一眼都能想到是要求连通分量，但是被分割的图形会让人措手不及。题目的关键点就在于如何将被分割的区域表示出来。

直接通过分类讨论算是不可能的，此处引入先分后合的思想，将 、\、/ 这三种情况转化为同一条件下的不同分割方法，使得极其复杂的组合变得规律可循：

先拆后合 + 并查集数据结构：并查集时间复杂度：O(n) \times \alpha(n)O(n)×α(n)，输入矩阵遍历时间乘以并查集 find 平均耗时。空间复杂度：O(n)O(n)，并查集维护是输入矩阵四倍大小的数组。注意点：分：注意矩阵中每一个字符拆分为四个部分之后的下标计算。合：合包括两种情况，一是同一字符内的合并，二是相邻字符间的合并。保证图可完全遍历

保证图可完全遍历：同时构造两棵生成树，是非常发挥并查集性质的一道题，难得主要是思维，实现的过程中有一些小细节要求。

private void find(int n) {    return parent[n] == n ? n : (parent[n] = find(parent[n]));}

最小体力消耗路径

最小体力消耗路径：考察图的寻路，图的路径权重有各种各样的表达方式，由于这道题路径权重的表示比较特殊，因此可以用并查集做。

优先队列

从起点出发对图进行遍历，每次选择所有可遍历路径中权重最小的一条，采用优先队列自动维护待遍历边顺序。数据结构：优先队列。时间复杂度：O(nm \times \log(mn))O(nm×log(mn))，利用优先队列对图进行遍历，排序消耗 log(m\times n)log(m×n)。空间复杂度：$O(mn)，优先队列的占用空间。注意点：无。并查集

将所有结点加入并查集中。获取所有边，对所有边依据权重进行排序，每次选择最小的边，在并查集中连接该边左右两点。当起点和终点处于同一集合时，最后所加的边即为结果。数据结构：并查集。时间复杂度：O(nm \times \log(mn))O(nm×log(mn))。空间复杂度：O(nm)O(nm)，维护一个边集和并查集。注意点：无。二分查找

不会，对图不喜欢用二分。树

就是特殊的图，不过由于树具有更多具体的特性，因此不和图混淆在一块

题目二叉树的右视图

二叉树的右视图：从二叉树的右边看它，然后把它的侧面输出出来。较为直观的是使用广度优先搜索，因为 BFS 是一层一层来的。对于深度优先搜索的话，就需要我们传递一个变量给 DFS，让他来判断是不是右边了。

广度优先搜索数据结构：队列时间复杂度：O(n)O(n)空间复杂度：O(n)O(n)注意点：没什么好注意的。原理是每次入队都是一层一层入，最后或者第一个入的就是右侧结点。

private void dfs(TreeNode node, int level, List<Integer> answer) {    if (node == null) return;    if (level == answer.size()) answer.add(node.val);    dfs(node.right, level + 1, answer);    dfs(node.left,  level + 1, answer);}

集合

使用集合的思想和解法解决的题目

题目等式方程可满足性

等式方程可满足性：相等则表示属于同一集合，不相等则表示是不同集合。就这么直观。

并查集数据结构：并查集，同一集合的元素使用并查集进行判断最为方便。时间复杂度：$O(n \times \alpha(26))，由于并查集的大小仅 26 个字母，因此 find 函数数量级固定。空间复杂度：O(1)O(1)，并查集维护的数组长度为 26。注意点：使用两次遍历而非一次遍历，第一次遍历所有等式，建立集合的关系。第二次遍历所有不等式，一旦发现不等号两端的操作数属于同一集合，即可返回 false。注意并非参数数组长度为 1 就一定是正确的，因为有可能是这种形式 ["a!=a"] 。其他

指一些看似寻常，但是非常有意思，非常巧妙的题目。

数组中的逆序对

数组中的逆序对：求数组中逆序对的数量。

private int mergeSort(int[] nums, int l, int r) {    if (r - l == 1) return 0;    int mid = l + (r - 1 - l >> 1), count = 0;    count += mergeSort(nums, l, mid + 1);    count += mergeSort(nums, mid + 1, r);    int[] tmp = new int[r - l];    int lCur = l, rCur = mid + 1, cur = 0;    while (lCur <= mid && rCur < r) {        if (nums[rCur] < nums[lCur]) {            count += mid - lCur + 1; // 左边剩多少，就是右边当前元素贡献的逆序对            tmp[cur++] = nums[rCur++];        } else            tmp[cur++] = nums[lCur++];    }    while (lCur <= mid) tmp[cur++] = nums[lCur++];    while (rCur < r)    tmp[cur++] = nums[rCur++];    System.arraycopy(tmp, 0, nums, l, r - l);    return count;}

如果本文对你有帮助，别忘记给我个3连 ，点赞，转发，评论，

咱们下期见。

原文