leetcode / Medium
4 分钟 读完 (大约 586 个字)

is-graph-bipartite

题目链接：is-graph-bipartite

题目描述

给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

题目分析

题目比较容易理解，我们只需要使用深搜或者广搜，将节点分成两部分，如果找到某个节点必须在两部分中同时出现，即该图不可二分。

算法

深度优先遍历（Depth-first-Search）

代码

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
class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[graph.length];   // 三色标记法，0表示该节点未划分，-1表示该节点在partA，1表示该节点在partB
        for (int i = 0; i < graph.length; i++) {
            // 遍历所有节点，对未划分的节点分入partB（因为该节点和之前划分的节点没有边相连，即无所谓partA和partB，这里选partB）
            if (colors[i] == 0 && !validColor(graph, colors, 1, i)) return false;
        }
        return true;
    }
    
    public boolean validColor(int[][] graph, int[] colors, int color, int node) {
        if (colors[node] != 0) {
            // 剪支，如果当前节点已经归类，则判断他是不是需要在两部分同时出现
            return colors[node] == color;
        }
        colors[node] = color;
        for (int j : graph[node]) {
            // 找到反例立刻返回
            if (!validColor(graph, colors, -color, j)) return false;
        }
        return true;
    }
    
    
}

宽度优先遍历（优化）（Breadth-first-Search）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[graph.length];
        
        for (int i = 0; i < graph.length; i++) {
            if (colors[i] != 0) continue;   // 以染色节点，迅速返回
            queue.offer(i);
            colors[i] = 1;  // 无所谓1或-1，这里选1
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int j : graph[cur]) {
                    // 一条边上另个节点和当前节点分类相同，即非二分图
                    if (colors[j] == colors[cur]) return false;
                    if (colors[j] == 0) {
                        colors[j] = -colors[cur];
                        queue.offer(j);
                    }
                }
            }
        }
        return true;
    }
}
leetcode / Medium
6 分钟 读完 (大约 948 个字)

all-nodes-distance-k-in-binary-tree

题目链接：all-nodes-distance-k-in-binary-tree

题目描述

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

题目分析

  1. 距离给定节点距离为K的节点有两种情况：第一种是他的子节点，这种情况比较容易通过遍历得到。第二种是他的祖先节点的其他子树，对于这种情况，我们需要能找到节点的祖先节点的方法。
  2. 找到某节点父节点的方法可有两种，一种是深搜回退到他的父节点，一种是建立子节点到父节点的映射。

算法

深度优先遍历（Depth-first-Search）

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result;
    int k;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        result = new ArrayList<>();
        k = K;
        dfs(root, target);
        return result;
    }

    public int dfs(TreeNode cur, TreeNode target) {
        if (cur == null) {
            return -1;            // 返回-1表示在当前子树没有找到目标节点
        }
        if (cur == target) {
            subtreeAdd(cur, 0); // 找到目标节点了，对目标节点子树进行查找
            return 1; // 返回他的父节点到目标节点距离
        } else {
            int d = dfs(cur.left, target);
            if (d != -1) {
                // 目标节点在左子树
                if (d == k) {
                    // 当前节点符合到目标节点距离，添加到结果集
                    result.add(cur.val);                    
                }
                subtreeAdd(cur.right, d + 1);  // 寻找当前节点右子树符合条件的节点
                return d + 1; // 返回当前节点父节点到目标节点的距离
            } else {
                d = dfs(cur.right, target);
                if (d != -1) {
                    // 目标节点在右子树
                    if (d == k) {
                        // 当前节点符合到目标节点距离，添加到结果集
                        result.add(cur.val);    
                    }
                    subtreeAdd(cur.left, d + 1);    // 寻找当前节点左子树符合条件的节点
                    return d + 1;   // 返回当前节点父节点到目标节点的距离
                }
            }
            return -1;  // 目标节点在当前子树不存在
        }
    }

    // 查找当前子树符合到目标节点距离的值，保存结果
    public void subtreeAdd(TreeNode cur, int d) {
        if (cur == null || d > k) {
            return;
        }
        if (k == d) {
            result.add(cur.val);            
        }
        subtreeAdd(cur.left, d + 1);
        subtreeAdd(cur.right, d + 1);
    }
}

