力扣第 375 场周赛

比赛时间 2023-12-10。本场周赛国服共 855 人 AK。

T1. 统计已测试设备（3 分）

解题思路

模拟。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int n = batteryPercentages.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (batteryPercentages[i] > 0) {
                for (int j = i + 1; j < n; j++) {
                    batteryPercentages[j]--;
                }
                ans++;
            }
        }
        return ans;
    }
}

T2. 双模幂运算（4 分）

解题思路

模拟 + 快速幂。

时间复杂度：O(nlogU)。

参考代码

class Solution {
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        int n = variables.length;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] p = variables[i];
            int a = p[0], b = p[1], c = p[2], m = p[3];
            long res = quickPow(quickPow(a, b, 10), c, m);
            if (res == target) {
                ans.add(i);
            }
        }
        return ans;
    }

    private long quickPow(long a, long b, long mod) {
        long res = 1L;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
}

T3. 统计最大元素出现至少 K 次的子数组（5 分）

解题思路

双指针。

时间复杂度：O(n)。

参考代码

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int mx = Arrays.stream(nums).max().orElseThrow();
        int l = 0, r = 0;
        long ans = 0;
        // 频次大于等于 k 的数目
        int cnt = 0;
        while (r < n) {
            if (nums[r] == mx) cnt++;
            while (cnt >= k) {
                ans += n - r;
                if (nums[l] == mx) cnt--;
                l++;
            }
            r++;
        }
        return ans;
    }
}

T4. 统计好分割方案的数目（6 分）

解题思路

找出每个数字的区间（最左下标，最右下标）。然后合并区间。设区间个数为 m，则答案为 2^(m-1)。

时间复杂度：O(nlogn)。

参考代码

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

    public int numberOfGoodPartitions(int[] nums) {
        int n = nums.length;
        Map<Integer, int[]> ranges = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (!ranges.containsKey(x)) {
                ranges.put(x, new int[]{i, i});
            } else {
                ranges.get(x)[1] = i;
            }
        }
        // 合并区间
        List<int[]> intervals = new ArrayList<>(ranges.values());
        int sz = merge(intervals).size();
        return (int) quickPow(2, sz - 1);
    }

    private List<int[]> merge(List<int[]> intervals) {
        intervals.sort(Comparator.comparingInt(o -> o[0]));
        List<int[]> ans = new ArrayList<>();
        for (int[] p : intervals) {
            int l = p[0], r = p[1];
            if (!ans.isEmpty() && l <= ans.get(ans.size() - 1)[1]) {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], r);
            } else {
                ans.add(new int[]{l, r});
            }
        }
        return ans;
    }

    private long quickPow(long a, long b) {
        long res = 1L;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
}

（全文完）