力扣第 400 场周赛

比赛时间 2024-06-02。本场周赛国服共 627 人 AK。

其实 咱们只要足够努力，机会就一直会在 不是的，我努力过无数次了，但我知道，机会只会出现在 这其中的一两次。

——《飞驰人生 2》

T1. 候诊室中的最少椅子数（3 分）

解题思路

遍历，将 E 看成 1，将 L 看成 -1，和取最大值即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minimumChairs(String s) {
        int ans = 0, sum = 0;
        for (char c : s.toCharArray()) {
            if (c == 'E') sum++;
            else sum--;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

T2. 无需开会的工作日（4 分）

解题思路

合并区间后，再统计即可。

赛时想用差分解决，但并不顺利，用动态开点线段树水过。。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int countDays(int days, int[][] meetings) {
        DynamicSegTreeUpd_sum seg = new DynamicSegTreeUpd_sum();
        for (int[] p : meetings) {
            int st = p[0], end = p[1];
            seg.update(st, end, 1);
        }
        return (int) (days - seg.getSum(1, days));
    }

    static class DynamicSegTreeUpd_sum {
        static final int N = Integer.MAX_VALUE;
        final Node root = new Node();

        private static class Node {
            Node ls, rs;
            long sum, lazy;
        }

        void update(int ql, int qr, int val) {
            this.update(root, 0, N, ql, qr, val);
        }

        void update(Node p, int l, int r, int ql, int qr, int val) {
            if (ql <= l && r <= qr) {
                p.sum = (r - l + 1L) * val;
                p.lazy = val;
                return;
            }
            pushDown(p, l, r);
            int mid = l + (r - l) / 2;
            if (ql <= mid) update(p.ls, l, mid, ql, qr, val);
            if (qr > mid) update(p.rs, mid + 1, r, ql, qr, val);
            pushUp(p);
        }

        long getSum(int ql, int qr) {
            return this.getSum(root, 0, N, ql, qr);
        }

        long getSum(Node p, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) {
                return p.sum;
            }
            pushDown(p, l, r);
            int mid = l + (r - l) / 2;
            long sum = 0;
            if (ql <= mid) sum = getSum(p.ls, l, mid, ql, qr);
            if (qr > mid) sum += getSum(p.rs, mid + 1, r, ql, qr);
            return sum;
        }

        void pushDown(Node p, int l, int r) {
            if (p.ls == null) p.ls = new Node();
            if (p.rs == null) p.rs = new Node();
            if (p.lazy != 0) {
                int mid = l + (r - l) / 2;
                p.ls.sum = p.lazy * (mid - l + 1L);
                p.rs.sum = p.lazy * (r - mid);
                p.ls.lazy = p.lazy;
                p.rs.lazy = p.lazy;
                p.lazy = 0;
            }
        }

        void pushUp(Node p) {
            p.sum = p.ls.sum + p.rs.sum;
        }
    }
}

T3. 删除星号以后字典序最小的字符串（5 分）

解题思路

贪心。想明白有多个字典序最小的字符时，要使字典序最小，删下标最大的字符即可。

可以开 26 个栈，但感觉用优先队列好写一点。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public String clearStars(String s) {
        int n = s.length();
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.ch == o2.ch) {
                return Integer.compare(o2.i, o1.i);
            }
            return Character.compare(o1.ch, o2.ch);
        });
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == '*') {
                pq.remove();
            } else {
                pq.add(new Node(ch, i));
            }
        }

        List<Node> list = new ArrayList<>(pq);
        list.sort(Comparator.comparingInt(o -> o.i));
        StringBuilder ans = new StringBuilder();
        for (Node node : list) {
            ans.append(node.ch);
        }
        return ans.toString();
    }

    static class Node {
        char ch;
        int i;

        public Node(char ch, int i) {
            this.ch = ch;
            this.i = i;
        }
    }
}

T4. 找到按位与最接近 K 的子数组（6 分）

解题思路

按位与显然是存在单调性的（单调减），因此可用拆位 + 二分答案。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        int[][] ps = new int[n + 1][31];
        for (int bit = 0; bit < 31; bit++) {
            for (int i = 0; i < n; i++) {
                ps[i + 1][bit] = ps[i][bit];
                if ((nums[i] >> bit & 1) == 1) {
                    ps[i + 1][bit] += 1;
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int l = i, r = n;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (bitwiseAnd(ps, i, mid) <= k) r = mid;
                else l = mid + 1;
            }

            if (l < n) ans = Math.min(ans, k - bitwiseAnd(ps, i, l));
            if (l - 1 >= 0) ans = Math.min(ans, bitwiseAnd(ps, i, l - 1) - k);
        }
        return ans;
    }

    private int bitwiseAnd(int[][] ps, int l, int r) {
        int res = 0;
        for (int bit = 0; bit < 31; bit++) {
            int s = ps[r + 1][bit] - ps[l][bit];
            if (s == r - l + 1) {
                res |= 1 << bit;
            }
        }
        return res;
    }
}

（全文完）