leetcode / Medium
5 分钟 读完 (大约 765 个字)

移除最多的同行或同列石头

题目链接：most-stones-removed-with-same-row-or-column

题目描述

在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。我们最多能执行多少次 move 操作？

题目分析

  1. 刚开始看到这道题目的时候，一脸蒙蔽，不是很明白最多move操作的意思，然后把示例画成二维图，试了一下，终于明白，这道题目的意思是，让最终每行每列上最多只能有一块石头，最少剩下多少块石头，然后返回原石头数量-剩余石头数量。
  2. 很显然，这道题目可以使用深度优先搜索和并查集的方法。我们可以将每行每列定义为一个component，将有石头相连的component合并成一个（并查集的方法），最后在统计有多少个独立的component，即剩下的石头数量；也可以对每块石头所在的component执行一个深度优先遍历，最后统计有从入口执行了多少次，即剩下的石头数量。

算法

深度优先遍历（Depth-first-Search,time: O(N2),memory：O(N）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;

class Solution {
    
    public int removeStones(int[][] stones) {
        int N = stones.length;
        
        // 这里无所谓行和列的概念，我们将行和列都当做一个component，
        // graph[i][0]记录了第i块石头的邻居数量。
        int[][] graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                // 两块石头在同一行或同一列，将他们记录为邻居
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    graph[i][++graph[i][0]] = j;
                    graph[j][++graph[j][0]] = i;
                }
            }
        }
        

        boolean[] seen = new boolean[N];    // 深搜遍历过的标志，避免死循环
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (!seen[i]) {
                seen[i] = true;
                Stack<Integer> stack = new Stack<>();
                ans--;
                stack.push(i);
                while (!stack.isEmpty()) {
                    int cur = stack.pop();
                    ans++;
                    // 将该块石头的所有邻居推入栈
                    for (int j = 1; j <= graph[cur][0]; j++) {
                        if (!seen[graph[cur][j]]) {
                            seen[graph[cur][j]] = true;
                            stack.push(graph[cur][j]);
                        }
                    }
                }
            }
        }
        return ans;
    }
        
}

并查集（Union-Find,time: O(NlogN),memory：O(N）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

class Solution {
    
    public int removeStones(int[][] stones) {
        int N = stones.length;
        DSU dsu = new DSU(20000);
        // 将这块石头所在行和列合并成一个component
        // 最终，能合并在一起的石头会拥有同样的parent
        for (int i = 0; i < N; i++) dsu.union(stones[i][0], stones[i][1] + 10000);
        
        HashSet<Integer> seen = new HashSet<>();
        // 遍历所有的石头，找出它的父节点，即最后剩余的最少石头数量。
        for (int i = 0; i < N; i++) seen.add(dsu.find(stones[i][0]));
        return N - seen.size();
    }
    
    class DSU {
        int[] parent;
        
        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        public int find(int p) {
            if (parent[p] != p) parent[p] = find(parent[p]);
            return parent[p];
        }
        
        public void union(int p, int q) {
            parent[find(p)] = find(q);
        }
    }
        
}
leetcode / Medium
3 分钟 读完 (大约 516 个字)

飞地的数量

题目链接：number-of-enclaves

题目描述

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

题目分析

  1. 这道题其实和leetcode上岛屿的数量那道题目很类似，不同点在于连接到边界的岛屿不计入数量，并且这里要计算的是岛屿的面积（1的数量），不是岛屿的面积。
  2. 我们应该从边界开始遍历，要把能连接到边界的陆地1转化成用-1表示（像是地理上的半岛），最后，在重新遍历地图，数出1的数量。

算法

深度优先遍历（Depth-first-Search,time: O(M * N),memory：O(M*N）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };    // 四个方向，上下左右
    
    public int numEnclaves(int[][] A) {
        int ans = 0;

        for (int row = 0; row < A.length; row++) {
            for (int col = 0; col < A[0].length; col++) {
                // 当在边界且边界这里是陆地（即1）的时候，往下深搜，把连接到这块陆地的所有陆地转化为半岛（-1）
                if (isBoundary(A, row, col) && A[row][col] == 1) {
                    dfs(A, row, col);
                }
            }
        }
        
        // 计算岛屿的面积
        for (int row = 0; row < A.length; row++)
            for (int col = 0; col < A[0].length; col++)
                if(A[row][col] == 1) ans++;
        return ans;
    }
    
    
    private void dfs(int[][] A, int row, int col) {
        // 超出地图边界或者非陆地或者已经遍历过的陆地，直接返回
        if (outOfBoundary(A, row, col) || A[row][col] == 0 || A[row][col] == -1) return;
        // 将该陆地标记为岛屿，并遍历
        A[row][col] = -1;
        for (int[] dir : dirs) {
            dfs(A, row + dir[0], col + dir[1]);
        }
    }
    
    // 判断地图边界
    private boolean isBoundary(int[][] A, int row, int col) {
        return row == 0 || row == A.length - 1 || col == 0 || col == A[0].length - 1;
    }
    
    // 判断是否超出地图边界
    private boolean outOfBoundary(int[][] A, int row, int col) {
        return row < 0 || row > A.length - 1 || col < 0 || col > A[0].length - 1;
    }
    
}
由斜杠划分区域
leetcode / Medium
8 分钟 读完 (大约 1259 个字)

