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
5 分钟 读完 (大约 807 个字)

find-eventual-safe-states

题目链接：find-eventual-safe-states

题目描述

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。哪些节点最终是安全的？ 结果返回一个有序的数组。该有向图有 N 个节点，标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

题目分析

题目意思即找出非闭环的所有节点

  1. 我们可以从终点开始，即先找出那些没有出去的边的节点，即出度为0，这些节点一定符合条件，然后，反向搜索，找出他的上游，如果他的上游的所有出去的边都是在这些节点当中，则他的上游节点也是安全的。
  2. 我们还可以采用深搜的方式，对每个节点的所有出去的边进行搜索，如果他的所有下游节点都是安全的，则他也是安全的。

算法

反向边（Graph)

代码

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
class Solution {
    
    public List<Integer> eventualSafeNodes(int[][] G) {
        List<Set<Integer>> graph = new ArrayList<>();       // 正向边图
        List<Set<Integer>> rgraph = new ArrayList<>();      // 反向边图
        Queue<Integer> queue = new LinkedList<>();          // 安全节点队列
        List<Integer> result = new ArrayList<>();           // 返回结果集
        boolean[] safe = new boolean[G.length];             // 标记安全节点（因为返回结果要有序的，这里用空间换时间）
        
        // 图的初始化
        for (int i = 0; i < G.length; i++) {
            graph.add(new HashSet<Integer>());
            rgraph.add(new HashSet<Integer>());
        }
        for (int i = 0; i < G.length; i++) {
            for (int j : G[i]) {
                graph.get(i).add(j);
                rgraph.get(j).add(i);
            }
            if (G[i].length == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            // 安全节点集非空，出队并标记
            int i = queue.poll();
            safe[i] = true;
            for (int j : rgraph.get(i)) {
                // 移除上游节点到安全节点的边，如果上游节点的所有边都是到安全节点（即graph.get(j).isEmpty()），则入队
                graph.get(j).remove(i);
                if (graph.get(j).isEmpty()) queue.offer(j);
            }
        }
        // 读取标记，返回结果
        for (int i = 0; i < G.length; i++) {
            if (safe[i]) result.add(i);
        }
        return result;
    }
}

深度优先搜索（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
import java.util.*;

class Solution {
    // white表示未搜索，
    // black表示安全节点，
    // grey表示搜索中的节点或不安全节点
    enum Color {
        WHITE,
        BLACK,
        GREY,
    }
    
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> result = new ArrayList<>();
        if (graph.length == 0) return result;
        Color[] color = new Color[graph.length];
        Arrays.fill(color, Color.WHITE);
        for (int i = 0; i < graph.length; i++) {
            if (dfs(graph, i, color)) result.add(i);
        }
        return result;
    }
    
    public boolean dfs(int[][] graph, int i, Color[] color) {
        if (color[i] != Color.WHITE) return color[i] == Color.BLACK;        // 节点i被搜索过，剪支，快速返回
        color[i] = Color.GREY;          // 标记节点i在搜索中
        for (int child : graph[i]) {
            if (!dfs(graph, child, color)) return false;       
        }
        color[i] = Color.BLACK;         // 标记节点i安全
        return true;
    }
}
由斜杠划分区域
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;
    }
}
关注我

分类

标签云

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

×