力扣第 394 场周赛

比赛时间 2024-04-21。本场周赛国服共 647 人 AK。

最近有些断更，实在太忙了，就连今天这一场，赛时也在处理工作相关的事情。。

T1. 统计特殊字母的数量 I（3 分）

解题思路

枚举。

时间复杂度：O(n)。

参考代码

class Solution {
    public int numberOfSpecialChars(String word) {
        boolean[] lowercase = new boolean[26];
        boolean[] uppercase = new boolean[26];
        for (char c : word.toCharArray()) {
            if (Character.isLowerCase(c)) {
                lowercase[c - 'a'] = true;
            } else {
                uppercase[c - 'A'] = true;
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lowercase[i] && uppercase[i]) {
                ans++;
            }
        }
        return ans;
    }
}

T2. 统计特殊字母的数量 II（4 分）

解题思路

枚举。

时间复杂度：O(n)。

参考代码

class Solution {
    public int numberOfSpecialChars(String word) {
        int n = word.length();
        int[] upper_first = new int[26];
        Arrays.fill(upper_first, -1);
        int[] lower_last = new int[26];
        Arrays.fill(lower_last, n);
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            if (Character.isLowerCase(c)) {
                lower_last[c - 'a'] = i;
            } else {
                if (upper_first[c - 'A'] == -1) {
                    upper_first[c - 'A'] = i;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lower_last[i] < upper_first[i]) {
                ans++;
            }
        }
        return ans;
    }
}

T3. 使矩阵满足条件的最少操作次数（5 分）

解题思路

记忆化搜索。取 top3 频次对应的数字来做 DP 即可。

时间复杂度：O(mn + nU^2)。其中本题 U = 10。

参考代码

class Solution {
    private int m, n;
    private List<Node[]> cntList;
    private int[][] memo;

    public int minimumOperations(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;

        cntList = new ArrayList<>();
        Node[] cnt0 = new Node[3];
        for (int i = 0; i < 3; i++) {
            cnt0[i] = new Node(10, m);
        }
        cntList.add(cnt0);
        for (int j = 0; j < n; j++) {
            Node[] cnt = new Node[11];
            for (int i = 0; i < 11; i++) {
                cnt[i] = new Node(i, 0);
            }
            for (int[] row : grid) {
                cnt[row[j]].cnt++;
            }
            Arrays.sort(cnt, (o1, o2) -> Integer.compare(o2.cnt, o1.cnt));
            cntList.add(cnt);
        }

        memo = new int[n + 1][11];
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(1, 10);
    }

    private int dfs(int i, int pre) {
        if (i == n + 1) return 0;

        if (memo[i][pre] != -1) return memo[i][pre];
        int res = Integer.MAX_VALUE;
        Node[] cnt = cntList.get(i);
        // 取 top3 即可
        for (int k = 0; k < 3; k++) {
            if (cnt[k].num != pre) {
                res = Math.min(res, m - cnt[k].cnt + dfs(i + 1, cnt[k].num));
            }
        }
        return memo[i][pre] = res;
    }

    private static class Node {
        int num, cnt;

        public Node(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

T4. 最短路径中的边（6 分）

解题思路

最短路 + BFS。

找出需要保留的点。具体就是从 0 和 n-1 出发分别跑一趟 dijkstra，然后在最短路上的带你就是需要保留的。

然后 BFS 处理一下即可。

时间复杂度：O(mlogm + n)。

参考代码

class Solution {
    private static final long INF = (long) 1e18;
    private int n;
    private List<int[]>[] g;

    public boolean[] findAnswer(int n, int[][] edges) {
        this.n = n;
        int m = edges.length;
        // y, wt, i
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int x = edges[i][0], y = edges[i][1], wt = edges[i][2];
            g[x].add(new int[]{y, wt, i});
            g[y].add(new int[]{x, wt, i});
        }
        long[] dist_st = dijkstra_mlogm(0);
        long[] dist_end = dijkstra_mlogm(n - 1);
        // 需要保留的点
        boolean[] must = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (dist_st[i] + dist_end[i] == dist_st[n - 1]) {
                must[i] = true;
            }
        }

        boolean[] ans = new boolean[m];
        // y, wt
        Queue<long[]> q = new ArrayDeque<>();
        q.add(new long[]{0, 0});
        while (!q.isEmpty()) {
            long[] top = q.remove();
            int x = (int) top[0];
            long d = top[1];
            for (int[] p : g[x]) {
                int y = p[0], wt = p[1], id = p[2];
                if (must[y] && dist_st[y] == wt + d) {
                    ans[id] = true;
                    q.add(new long[]{y, wt + d});
                }
            }
        }
        return ans;
    }

    private long[] dijkstra_mlogm(int st) {
        // y, wt
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o[1]));
        boolean[] vis = new boolean[n];
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        pq.add(new long[]{st, 0});
        dist[st] = 0;
        while (!pq.isEmpty()) {
            long[] top = pq.remove();
            int x = (int) top[0];
            if (vis[x]) continue;
            vis[x] = true;
            for (int[] p : g[x]) {
                int y = p[0], wt = p[1];
                if (dist[y] > dist[x] + wt) {
                    dist[y] = dist[x] + wt;
                    pq.add(new long[]{y, dist[y]});
                }
            }
        }
        return dist;
    }
}

（全文完）