由斜杠划分区域

题目链接：regions-cut-by-slashes

题目描述

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。（请注意，反斜杠字符是转义的，因此 \ 用 “\“ 表示。）。返回区域的数目。

题目分析

  1. 该题目用用图来表示的话，一目了然。可是表示成了字符串之后，就感觉有点不知从何处下手。
  2. 想办法将图形表示转化成直观的数组表示法。

算法

并查集（Union Find）

由于每个小区域只填充’/‘或者’'，因此，小区域划分最多有三种情况（编号如上图所示）：

  1. 编号0和编号1在同一个块，编号2和编号3在同一个块。
  2. 编号0和编号2在同一个块，编号1和编号3在同一个块。
  3. 编号0， 1， 2， 3都在同一个块。

相邻区域间，他们的编号小区域存在一定会在同一个块的情况。其中：

  1. 编号0和上一个区域编号3一定在同一个块。
  2. 编号1和左边区域的编号2一定在同一个块。
  3. 编号2和右边区域的编号1一定在同一个块。
  4. 编号3和下边区域的编号0一定在同一个块。

我们开始给每个小区域编一个唯一的块号，通过遍历区域，达到数出全部唯一块的数目。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    private int[] grids;            // 用数组来表示块编号
    private int num;                // 统计唯一块的数目
    
    public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        buildUnionFind(N);
        
        // 遍历合并所有的区域
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[r].length(); c++)
                process(r, c, N, grid[r].charAt(c));
        return num;
    }
    
    // 构建并查集，初始每个块有一个唯一编号
    private void buildUnionFind(int N) {
        grids = new int[N * N * 4];
        num = N * N * 4;
        for (int i = 0; i < grids.length; i++) grids[i] = i;
    }
    
    // 根据行和列的序号，得到块在数组中的位置
    private int getSubSquare(int r, int c, int N, int ith) {
        return r * N * 4 + c * 4 + ith;
    }
    
    // 寻找块的根编号
    private int find(int p) {
        while (grids[p] != p) {
            grids[p] = grids[grids[p]];
            p = grids[p];
        }
        return p;
    }
    
    // 合并两个块
    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP != rootQ) num--;      // 如果两个块拥有不同的编号，合并后，唯一块的数目减1
        grids[rootP] = rootQ;
    }
    

    private void process(int r, int c, int N, char square) {
        // 获取区域中四个小区域的块编号
        int s0 = getSubSquare(r, c, N, 0);
        int s1 = getSubSquare(r, c, N, 1);
        int s2 = getSubSquare(r, c, N, 2);
        int s3 = getSubSquare(r, c, N, 3);
        
        // 同一个区域的小区域合并
        switch(square) {
            case '\\':
                union(s0, s2);
                union(s1, s3);
                break;
            case '/':
                union(s0, s1);
                union(s2, s3);
                break;
            default:
                union(s0, s1);
                union(s1, s2);
                union(s2, s3);
        }

        // 相邻区域的合并
        if (r > 0) {
            union(s0, getSubSquare(r - 1, c, N, 3));
        }
        if (r < N - 1) {
            union(s3, getSubSquare(r + 1, c, N, 0));
        }
        if (c > 0) {
            union(s1, getSubSquare(r, c - 1, N, 2));
        }
        if (c < N - 1) {
            union(s2, getSubSquare(r, c + 1, N, 1));
        }
    }
}

深度优先搜索（Depth first Search）

我们很难从原图中，将该图转化成一个用数字表示的数组。但是，当我们将原图表示成一个规模*2的数组时，他将可以表示如下：

1
2
3
4
                        0 1 0 1
["//", "/ "]    =>      1 0 1 0
                        0 1 0 0
                        1 0 0 0

我们将数字1当做一道墙，数字0当做一个空白块，则没有墙相隔的块，他们属于同一个唯一块。从上数字中，我们可以直观的看出，一共存在3个唯一块。但是这时，属于同一个唯一空白块的小空白块他们可能还不相邻（即在斜对角线上）。我们再把原图表示成一个规模*3数组，表示如下：

1
2
3
4
5
6
                        0 0 1 0 0 1
                        0 1 0 0 1 0
["//", "/ "]    =>      1 0 0 1 0 0
                        0 0 1 0 0 0
                        0 1 0 0 0 0
                        1 0 0 0 0 0

