7.18号刷题

发表于 | 分类于 | 0 comments

第一题 130. Surrounded Regions

题目描述

将所有被环绕的’O’变为‘X’，被环绕的定义是，所有相邻的’O’周围不靠近边界

算法

利用DFS对所有从边界开始的’O’进行探测，找出所有不环绕的’O’

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
public class solve130 {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                DFS(board, i, 0);
            if (board[i][n - 1] == 'O')
                DFS(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O')
                DFS(board, 0, j);
            if (board[m - 1][j] == 'O')
                DFS(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '*')
                    board[i][j] = 'O';
            }
        }
    }
    public void DFS(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1)
            return;
        if (board[i][j] == 'O')
            board[i][j] = '*';
        if (i - 1 >= 0 && board[i - 1][j] == 'O')
            DFS(board, i - 1, j);
        if (i + 1 < board.length - 1 && board[i + 1][j] == 'O')
            DFS(board, i + 1, j);
        if (j - 1 >= 0 && board[i][j - 1] == 'O')
            DFS(board, i, j - 1);
        if (j + 1 < board[0].length - 1 && board[i][j + 1] == 'O')
            DFS(board, i, j + 1);
    }
}

第二题 200. Number of Islands

题目描述

给定一个由字符‘1’（陆地）和‘0’（水域）组成的二维网格地图，计算岛屿的个数。岛屿被水域环绕，由竖直或者水平方向邻接的陆地构成。你可以假设网格地图的四条边都被水域包围。

测试样例见题目描述。

算法

与上题相似，DFS

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
public class numIslands200 {
    public int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] != '1')
            return;
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

第三题 305. Number of Islands II

题目描述

现在给定一个m * n的二维矩阵，和一系列的操作。具体操作是将一片海域变为陆地，并统计在每次操作后，岛屿的数量

算法

利用数组来代表一个树，points[newOperation] = ?如果是新的岛屿，那么树的根就是自己。如果不是新的岛屿，那么就让现在的point[newOperation] = FirstAddPosition，这样可以非常快速的检查每次加入的岛屿是否属于之前加入的岛屿中。比每次加入后做深度遍历要快很多

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
public class numIslands2305 {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        if (m <= 0 || n <= 0) return res;
        int[] points = new int[m * n];
        Arrays.fill(points, -1);
        int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        int count = 0;
        for (int[] point : positions) {
            int root = n * point[0] + point[1];
            points[root] = root;
            count++;
            for (int[] dir : dirs) {
                int x = dir[0] + point[0];
                int y = dir[1] + point[1];
                if (x < 0 || y < 0 || x >= m || y >= n || points[n * x + y] == -1)
                    continue;
                int rootNb = findRoot(points, n * x + y);
                if (root != rootNb) {
                    points[root] = rootNb;
                    root = rootNb;
                    count--;
                }
            }
            res.add(count);
        }
        return res;
    }
    public int findRoot(int[] points, int newroot) {
        while (newroot != points[newroot]) {
            points[newroot] = points[points[newroot]];
            newroot = points[newroot];
        }
        return newroot;
    }
}

第四题 261. Graph Valid Tree

题目描述

给定n个节点，以及他们之间边的关系（无向）,问是否这些节点能够组成一棵树

算法

利用Union and Find 进行求解，将所有已经在一起的节点归并到一个Set中。然后用find查看新进来的节点是否会形成图

关于Union and Find 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class validTree261 {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0) return false;
        int[] sets = new int[n];
        Arrays.fill(sets, -1);
        for (int[] edge : edges) {
            int x = findRoot(sets, edge[0]);
            int y = findRoot(sets, edge[1]);
            if (x == y) return false;
            sets[x] = y;
        }
        return edges.length == n - 1;
    }
    public int findRoot(int[] sets, int id) {
        if (sets[id] != -1) return findRoot(sets, sets[id]);
        return id;
    }
}

第五题 323. Number of Connected Components in an Undirected Graph

题目描述

对于n个节点，我们有任意条无向的边缘，求整个图中有几个独立不联通的区域

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class countComponents323 {
    public int countComponents(int n, int[][] edges) {
        int[] sets = new int[n];
        Arrays.fill(sets, -1);
        for (int[] edge : edges) {
            int x = findRoot(sets, edge[0]);
            int y = findRoot(sets, edge[1]);
            if (x == y) continue;
            sets[x] = y;
            n--;
        }
        return n;
    }
    public int findRoot(int[] sets, int id) {
        if (sets[id] == -1) return id;
        else return findRoot(sets, sets[id]);
    }
}
压缩路径后
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
public class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] sets = new int[n];
        for (int i = 0; i < n; i++) sets[i] = i;
        for(int[] edge : edges) {
            int rootF = findRoot(sets, edge[0]);
            int rootS = findRoot(sets, edge[1]);
            if (rootF != rootS) {
                n--;
                sets[rootF] = rootS;
            }
        }
        return n;
    }
    public int findRoot(int[] sets, int id) {
        while (sets[id] != id) {
            sets[id] = sets[sets[id]];
            id = sets[id];
        }
        return id;
    }
}

