力扣第 348 场周赛

“光芒熄灭了 但我们还在战斗”。

纪念挚友 ming1ing。

比赛时间 2023-06-04。本场周赛国服共 389 人 AK。

T1. 最小化字符串长度（3 分）

解题思路

读题题。问题等价于统计不同字符个数。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minimizedStringLength(String s) {
        Set<Character> set = new HashSet<>();
        for (char ch : s.toCharArray()) {
            set.add(ch);
        }
        return set.size();
    }
}

T2. 半有序排列（3 分）

解题思路

分类讨论。找出最小值，最大值坐标后：

• ans = i + (n-1-i) 下标不交叉；
• ans = i + (n-1-i) - 1 下标交叉；

时间复杂度：O(n)。

参考代码

class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int minIdx = 0, maxIdx = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIdx]) minIdx = i;
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }

        int ans = minIdx + (n - 1 - maxIdx);
        return minIdx < maxIdx ? ans : ans - 1;
    }
}

T3. 查询后矩阵的和（5 分）

解题思路

脑筋急转弯。从后往前考虑，已经被修改过的元素不会被再次修改。

时间复杂度：O(q)。

参考代码

class Solution {
    public long matrixSumQueries(int n, int[][] queries) {
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        long ans = 0L;
        int q = queries.length;
        for (int i = q - 1; i >= 0; i--) {
            int type = queries[i][0], index = queries[i][1], val = queries[i][2];
            if (type == 0) {
                if (rows.contains(index)) continue;
                ans += (long) (n - cols.size()) * val;
                rows.add(index);
            } else {
                if (cols.contains(index)) continue;
                ans += (long) (n - rows.size()) * val;
                cols.add(index);
            }
        }
        return ans;
    }
}

T4. 统计整数数目（6 分）

解题思路

数位 DP。上下界稍微处理一下即可：（[0, num2] 符合要求的数量 减去 [0, num1-1] 符合要求的数量）。

时间复杂度：O(n * max_sum)。其中 n = num2.length。

参考代码

import java.math.BigInteger;

class Solution {
    private static final int MOD = (int) (1e9 + 7);
    private int min_sum, max_sum;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        long ans1 = count(new BigInteger(num1).subtract(BigInteger.ONE).toString());
        long ans2 = count(num2);
        return (int) (((ans2 - ans1) % MOD + MOD) % MOD);
    }

    private char[] s;
    private long[][] dp;

    private long count(String num) {
        s = num.toCharArray();
        int n = num.length();
        dp = new long[n][max_sum + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    private long f(int i, int sum, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            if (!isNum) return 0;
            if (sum > max_sum || sum < min_sum) return 0;
            return 1;
        }
        if (sum > max_sum) return 0;
        if (!isLimit && isNum && dp[i][sum] != -1) {
            return dp[i][sum];
        }
        long ans = 0L;
        if (!isNum) {
            ans += f(i + 1, sum, false, false);
            ans %= MOD;
        }
        int down = isNum ? 0 : 1;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = down; d <= up; d++) {
            ans += f(i + 1, sum + d, isLimit && d == up, true);
            ans %= MOD;
        }
        return dp[i][sum] = ans;
    }
}

（全文完）