这时，可以清楚的看出，一共存在3个唯一空白块，且在同一个唯一空白块的所有小空白块，都是相邻的了。这个时候，我们就可以采用深度优先搜索，从数组的边界开始，遍历存在多少个不相邻的0，即可得到答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int[][] grids;          // 表示原图的数组
    
    public int regionsBySlashes(String[] grid) {
        buildGrids(grid);
        int count = 0;
        // 深搜遍历
        for (int r = 0; r < grids.length; r++) {
            for (int c = 0; c < grids[r].length; c++) {
                count += dfs(r, c);
            }
        }
        return count;
    }
    
    // 将原图表示成规模*3的数组
    private void buildGrids(String[] grid) {
        int N = grid.length;
        grids = new int[N * 3][N * 3];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length(); j++) {
                if (grid[i].charAt(j) == '/') {
                    grids[i * 3 + 2][j * 3] = 1;
                    grids[i * 3 + 1][j * 3 + 1] = 1;
                    grids[i * 3][j * 3 + 2] = 1;
                } else if (grid[i].charAt(j) == '\\') {
                    grids[i * 3][j * 3] = 1;
                    grids[i * 3 + 1][j * 3 + 1] = 1;
                    grids[i * 3 + 2][j * 3 + 2] = 1;
                }
            }
        }
    }
    
    private int dfs(int r, int c) {
        // 越界返回0
        if (r < 0 || r >= grids.length || c < 0 || c >= grids[r].length) return 0;
        // 遇到墙（数字1）返回0
        if (grids[r][c] == 1) return 0;
        
        // 将空白块改为1，并向他四周遍历，结果返回1
        grids[r][c] = 1;
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
        return 1;
    }
}
在二叉树中分配硬币
leetcode / Medium
7 分钟 读完 (大约 998 个字)

在二叉树中分配硬币

题目链接：distribute-coins-in-binary-tree

题目描述

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。返回使每个结点上只有一枚硬币所需的移动次数。

题目分析

  1. 要使得硬币移动次数最少，我们应该把结点中多余的硬币移到离它最近且需要硬币的结点上。
  2. 由于是在二叉树上移动，则硬币移动轨迹一定是从某结点移动到他的父节点或者子节点上。
  3. 从需要硬币的结点到有多余硬币的结点的距离等于从有多余硬币结点的距离到需要硬币的结点的距离。
  4. 一个结点可能有两个子节点，因此，如果该结点需要硬币或者有多余的硬币，我们无法一下子确定该硬币应该从左子节点还是右子节点获得或者移向左子节点还是右子节点；而一个结点一定只有一个父节点，因此，如果该结点需要硬币或者有多余的硬币，移动轨迹一定会经过他的父节点。

算法分析

采用深度搜索优先的思路，从树的叶子节点出发，如果该结点（设为cur）需要硬币，则从他的父节点获得，如果该结点有多余的硬币，则多余的硬币全部移动向他的父节点。即该结点的初始值为cur.val,从该结点递归到他的父节点，移动次数增加Math.abs(cur.val - 1)。该结点cur.val变为期待的1，如果该结点的值cur.val > 1，则他的父节点的的值cur.parent.val = cur.parent.val + cur.val - 1;如果该结点的值cur.val <= 1,则他的父节点的的值cur.parent.val = cur.parent.val - (-cur.val + 1)。逐步递归，直到遍历完整棵树，则可得出结果。

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int moves = 0;      // 记录移动次数
    
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }
    
    // 该方法返回值为移动完成后结点cur拥有多余的或者缺少的硬币数量，即cur.val - 1。
    public int dfs(TreeNode cur) {
        if (cur == null) return 0;
        int l = dfs(cur.left);
        int r = dfs(cur.right);
        moves += Math.abs(l) + Math.abs(r);         // 总结果加上左右子节点硬币流向父节点或从父节点移动过去需要的次数
        return cur.val + l + r - 1;         // 当前结点缺少的的或者多余的硬币数量
    }
    
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public int distributeCoins(TreeNode root) {
        return dfs(root, null);
    }
    
    // 该方法返回值为移动好当前结点（包括他的子节点，即当前结点表示的树）需要的移动次数
    public int dfs(TreeNode cur, TreeNode parent) {
        if (cur == null) return 0;
        int l = dfs(cur.left, cur);
        int r = dfs(cur.right, cur);
        
        int result = l + r;         // 移动好左右子树需要的移动次数
        // 修改当前结点父节点的硬币值
        if (cur.val < 1) {
            // 当前结点硬币值小于1，从父节点移动硬币到当前结点,父节点硬币数量减少
            result += (1 - cur.val);
            parent.val -= (1 - cur.val);
        } else if (cur.val > 1) {
            // 当前结点硬币值大于1，将多余的硬币值移动到父节点，父节点硬币数量增加
            result += (cur.val - 1);
            parent.val += (cur.val - 1);
        }
        return result;
    }
    
}
关注我

分类

标签云

Bit-Manipulation Breadth-first-Search Depth-first-Search Dynamic-Programming Graph Stack Tree Union-Find

最新文章

归档

标签

Bit-Manipulation 1
Breadth-first-Search 3
Depth-first-Search 14
Dynamic-Programming 1
Graph 3
Stack 1
Tree 3
Union-Find 3

最新文章

归档

标签

Bit-Manipulation 1
Breadth-first-Search 3
Depth-first-Search 14
Dynamic-Programming 1
Graph 3
Stack 1
Tree 3
Union-Find 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×