宽度优先搜索（Breadth-first-Search）

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, TreeNode> child2parent = new HashMap<>();
        dfs(root, null, child2parent);  // 建立子节点到父节点的映射

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(target);
        queue.offer(null);  // 以null为到目标节点距离相同的节点集分割点

        HashSet<TreeNode> seen = new HashSet<>();   // 标记查找过的节点，保证入队节点距离目标节点的距离是逐渐增加的
        seen.add(target);
        seen.add(null);

        List<Integer> result = new ArrayList<>();   // 保存结果
        while (!queue.isEmpty()) {
            TreeNode tmp;
            if (K == 0) {
                // 到目标节点距离为K，将当前队列中所有节点集保存到结果，null节点是分割点
                while ((tmp = queue.poll()) != null) {
                    result.add(tmp.val);
                }
            } else {
                while ((tmp = queue.poll()) != null) {
                    // 遍历当前距离目标节点距离相等的所有节点，分别将他的父节点、左子节点、右子节点
                    // 入队（如果这些节点没有被标记过，即他们离目标节点的距离都是+1）
                    if (!seen.contains(tmp.left)) {
                        seen.add(tmp.left);
                        queue.offer(tmp.left);
                    }
                    if (!seen.contains(tmp.right)) {
                        seen.add(tmp.right);
                        queue.offer(tmp.right);
                    }
                    if (!seen.contains(child2parent.get(tmp))) {
                        seen.add(child2parent.get(tmp));
                        queue.offer(child2parent.get(tmp));
                    }
                }
                queue.offer(null); // null入队分割下次循环
                K--; // 目标距离-1
            }
        }
        return result;
    }
    
    public void dfs(TreeNode cur, TreeNode parent, Map<TreeNode, TreeNode> child2parent) {
        if (cur != null) {
            child2parent.put(cur, parent);
            dfs(cur.left, cur, child2parent);
            dfs(cur.right, cur, child2parent);
        }
    }
}
leetcode / Medium
5 分钟 读完 (大约 792 个字)

minesweeper

题目链接：minesweeper

题目描述

让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

  1. 如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’。
  2. 如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的方块都应该被递归地揭露。
  3. 如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。
  4. 如果在此次点击中，若无更多方块可被揭露，则返回面板。

题目分析

  1. 这里的相邻是上下左右和四个对角线，注意不是只有上下左右

算法

深度优先遍历（Depth-first-Search）

代码

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
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int row = click[0];
        int col = click[1];
        if (board[row][col] == 'M') board[row][col] = 'X';  // 踩雷直接返回
        else dfs(board, row, col);
        return board;
    }
    
    private void dfs(char[][] board, int row, int col) {
        if (isOutOfBoundary(board, row, col) || board[row][col] != 'E') return; // 越界或已经遍历过
        int mines = getNumOfMinesAround(board, row, col);
        if (mines == 0) {
            // 周围地雷数量为0，才会递归遍历
            board[row][col] = 'B';
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    dfs(board, row + i, col + j);
                }
            }
        } else {
            board[row][col] = (char)('0' + mines);
        }
    }
    
    // 获取周围地雷数量
    public int getNumOfMinesAround(char[][] board, int row, int col) {
        int result = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if ((i == j && i == 0) || isOutOfBoundary(board, row + i, col + j)) continue;
                if (board[row+i][col+j] == 'M') result++;
            }
        }
        return result;
    }
    
    // 判断是否越界
    public boolean isOutOfBoundary(char[][] board, int row, int col) {
        return row < 0 || row >= board.length || col < 0 || col >= board[0].length;
    }
}

广度优先遍历（Breadth-first-Search）

代码

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
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int row = click[0];
        int col = click[1]; 
        if (board[row][col] == 'M') {
            // 踩雷直接返回
            board[row][col] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(click);
        while (!queue.isEmpty()) {
            click = queue.poll();
            row = click[0];
            col = click[1];
            if (isOutOfBoundary(board, row, col) || board[row][col] != 'E') continue;   // 越界或已经遍历过
            int mines = getNumOfMinesAround(board, row, col);
            if (mines == 0) {
                // 周围地雷数量为0，入队遍历
                board[row][col] = 'B';
                for (int i = -1; i <= 1; i++) {
                    for (int j = -1; j <= 1; j++) {
                        queue.offer(new int[]{row + i, col + j});
                    }
                }
            } else {
                board[row][col] = (char)('0' + mines);
            }    
        }
        return board;
    }
    
    // 获取周围地雷数量
    public int getNumOfMinesAround(char[][] board, int row, int col) {
        int result = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if ((i == j && i == 0) || isOutOfBoundary(board, row + i, col + j)) continue;
                if (board[row+i][col+j] == 'M') result++;
            }
        }
        return result;
    }
    
    // 判断是否越界
    public boolean isOutOfBoundary(char[][] board, int row, int col) {
        return row < 0 || row >= board.length || col < 0 || col >= board[0].length;
    }
}
关注我

分类

标签云

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

×