lcp345

找出转圈游戏输家

模拟

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 int[] circularGameLosers(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int index = 1, multiple = 1;
        while (true) {
            if (set.contains(index))
                break;
            set.add(index);
            int temp = index + multiple * k;
            if (temp % n == 0)
                index = n;
            else
                index = temp % n;
            multiple++;
        }
        List<Integer> res = new LinkedList<>();
        for (int i = 1; i <= n; ++i) {
            if (set.contains(i))
                continue;
            res.add(i);
        }
        return res.stream().mapToInt(i->i).toArray();
    }
}

方法二：下标从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] circularGameLosers(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int index = 0, multiple = 1;
        while (true) {
            if (set.contains(index))
                break;
            set.add(index);
            index = (index + multiple * k) % n;
            multiple++;
        }
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (set.contains(i))
                continue;
            res.add(i + 1);
        }
        return res.stream().mapToInt(i->i).toArray();
    }
}

相邻值的按位异或

方法一：回溯 (枚举)

枚举ori[0]为0和1，只要有一个能构造成derived数组则为true

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
class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        this.derived = derived;
        n = derived.length;
        if (n == 1)
            return derived[0] == 0;
        original = new int[n];
        return dfs(0, 0) || dfs(0, 1);
    }

    private boolean dfs(int index, int x) {
        if (index == n - 1) {
            if (derived[index] == 0)
                return original[0] == x;
            else
                return original[0] != x;
        }
        String key = index + "#" + x;
        original[index] = x;
        int next = -1;
        if (derived[index] == 0)
            next = x == 0 ? 0 : 1;
        else // derived[index] == 1
            next = x == 0 ? 1 : 0;
        if (dfs(index + 1, next))
            return true;
        return false;
    }

    int[] derived, original;
    int 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
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        int res = 0;
        for (int j = 0; j < m; ++j) {
            res = Math.max(res, dfs(j, 0));
        }
        return res;
    }

    private int dfs(int i, int j) {
        if (dp[i][j] != -1)
            return dp[i][j];
        int res = 0;
        for (int[] dir : dirs) {
            int step = 0;
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] > grid[i][j]) {
                step = dfs(row, col) + 1;
            }
            res = Math.max(res, step);
        }
        return dp[i][j] = res;
    }

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

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

加上base case

可以在j = n - 1时直接return

1
2
if (j == n - 1)
    return 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
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        int res = 0;
        for (int j = 0; j < m; ++j) {
            res = Math.max(res, dfs(j, 0));
        }
        return res;
    }

    private int dfs(int i, int j) {
        if (j == n - 1)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        int res = 0;
        for (int[] dir : dirs) {
            int step = 0;
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] > grid[i][j]) {
                step = dfs(row, col) + 1;
            }
            res = Math.max(res, step);
        }
        return dp[i][j] = res;
    }

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

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

简化(去掉step)

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
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        int res = 0;
        for (int j = 0; j < m; ++j) {
            res = Math.max(res, dfs(j, 0));
        }
        return res;
    }

    private int dfs(int i, int j) {
        if (j == n - 1)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        int res = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] > grid[i][j]) 
                res = Math.max(res, dfs(row, col) + 1);
        }
        return dp[i][j] = res;
    }

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

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

时间复杂度：\(O(mn)\)

方法二：DP

记忆化搜索(自动挡)转DP(手动挡)需要考虑

  1. 初始化
  2. 遍历顺序

步骤

  1. 记忆化搜索转DP，有几个状态(i,j)就有几个for循环

  2. 状态转移方程直接搬过来

    1
    2
    if (isValid(row, col) && grid[row][col] > grid[i][j]) 
        res = Math.max(res, dfs(row, col) + 1);

  3. 遍历顺序

    如下图，遍历顺序是从上到下，从右到左

  4. 最后的答案是在第一列里找最大值！不要用一个变量在所有列里找最大值

代码

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
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        dp = new int[m][n];
        int res = 0;
        for (int j = n - 2; j >= 0; --j) 
            for (int i = 0; i < m; ++i) 
                for (int[] dir : dirs) {
                    int row = i + dir[0], col = j + dir[1];
                    if (isValid(row, col) && grid[i][j] < grid[row][col]) 
                        dp[i][j] = Math.max(dp[i][j], dp[row][col] + 1);
                }
        for (int i = 0; i < m; ++i)
            res = Math.max(res, dp[i][0]);
        return res;
    }


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

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

方法三：BFS

?why 双队列会超时

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
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int res = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i)
            queue.offer(new int[]{i, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int row = arr[0], col = arr[1];
            res = Math.max(res, col);
            for (int[] dir : dirs) {
                int nextRow = row + dir[0], nextCol = col + 1;
                if (isValid(nextRow, nextCol) && !visited[nextRow][nextCol] && grid[nextRow][nextCol] > grid[row][col]) {
                    if (nextCol == n - 1)
                        return n - 1;
                    visited[nextRow][nextCol] = true;
                    queue.offer(new int[]{nextRow, nextCol});
                }
            }

        }
        return res;
    }


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

    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
61
class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        // 并查集确定连通分量
        // 遍历每个连通分量，如果每个节点的入度 == 连通分量节点数 - 1，则是完全连通(或者只有一个顶点)
        init(n);

        int[] inDegrees = new int[n];
//        Set<Integer> visited = new HashSet<>(); // 如果某个节点没有与其他节点有边，算一个完全连通分量
        for (int[] edge : edges) {
//            visited.add(edge[0]);
//            visited.add(edge[1]);
            ++inDegrees[edge[0]];
            ++inDegrees[edge[1]];
            union(edge[0], edge[1]);
        }
//        int notVisitedNum = n - visited.size(), res = 0;
        int res = 0;
        Map<Integer, List> graph = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            graph.putIfAbsent(findParent(i), new LinkedList());
            graph.get(findParent(i)).add(i);
        }
        for (Map.Entry<Integer, List> entry : graph.entrySet()) {
            List<Integer> nodes = entry.getValue();
            int size = nodes.size();
            boolean flag = true;
            for (int node : nodes) {
                if (inDegrees[node] != size - 1) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                ++res;
        }

        return res;
    }

    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;
    }
}

记忆化搜索的缺点

值域大的时候，不能使用记忆化搜索，占用太多内存空间

比如不能解决https://leetcode.cn/problems/maximum-subarray/description/

Contest > LCP
#力扣杯
lcp345
https://leopol1d.github.io/2023/07/17/lcp345/
作者
Leopold
发布于
2023年7月17日
许可协议