[Leetcode Weekly Contest]336

链接：LeetCode

[Leetcode]2586. 统计范围内的元音字符串数

给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。
如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。
返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

遍历即可。

class Solution {
    private final HashSet<Character> vowels = new HashSet<Character>(){{
            add('a');
            add('e');
            add('i');
            add('o');
            add('u');
    }};

    public int vowelStrings(String[] words, int left, int right) {
        int res = 0;
        for(int i=left;i<=right;++i)
        {
            String word = words[i];
            int length = word.length();
            if(vowels.contains(word.charAt(0)) && vowels.contains(word.charAt(length-1))) res ++;
        }
        return res;
    }
}

[Leetcode]2587. 重排数组以得到最大前缀分数

给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。
令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。
返回可以得到的最大分数。

排序累加即可。

class Solution {
    public int maxScore(int[] nums) {
        long sum = 0;
        int res = 0;
        Arrays.sort(nums);
        for(int i=nums.length-1;i>=0;--i) {
            sum += nums[i];
            if(sum > 0) res++;
            else break;
        }
        return res;
    }
}

[Leetcode]2588. 统计美丽子数组数目

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2k 。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。

前缀异或和

class Solution {
    public long beautifulSubarrays(int[] nums) {
        long ans = 0;
        int n = nums.length;
        var s = new int[n + 1];
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] ^ nums[i];
        var cnt = new HashMap<Integer, Integer>();
        for (int x : s) {
            // 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
            ans += cnt.getOrDefault(x, 0);
            cnt.merge(x, 1, Integer::sum);
        }
        return ans;
    }
}

[Leetcode]2589. 完成所有任务的最少时间

你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。
当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。
请你返回完成所有任务的情况下，电脑最少需要运行多少秒。

贪心+线段树。
按照右端点排序。遍历排序后的任务，先统计区间内的已有的电脑运行时间点，如果个数小于 duration，则需要新增时间点。尽量把新增的时间点安排在区间 [start,end] 的后缀上，这样下一个区间就能统计到更多已有的时间点。

class Solution {
    public int findMinimumTime(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        int u = tasks[tasks.length - 1][1];
        cnt = new int[u * 4];
        todo = new boolean[u * 4];
        for (var t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            suffix = d - query(1, 1, u, start, end);  // 去掉运行中的时间点
            if (suffix > 0) update(1, 1, u, start, end); // 新增时间点
        }
        return cnt[1];
    }

    private int[] cnt;
    private boolean[] todo;
    private int suffix;

    private void do_(int o, int l, int r) {
        cnt[o] = r - l + 1;
        todo[o] = true;
    }

    void spread(int o, int l, int m, int r) {
        if (todo[o]) {
            do_(o * 2, l, m);
            do_(o * 2 + 1, m + 1, r);
            todo[o] = false;
        }
    }

    // 查询区间 [L,R]   o,l,r=1,1,u
    int query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) return cnt[o];
        int m = (l + r) / 2;
        spread(o, l, m, r);
        if (m >= R) return query(o * 2, l, m, L, R);
        if (m < L) return query(o * 2 + 1, m + 1, r, L, R);
        return query(o * 2, l, m, L, R) + query(o * 2 + 1, m + 1, r, L, R);
    }

    // 新增区间 [L,R] 后缀的 suffix 个时间点    o,l,r=1,1,u
    // 相当于把线段树二分和线段树更新合并成了一个函数，时间复杂度为 O(log u)
    void update(int o, int l, int r, int L, int R) {
        int size = r - l + 1;
        if (cnt[o] == size) return; // 全部为运行中
        if (L <= l && r <= R && size - cnt[o] <= suffix) { // 整个区间全部改为运行中
            suffix -= size - cnt[o];
            do_(o, l, r);
            return;
        }
        int m = (l + r) / 2;
        spread(o, l, m, r);
        if (m < R) update(o * 2 + 1, m + 1, r, L, R); // 先更新右子树
        if (suffix > 0) update(o * 2, l, m, L, R); // 再更新左子树（如果还有需要新增的时间点）
        cnt[o] = cnt[o * 2] + cnt[o * 2 + 1];
    }
}

参考：LeetCode