7.19号刷题

发表于 | 分类于 | 0 comments

第一题 286. Walls and Gates

题目描述

在一个二维矩阵中，有0，-1，Integer.MaxValue三种数字，分别表示了入口，墙壁，空区域。

现在需要求从0到这些空区域的最小距离分别是多少

算法

如果DFS暴力求解，将会超时。因此，我们采用BFS进行求解

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
public class wallsAndGates286 {
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0 || rooms[0].length == 0) return;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                if (x < 0 || y < 0 || x >= rooms.length || y >= rooms[0].length || rooms[x][y] != Integer.MAX_VALUE)
                    continue;
                queue.offer(new int[]{x, y});
                rooms[x][y] = rooms[cur[0]][cur[1]] + 1;
            }
        }
    }
}

第二题 317. Shortest Distance from All Buildings

题目描述

在一个二维矩阵，有三个数0表示空白区域，1表示房子，2表示障碍。在区域中求一个点，使得到所有房子距离最近

算法

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
public class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length, buildingNum = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[][] distance = new int[m][n];
        int[][] reached = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    buildingNum++;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    boolean[][] visited = new boolean[m][n];
                    int dis = 1;
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        for (int k = 0; k < size; k++) {
                            int[] cur = queue.poll();
                            for (int[] dir : dirs) {
                                int x = cur[0] + dir[0];
                                int y = cur[1] + dir[1];
                                if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 0 || visited[x][y])
                                    continue;
                                distance[x][y] += dis;
                                reached[x][y]++;
                                visited[x][y] = true;
                                queue.offer(new int[]{x, y});
                            }
                        }
                        dis++;
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && reached[i][j] == buildingNum)
                    res = Math.min(res, distance[i][j]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

第三题 301. Remove Invalid Parentheses

题目描述

移除最小数量的无效括号，使得输入字符串有效。返回所有可能的结果。

注意：输入字符串除了左右小括号外，还可能包含字母。

测试样例见题目描述。

算法

主要思路：

如果）多于（，那么我们需要删除一个），删除的位置只要是前面的任意一个位置即可。但是，如果有两个或两个以上连续的））那么，我们发现不管删除哪一个，都会得到同样的结果。因此，我们只删除第一个

对于（多于）的情况，我们从右边往左看，其实效果是相同的。这样，通过回溯，我们便可以得到最后的答案

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 removeInvalidParentheses301 {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        remove(s, 0, 0, new char[]{'(', ')'}, ans);
        return ans;
    }
    //pars = (,) or ),(
    public void remove(String s, int last_i, int last_j, char[] pairs, List<String> ans) {
        int stack = 0;
        for (int i = last_i; i < s.length(); i++) {
            if (s.charAt(i) == pairs[0]) stack++;
            if (s.charAt(i) == pairs[1]) stack--;
            if (stack >= 0) continue;
            for (int j = last_j; j <= i; j++) {
                if (s.charAt(j) == pairs[1] && (j == last_j || s.charAt(j - 1) != pairs[1])) {
                    remove(s.substring(0, j) + s.substring(j + 1),i, j, pairs, ans);
                }
            }
            return;
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if (pairs[0] == '(')
            remove(reversed, 0, 0, new char[]{')', '('}, ans);
        else
            ans.add(reversed);
    }
}

第四题 310. Minimum Height Trees

题目描述

对于一棵无向树，我们可以选择它的任意节点作为根。得到的结果就是有根树。在所有可能的有根树中，高度最小的称为最小高度树（MHT）。给定一个无向图，编写函数找出所有的最小高度树，并返回其根标号的列表。

格式：

图包含n个节点，标号为0到n-1。给定数字n以及一列无向边（每条边用一对标号表示）

你可以假设边没有重复。由于所有边都是无方向的，因此[0, 1]与[1, 0]是等价的。因而它们不会同时出现在边集合中。

测试用例如题目描述。

提示：

最多可能存在多少个MHT？

注意：

(1) 根据维基百科的定义：“一棵树是一个满足这样性质的无向图：任意两个节点之间只存在一条路径相连。或者说，任意不包含简单环路的连通图叫做树”。

(2) 有根树的高度为从根部到叶子节点的路径中最长的那一条的边数。

算法

主要思路是每一回合吃掉所有的叶节点，即出度为1的节点。这样就相当于所有叶节点向中央同时推进了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
public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        List<Set<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < n; i++) neighbors.add(new HashSet<>());
        for (int[] edge : edges) {
            neighbors.get(edge[0]).add(edge[1]);
            neighbors.get(edge[1]).add(edge[0]);
        }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (neighbors.get(i).size() == 1) leaves.add(i);
        }
        while (n > 2) {
            n -= leaves.size();
            List<Integer> temp = new ArrayList<>();
            for (int leave : leaves) {
                int neighbor = neighbors.get(leave).iterator().next();
                neighbors.get(neighbor).remove(leave);
                if (neighbors.get(neighbor).size() == 1) temp.add(neighbor);
            }
            leaves = temp;
        }
        return leaves;        
    }
}

第五题 529. Minesweeper

题目描述

