发表更新算法 / LeetCode6 分钟读完 (大约857个字)

第 397 场力扣周赛

矩阵中的最大得分

题目

输入一个 \(m\times n\) 的矩阵 \(grid\)，输出选择任意单元格作为起点，至少移动一次能够得到的最大得分。每次移动只能向正右方和正下方的单元格移动，不必相邻。假设从单元格 \((x_{1},y_{1})\) 移动到 \((x_{2},y_{2})\)，则本次移动的得分为 \(grid[x_{2}][y_{2}]-grid[x_{1}][y_{1}]\)。

数据范围：\(2\leq m,n\leq 1000\)，\(4\leq m\times n\leq 10^{5}\)，\(1\leq grid[i][j]\le 10^{5}\)。

思路

比赛时想到计算过程存在重叠子问题，可以使用记忆化搜索。定义 \(f[i][j]\) 表示以 \((i,j)\) 为起点能够得到的最大得分，初始化 \(f[i][j]\) 为负无穷。当 \(i<m-1\) 且 \(j<n-1\) 时，状态转移方程为 \(f[i][j]=\max{(f[i+1][j]+grid[i+1][j]-grid[i][j],f[i][j+1])+grid[i][j+1]-grid[i][j]}\)。也可以将记忆化搜索转化为自底向上的形式，或者定义 \(f[i][j]\) 表示以 \((i,j)\) 为终点能够得到的最大得分。

通过观察可以发现，对于某个移动路径，得分只和起点和终点有关，中间的值都被抵消了。也就是说，某个起点能够得到的最大得分，是其右下角的最大值减去起点的值，反之亦然。所以也可以定义 \(f[i][j]\) 表示 \((i,j)\) 右下角的最大值或者左上角的最小值，然后进行递推。

时间复杂度为 \(O(mn)\)，空间复杂度为 \(O(mn)\)。灵神题解有个空间复杂度为 \(O(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
class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dfs(0, 0, grid, dp);
        
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
    
    private int dfs(int x, int y, List<List<Integer>> grid, int[][] dp) {
        int m = grid.size(), n = grid.get(0).size();
        if (dp[x][y] == Integer.MIN_VALUE) {
            if (x + 1 < m) {
                int diff = grid.get(x + 1).get(y) - grid.get(x).get(y);
                dp[x][y] = Math.max(dp[x][y], diff + dfs(x + 1, y, grid, dp));
            }
            if (y + 1 < n) {
                int diff = grid.get(x).get(y + 1) - grid.get(x).get(y);
                dp[x][y] = Math.max(dp[x][y], diff + dfs(x, y + 1, grid, dp));
            }
        }
        return Math.max(0, dp[x][y]);
    }
}

找出分数最低的排列

题目

输入从 \(0\) 到 \(n-1\) 的一个排列 \(nums\)，输出从 \(0\) 到 \(n-1\) 的排列 \(perm\)，使得 \(score(perm)=\sum_{i=0}^{n-1}{|perm[i]-nums[perm[(i+1)\bmod n|}\) 的值最小。如果有多个满足条件的排列，则返回字典序最小的那个。

数据范围：\(2\leq n\leq 14\)。

思路

通过观察可以发现，对于一个给定的排列 \(perm\)，将其循环移动不会改变 \(score(perm)\) 的值。要使满足条件的 \(perm\) 字典序最小，那么必然有 \(perm[0]=0\)。暴力的想法是枚举所有排列，但是时间复杂度为 \(n!\times n\)。由于枚举过程中，存在重复子问题，可以使用记忆化搜索来降低时间复杂度到 \(O(2^{n}n^{2})\)。定义 \(f[mask][pre]\) 表示已经选择集合 \(mask\) 中的数，上一个选择的数是 \(pre\)，剩余的数排列能够得到的最小分数。同理，定义 \(g[mask][pre]\) 表示下一个选择什么数能够使得分数最小，以及相同分数的排列字典序最小。可以看下灵神题解，不使用记忆化搜索，自底向上的解法也是非常经典的。

代码

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
class Solution {
    public int[] findPermutation(int[] nums) {
        int n = nums.length;
        int[][] f = new int[1 << n][n];
        int[][] g = new int[1 << n][n];
        for (int i = 0; i < (1 << n) - 1; i++) {
            Arrays.fill(f[i], -1);
        }
        for (int i = 0; i < n; i++) {
            f[(1 << n) - 1][i] = Math.abs(i - nums[0]);
        }
        dfs(1, 0, nums, f, g);

        int[] ans = new int[n];
        for (int i = 0, mask = 0, cur = 0; i < n; i++) {
            ans[i] = cur;
            mask |= 1 << cur;
            cur = g[mask][cur];
        }
        return ans;
    }

    private int dfs(int mask, int pre, int[] nums, int[][] f, int[][] g) {
        int n = nums.length;
        if (mask == (1 << n) - 1 || f[mask][pre] != -1) {
            return f[mask][pre];
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if ((mask >> i & 1) == 0) {
                int cur = dfs(mask | 1 << i, i, nums, f, g) + Math.abs(pre - nums[i]);
                if (cur < res) {
                    res = cur;
                    g[mask][pre] = i;
                }
            }
        }
        return f[mask][pre] = res;
    }
}
发表更新算法 / AtCoder1 分钟读完 (大约119个字)

AtCoder Beginner Contest 350

Sort

题目

输入长度为 \(n\) 的数组 \(a\)，表示从 \(1\) 到 \(n\) 的排列。输出操作的次数和过程，使得排列有序。每次操作可以交换 \(a_{i}\) 和 \(a_{j}\)，其中 \(1\leq i<j\leq n\)。

数据范围：\(2\leq n\leq 2\times 10^{5}\)。

思路

如果 \(a_{i}=i\)，则说明 \(a_{i}\) 在正确的位置上。否则，\(a_{i}\) 应该移动到位置 \(a_{i}\) 上，即交换下标 \(i\) 和 \(a_{i}\) 的值。这样每次交换都至少使得一个数在正确的位置上，最多交换 \(n-1\) 次，时间复杂度为 \(O(n)\)。PS：太久没做题，竟然没有做出来。比赛时多此一举，使用的是下标数组 + 排序做的，其实也没问题，就是最后没有按照大小顺序输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt() - 1;
    }

    List<int[]> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        while (a[i] != i) {
            ans.add(new int[]{Math.min(i, a[i]), Math.max(i, a[i])});
            int t = a[a[i]]; a[a[i]] = a[i]; a[i] = t;
        }
    }

    io.println(ans.size());
    for (var t : ans) {
        io.println((t[0] + 1) + " " + (t[1] + 1));
    }
}
发表更新算法 / LeetCode6 分钟读完 (大约934个字)