第六题 547. Friend Circles

题目描述

给定邻接矩阵M，求连通分量的个数。

注意：

  1. N的范围[1, 200]
  2. M[i][i] = 1
  3. 如果M[i][j] = 1，那么M[j][i] = 1

算法

依然用Union Find的办法

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
public class findCircleNum547 {
    public int findCircleNum(int[][] M) {
        int n = M.length, count = n;
        int[] sets = new int[n];
        for (int i = 0; i < n; i++) sets[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (M[i][j] == 1) {
                    int rootFirst = findRoot(sets, i);
                    int rootSecond = findRoot(sets, j);
                    if (rootFirst != rootSecond) {
                        sets[rootFirst] = rootSecond;
                        count--;
                    }
                }
            }
        }
        return count;
    }
    public int findRoot(int[] sets, int id) {
        while (sets[id] != id) {
            sets[id] = sets[sets[id]];
            id = sets[id];
        }
        return id;
    }
}
```   
    
### 第七题 [133. Clone Graph](https://leetcode.com/problems/clone-graph/tabs/description)
#### 题目描述
复制整个无向图
#### 算法
利用BFS，一个HashMap和Queue进行复制
如果是有向图，则需要两遍遍历，第一遍创建所有节点，第二遍复制。算法类似LinkedList
```java
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        UndirectedGraphNode newnode = new UndirectedGraphNode(node.label);
        map.put(node.label, newnode);
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for (UndirectedGraphNode neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor.label)) {
                    map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));
                    queue.offer(neighbor);
                }
                map.get(cur.label).neighbors.add(map.get(neighbor.label));
            }
        }
        return newnode;        
    }
}

第八题 207. Course Schedule

题目描述

一共有n门需要选择的课程，标号为0到n-1。

有些课程可能会有先修课程，例如想要选择课程0，必须首先选过课程1，可以表述为配对：[0,1]

给定课程总数和一组先修课程配对，判断是否可以修完所有的课程。

例如：

2, [[1,0]]

一共有2门备选课程。要选择课程1，必须先完成课程0。因此这是可能的。

2, [[1,0],[0,1]]

一共有2门备选课程。要选择课程1，必须先完成课程0，而要修课程0，必须修完课程1。因此这是不可能的。

算法

利用拓扑排序解决这个问题

两个链接帮助了解拓扑排序 链接一, 链接二

简而言之拓扑排序有三步

  1. 找寻入度为0的节点
  2. 将这个节点所有的向外的连线都删除
  3. 如果没有这样的节点，则返回，如果有则返回1循环
  4. 最后查看图中是否有剩余的入度不为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
public class canFinish207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];
        int[] poinToIt = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int pre = prerequisites[i][1];
            int after = prerequisites[i][0];
            if (matrix[pre][after] == 0)
                poinToIt[after]++;
            matrix[pre][after] = 1;
        }
        Queue<Integer> queue = new LinkedList<>();
        //Add all nodes that no node point to it
        for (int i = 0; i < numCourses; i++) {
            if (poinToIt[i] == 0)
                queue.offer(i);
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            //Remove all out point
            for (int i = 0; i < numCourses; i++) {
                if (matrix[cur][i] == 1) {
                    if (--poinToIt[i] == 0) {  // if there is no node point to it, add to queue
                        queue.offer(i);
                    }
                    matrix[cur][i] = 0;
                }
            }
        }
        return count == numCourses;
    }
}

第九题 210. Course Schedule II

题目描述

一共有n门需要选择的课程，标号为0到n-1。

有些课程可能会有先修课程，例如想要选择课程0，必须首先选过课程1，可以表述为配对：[0,1]

给定课程总数和一组先修课程配对，返回可以完成所有课程的选课顺序。

可能有多个正确的顺序，只需要任选其一即可。如果不可能完成所有的课程，返回一个空数组。

例如：

2, [[1,0]]

一共有2门备选课程。要选择课程1，必须先完成课程0。因此正确的课程顺序是[0,1]。

4, [[1,0],[2,0],[3,1],[3,2]]

一共有4门备选课程。要选择课程3，必须先完成课程1和2。而课程1和2都需要先修完课程0才能选。因此一种正确的课程顺序是[0,1,2,3]。另一个正确的顺序是[0,2,1,3]。

算法

仍然与前面的一题一样

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
public class findOrder210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses], inDegree = new int[numCourses];
        int[][] relationShip = new int[numCourses][numCourses];
        for (int[] prerequsite : prerequisites) {
            int pre = prerequsite[1];
            int next = prerequsite[0];
            if (relationShip[pre][next] == 0) {
                inDegree[next]++;
            }
            relationShip[pre][next] = 1;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                queue.offer(i);
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (count > numCourses - 1) return new int[0];
            res[count++] = cur;
            for (int i = 0; i < numCourses; i++) {
                if (relationShip[cur][i] == 1) {
                    if (--inDegree[i] == 0) {
                        queue.offer(i);
                    }
                    relationShip[cur][i] = 0;
                }
            }
        }
        return count == numCourses ? res : new int[0];
    }
}