给定2维字符矩阵board，’M’表示未挖到的地雷，’E’表示未挖到的空地。’B’表示已经挖到的、四周（上下左右以及对角线）没有地雷的空地。数字’1’到’8’表示四周包含相应数字的地雷，’X’表示挖到地雷。

给定下一次鼠标点击的位置（只在’M’或者’E’处点击），根据如下规则返回点击之后的board：

如果挖到’M’，则将其变成’X’，游戏结束

如果挖到四周没有地雷的’E’，将其变成’B’，并递归地挖开其相邻无雷区域

如果挖到四周包含地雷的’E’，将其替换为四周地雷的数目

算法

三种情况：

  1. 如果是雷，返回
  2. 如果是空白，周围有雷，返回数字
  3. 如果是空白，周围无雷，则课推进返回周围的

如果使用DFS，则回溯click函数本身。如果使用BFS，则用queue存储下所有要点击的位置

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
public class updateBoard529 {
    public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length, n = board[0].length;
        int row = click[0], col = click[1];
        if (board[row][col] == 'M') { // Mine
            board[row][col] = 'X';
        }
        else { // Empty
            // Get number of mines first.
            int count = 0;
            for (int i = -1; i < 2; i++) {
                for (int j = -1; j < 2; j++) {
                    if (i == 0 && j == 0) continue;
                    int r = row + i, c = col + j;
                    if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                    if (board[r][c] == 'M' || board[r][c] == 'X') count++;
                }
            }
            if (count > 0) { // If it is not a 'B', stop further DFS.
                board[row][col] = (char)(count + '0');
            }
            else { // Continue DFS to adjacent cells.
                board[row][col] = 'B';
                for (int i = -1; i < 2; i++) {
                    for (int j = -1; j < 2; j++) {
                        if (i == 0 && j == 0) continue;
                        int r = row + i, c = col + j;
                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                        if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
                    }
                }
            }
        }
        return board;
    }
}

第六题 542. 01 Matrix

题目描述

给定01矩阵，计算每一个元素距离最近0元素的距离。

注意：

  1. 给定矩阵元素个数不超过10,000
  2. 给定矩阵中至少包含1个0元素
  3. 相邻单元格是指上、下、左、右四个方向

算法

先将所有0的点存入Queue中，然后再通过BFS，更新所有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
public class updateMatrix542 {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return matrix;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length || matrix[x][y] <= matrix[cur[0]][cur[1]] + 1)
                    continue;
                matrix[x][y] = matrix[cur[0]][cur[1]] + 1;
                queue.offer(new int[]{x, y});
            }
        }
        return matrix;
    }
}

第七题 10. Regular Expression Matching

题目描述

给定两个String，其中第二个String含有正则匹配的* 和 . 两种字符，判断两个String能否匹配

补充：

* 能够匹配*前面一个字符0 ~ n次
. 能够匹配除/n以及/r以外所有字符

算法

利用dp[i][j]来表示对于s中0 ~ i长度 与 p中0~j长度的匹配状态。如果能匹配，则返回true，不能则返回false。依次迭代，直到结束

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
public class isMatch10 {
    public boolean isMatch(String s, String p) {
        // /*/ can match the character before * to 0 ~ n times
        // /./ can match every character except /r and /n
        if (s == null || p == null)
            return false;
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        // Initial, for j = *, there is one case that matches 0 time
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '*')
                dp[0][j + 1] = dp[0][j - 1];
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (s.charAt(i) == p.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (s.charAt(i) != p.charAt(j - 1) && p.charAt(j - 1) != '.') {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    }
                    else {
                        dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] || dp[i + 1][j - 1];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

第八题 44. Wildcard Matching

题目描述

现在改变规则：

?相当于前一题的 .
但是*可以匹配任何字符串，包括空字符串

算法

自己的

利用前面的思路，可以较为轻松的写出算法

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
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int i = 1;i <= p.length();i++)
            if (p.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-1];
            }
                
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (s.charAt(i) == p.charAt(j))
                    dp[i + 1][j + 1] = dp[i][j];
                if (p.charAt(j) == '?')
                    dp[i + 1][j + 1] = dp[i][j];
                if (p.charAt(j) == '*') {
                    boolean tag = false;
                    for (int k = 0; k <= s.length(); k++) {
                        if (tag) break;
                        tag = (tag || dp[k][j]);
                    }
                    dp[i + 1][j + 1] = tag;
                }
            }
        }
        return dp[s.length()][p.length()];        
    }
}
Refactory
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
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '*') {
                dp[0][j + 1] = true;
            } else
                break;
        }
        
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) != '*') {
                    dp[i + 1][j + 1] = dp[i][j] && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?');
                }
                else {
                    dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
                }
            }
        }
        return dp[s.length()][p.length()];        
    }
}

第九题 37. Sudoku Solver

题目描述

解决9宫格问题

算法

利用回溯算法，当出现空白点的时候，试探的填入1 - 9的数字。并对其他的继续尝试，直到场试完所有的数字位置。时间复杂度为9 ^ n次方，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
public class solveSudoku37 {
    public void solveSudoku(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        solve(board);
    }
    public boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board))
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isValid(char[][] board, int row, int col, char digit) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == digit) return false;
            if (board[i][col] == digit) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == digit) return false;
        }
        return true;
    }
}