第 394 场力扣周赛

使矩阵满足条件的最少操作次数

题目

输入 \(m\times n\) 的矩阵 \(grid\)，输出需要的最少操作次数，使得每列的值相等，且相邻两列的值不相等。每次操作可以将任意单元格的值修改为任意非负整数。

数据范围：\(1\leq n,m\leq 1000\)，\(0\leq grid[i][j]\leq 9\)。

思路

首先，每列的值肯定是修改为 \([0,9]\) 之间更优，因为操作次数可能更少。我们可以从前往后枚举每列修改为什么值，可以发现存在重叠子问题。定义 \(dp[i][j]\) 表示将第 \(i\) 列修改为 \(j\)，使得 \([0,i]\) 列满足条件所需的最少操作次数。有状态转移方程 \(dp[i][j]=\min{(dp[i-1][k])}+cnt_{i,j}\)，其中 \(0\leq k\leq 9\) 且 \(k\neq j\)，\(cnt_{i,j}\) 表示将第 \(i\) 列修改为 \(j\) 所需的操作次数。时间复杂度为 \(O(mn+nU^{2})\)，空间复杂度为 \(O(nU)\)，其中 \(U\) 表示 \(grid[i][j]\) 的值域大小。灵神题解提到一个优化方式，状态转移只会从前面所有列操作的最优值或者次优值转移过来，利用这个特性可以降低时间和空间复杂度。

代码

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 int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] cnt = new int[n][10];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cnt[j][grid[i][j]]++;
            }
        }
        
        int[][] dp = new int[n + 1][10];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    if (k != j) {
                        dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][k] + (m - cnt[i][j]));
                    }
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 10; i++) {
            ans = Math.min(ans, dp[n][i]);
        }
        return ans;
    }
}

最短路径中的边

题目

输入整数 \(n\) 和长度为 \(m\) 的数组 \(edges\)，表示包含 \(n\) 个节点和 \(m\) 条边的无向带权图（无重边和自环）。输出长度为 \(m\) 的布尔数组 \(ans\)，如果从节点 \(0\) 到节点 \(n-1\) 的所有最短路中包含 \(edges[i]\)，则 \(ans[i]=true\)。

数据范围：\(2\leq n\leq 5\times 10^{4}\)，\(1\leq m\leq\min{(5\times 10^{4},\frac{n(n-1)}{2})}\)，\(1\leq w_{i}\leq 10^{5}\)。

思路

首先使用 Dijkstra 算法求出从节点 \(0\) 到所有其他节点的最短路，然后暴力的想法是以节点 \(0\) 为起点使用 DFS 回溯来遍历图，遍历的同时存储路径上的边，当到达节点 \(n-1\) 的路径长度等于最短路时，则将该路径上的边都置为 \(true\)。回溯理论上最坏情况下的时间复杂度为 \(O(n\times n!)\)，但是可以通过力扣的测试，因为可以利用最短路的限制进行剪枝，至于能否构造出 Hack 回溯的测试用例，我不太清楚。

正确的解法是使用两次 Dijkstra 算法，分别求出从节点 \(0\) 到所有其他节点的最短路，和从节点 \(n-1\) 到所有其他节点的最短路。然后枚举每一条边，判断路径长度 \(d_{0,u}+w_{u,v}+d_{v,n-1}\) 或者 \(d_{0,v}+w_{u,v}+d_{u,n-1}\) 是否等于最短路，从而可以得出该边是否在某个最短路中。

另一种做法是只对起点使用一次 Dijkstra 算法，然后从终点反向 DFS，经过的边如果满足 \(d_{0,v}+w_{u,v}=d_{0,u}\)，则说明该边在某个最短路上。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×