lcp357

故障键盘

方法二：双端队列

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
class Solution {
    public String finalString(String s) {
        Deque<Character> queue = new LinkedList<>();
        boolean shouldReverse = false;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch == 'i')
                shouldReverse = !shouldReverse;
            else {
                if (!shouldReverse) 
                    queue.offerFirst(ch);
                else 
                    queue.offerLast(ch);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            if (shouldReverse)
                sb.append(queue.pollFirst());
            else
                sb.append(queue.pollLast());
        }
        return sb.toString();
    }
}

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String finalString(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (ch != 'i') {
                sb.append(ch);
            }
            else {
                reverse(sb);
            }
        }
        return sb.toString();
    }

    private void reverse(StringBuilder sb) {
        sb.reverse();
    }
}

判断是否能拆分数组

方法一：记忆化搜索

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
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        this.nums = nums;
        n = nums.size();
        if (n <= 2)
            return true;
        this.m = m;
        preSum = new int[n + 1];
        for (int i = 0; i < n; ++i)
            preSum[i + 1] = preSum[i] + nums.get(i);
        return dfs(0, n);
    }

    // [)
    private boolean dfs(int l, int r) {
        if (r - l == 1)
            return true;
        String key = l + "#" + r;
        if (map.containsKey(key))
            return map.get(key);
        if (preSum[r] - preSum[l] < m) {
            map.put(key, false);
            return false;
        }
        boolean res = false;
        for (int i = l + 1; i < r; ++i) {
            res = dfs(l, i) && dfs(i, r);
            if (res) {
                map.put(key, res);
                return true;
            }
        }
        map.put(key, res);
        return false;
    }

    List<Integer> nums;
    int m, n;
    Map<String, Boolean> map = new HashMap<>();
    int[] preSum;
}

方法二：贪心

1
2
3
4
5
6
7
8
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        for (int i = 0; i < nums.size() - 1; ++i) 
            if (nums.get(i) + nums.get(i + 1) >= m)
                return true;
        return nums.size() <= 2;
    }
}

6951. 找出最安全路径

方法一：多源BFS

二分做右端点的初始

1
int l = 0, r = Math.min(dist[0][0], dist[n - 1][n - 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
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
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                grid[i][j] = g.get(i).get(j);
        int[][] dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }

        
        int l = 0, r = Math.min(dist[0][0], dist[n - 1][n - 1]);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, dist))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;

    }

    private boolean check(int limit, int[][] dist) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && !visited[row][col] && dist[row][col] >= limit) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return visited[n - 1][n - 1];
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

在check中判断初始位置，r = 2 * n - 1 (大一点也没关系)

1
2
if (dist[0][0] < limit)
    return 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
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
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                grid[i][j] = g.get(i).get(j);

        int[][] dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }

        
        int l = 0, r = 2 * n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, dist))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;

    }

    private boolean check(int limit, int[][] dist) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        if (dist[0][0] < limit)
            return false;
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && !visited[row][col] && dist[row][col] >= limit) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return visited[n - 1][n - 1];
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

check使用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
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
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = g.get(i).get(j);
                dist[i][j] = -1;
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        // bfs
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    queue.offer(new int[]{row, col});
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                }
            }
        }
        int l = 0, r = (n - 1) << 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }

    private boolean check(int minDist) {
        if (dist[0][0] < minDist)
            return false;
        boolean[][] visited = new boolean[n][n];
        return dfs(0, 0, minDist, visited);
    }

    private boolean dfs(int i, int j, int minDist, boolean[][] visited) {
        if (i == n -1 && j == n - 1)
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col =  j + dir[1];
            if (isValid(row, col) && !visited[row][col] && dist[row][col] >= minDist) {
                if (dfs(row, col, minDist, visited))
                    return true;
            }
        }
        return false;
    }

    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dist, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

方法二：多源BFS + 并查集

关于从dists.size() - 2开始枚举：最后一步是空集，所以最大的距离为 dists.size() - 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
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 {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        int[][] dist = new int[n][n];
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        List<int[]> queue = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = g.get(i).get(j);
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }
        // 多源BFS
        List<List<int[]>> dists = new ArrayList<>();
        dists.add(queue);
        List<int[]> temp = new LinkedList<>();
        while (!queue.isEmpty()) {
            temp = queue;
            queue = new LinkedList<>();
            for (int[] node : temp) {
                for (int[] dir : dirs) {
                    int row = node[0] + dir[0], col = node[1] + dir[1];
                    if (isValid(row, col) && dist[row][col] == -1) {  // 没有被访问过
                        queue.add(new int[]{row, col});
                        dist[row][col] = dists.size();
                    }
                }
            }
            // 最后一步是空集，所以最大的距离为 dists.size() - 2
            dists.add(queue);
        }
        // 初始化并查集
        init(n * n);
        for (int i = dists.size() - 2; i > 0; --i) {
            List<int[]> q = dists.get(i);
            for (int[] node : q) {
                for (int[] dir : dirs) {
                    int row = node[0] + dir[0], col = node[1] + dir[1];
                    if (isValid(row, col) && dist[row][col] >= i)
                        union(node[0] * n + node[1],row * n + col);
                }
            }
            if (findParent(0) == findParent(n * n - 1))
                return i;
        }
        return 0;
    }



    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

补充题 1631. 最小体力消耗路径

方法一：多源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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        visited = new boolean[m][n];
        int l = 0, r = (int) 1e6;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int limit) {
        visited = new boolean[m][n];
        return dfs(0, 0, limit);
    }

    private boolean dfs(int i, int j, int limit) {
        if (i == m - 1 && j == n - 1)
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && !visited[row][col] && Math.abs(heights[i][j] - heights[row][col]) <= limit)
                if (dfs(row, col, limit))
                    return true;
        }
        return false;
    }


    int[][] heights, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    boolean[][] visited;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        visited = new boolean[m][n];
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int id = i * n + j;
                if (i > 0)
                    edges.add(new int[]{id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])});
                if (j > 0)
                    edges.add(new int[]{id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])});
            }
        }
        Collections.sort(edges, (o1, o2) -> o1[2] - o2[2]);
        // 初始化并查集
        init(m * n);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            union(from, to);
            if (findParent(0) == findParent(m * n - 1))
                return weight;
        }
        return 0;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }



    int[][] heights, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    boolean[][] visited;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}
Contest > LCP
#力扣杯
lcp357
https://leopol1d.github.io/2023/08/06/lcp357/
作者
Leopold
发布于
2023年8月6日
许可协议