Leetcode - 周赛450

一，3550. 数位和等于下标的最小下标

题目列表

本题直接暴力求解，代码如下：

class Solution {
    public int smallestIndex(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            int x = nums[i];
            int s = 0;
            while(x > 0){
                s += x % 10;
                x /= 10;
            }
            if(s == i) return i;
        }
        return -1;
    }
}

二，3551. 数位和排序需要的最小交换次数

题目列表

本题实际是一个环的问题，画个图理解一下：

在一个环当中，想要恢复排列，需要交换 $n-1$ 次，所以本题的问题就变成了，$nums$ 数组能形成几个环，可以使用并查集，也可使用循环来做，代码如下：

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int[] t = new int[n];
        Integer[] idx = new Integer[n];
        for(int i = 0; i < n; i++){
            int x = nums[i];
            while(x > 0){
                t[i] += x % 10;
                x /= 10;
            }
            idx[i] = i;
        }
        // 下标映射
        Arrays.sort(idx, (x, y) -> t[x] == t[y] ? nums[x] - nums[y] : t[x] - t[y]);
        boolean[] vis = new boolean[n];
        int cnt = 0;// 统计有几个环
        for(int i = 0; i < n; i++){
            if(vis[i]) continue;
            cnt++;
            while(!vis[i]){
                vis[i] = true;
                i = idx[i];
            }
        }
        return n - cnt;
    }
}

三，3552. 网格传送门旅游

题目列表

本题就是一个 dijstra 最短路问题，唯一的区别在于，该题多了一个传送门的条件，对于这个条件，它会出现两种情况：

• 第一次遇到的时候，使用传送门
• 第一次遇到的时候，不使用传送门
• 如果最少移动次数是需要使用该传送门，那么第一次遇到直接使用最优，否则下次使用至少也需要多走一步。
• 如果最少移动次数是不需要使用该传送门，那么随便什么时候使用都没用，不会对结果造成影响
• 综上所述，只需要在第一次遇到传送门时直接把该相同字母的传送门都添加到队列中就行，此外，为了防止重复访问，还需要将该传送门直接删除。

代码如下：

class Solution {
    public int minMoves(String[] matrix) {
        int n = matrix.length;
        int m = matrix[0].length();
        char[][] s = new char[n][m];
        List<int[]>[] g = new ArrayList[26];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int i = 0; i < n; i++){
            s[i] = matrix[i].toCharArray();
            for(int j = 0; j < m; j++){
                if(Character.isUpperCase(s[i][j])){
                    g[s[i][j] - 'A'].add(new int[]{i, j});
                }
            }
        }
        int[][] dirct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[][] dis = new int[n][m];
        for(int[] r : dis) Arrays.fill(r, Integer.MAX_VALUE);
        ArrayDeque<int[]> que = new ArrayDeque<>();
        que.addFirst(new int[]{0, 0, 0});
        dis[0][0] = 0;
        while(!que.isEmpty()){
            int[] t = que.pollFirst();
            int i = t[0], j = t[1], w = t[2];
            if(dis[i][j] < w){
                continue;
            }
            if(i == n - 1 && j == m - 1) return w;
            if(s[i][j] != '.'){// 如果是传送门
                for(int[] x : g[s[i][j] - 'A']){
                    if(i == x[0] && j == x[1]) continue;
                    dis[x[0]][x[1]] = dis[i][j];
                    que.addFirst(new int[]{x[0], x[1], dis[i][j]});
                }
                g[s[i][j]-'A'].clear();// 删除已访问的传送门
            }
            for(int[] d : dirct){
                int x = i + d[0], y = j + d[1];
                if(x >= 0 && x < n && y >= 0 && y < m && s[x][y] != '#'){
                    if(dis[x][y] > dis[i][j] + 1){
                        dis[x][y] = dis[i][j] + 1;
                        que.addLast(new int[]{x, y, dis[x][y]});
                    }
                }
            }
        }
        return -1;
    }
}

四，3553. 包含给定路径的最小带权子树 II

题目列表

本题题意，找到一条最短路径，使得 $queries[i]$ 中的三个点 $[a,b,c]$ 连起来，返回最短路径的长度。画个图理解一下：

所以本题的思路就是，使用树上倍增快速计算两点的最近公共祖先，然后根据上述所说的公式计算出最短公共路径就行，上述例子中的 OA，OC，OE 可以通过 dfs 来计算得到。

代码如下：

class Solution {
    public int[] minimumWeight(int[][] edges, int[][] queries) {
        int n = edges.length + 1;
        int m = 32 - Integer.numberOfLeadingZeros(n);
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e->new ArrayList<>());
        for(int[] e : edges){
            int u = e[0], v = e[1], w = e[2];
            g[u].add(new int[]{v, w});
            g[v].add(new int[]{u, w});
        }
        int[] depth = new int[n];
        int[][] pa = new int[n][m];
        int[] dis = new int[n];
        dfs(0, -1, g, pa, depth, dis);// 初始化
		
		// 初始化 pa
		// pa[i][j]: 从 i 节点向上走 1<<j 步到达节点位置
        for(int j = 1; j < m; j++){
            for(int i = 1; i < n; i++){
                pa[i][j] = pa[i][j-1] < 0 ? -1 : pa[pa[i][j-1]][j-1];
            }
        }

        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            int[] q = queries[i];
            int a = q[0], b = q[1], c = q[2];
            int ac = LCA(a, c, depth, pa);
            int bc = LCA(b, c, depth, pa);
            int ab = LCA(a, b, depth, pa);
            // (CE + ED + DC) / 2
            ans[i] = (dis[a] + dis[b] - 2 * dis[ab]
                    + dis[a] + dis[c] - 2 * dis[ac]
                    + dis[b] + dis[c] - 2 * dis[bc])/2;
        }
        return ans;
    }
    
    void dfs(int x, int fa, List<int[]>[] g, int[][] pa, int[] depth, int[] dis){
        pa[x][0] = fa;// 初始化树上倍增
        for(int[] t : g[x]){
            int y = t[0], w = t[1];
            if(y == fa) continue;
            depth[y] = depth[x] + 1;// 计算每个节点深度
            dis[y] = dis[x] + w; // ，计算每个节点到根节点的距离
            dfs(y, x, g, pa, depth, dis);
        }
    }
	// 返回从 x 节点出发，向上走 k 步所到的节点
    int getK(int x, int k, int[][] pa){
        for(; k > 0; k &= k-1){
            x = pa[x][Integer.numberOfTrailingZeros(k)];
        }
        return x;
    }
	// 计算 x, y 的最近公共祖先
    int LCA(int x, int y, int[] depth, int[][] pa){
        if(depth[x] > depth[y]){
            int tmp = x;
            x = y;
            y = tmp;
        }
        // 先将两个点调整到同一深度，在向上跳
        // 类似于一个链表分叉，求从哪里开始分叉
        y = getK(y, depth[y] - depth[x], pa);
        if(x == y) return x;
        for(int i = pa[x].length - 1; i >= 0; i--){
            int px = pa[x][i], py = pa[y][i];
            if(px != py){
                x = px;
                y = py;
            }
        }
        return pa[x][0];
    }
}

思考题：如果要连接 k 个节点，如何计算最短路？
答：先使用 dfs 先序遍历，确认两两节点的连接顺序，比如 ABCD，只能 (AB + BC + CD + DA) / 2 这么计算，其余不变。