LeetCode周记 EP14

2024-10-05

字数统计: 3.5k字 | 阅读时长: 17分

前言

面的有点麻了，做题反而有意思点。

本周主题：优化遍历、滑动窗口、线段树、集合

题目：

240923每日一题—Best Sightseeing Pair
240925每日一题—Naming a Company
240927每日一题—Take K of Each Character From Left and Right
240928每日一题—Booking Concert Tickets in Groups

Best Sightseeing Pair

Best Sightseeing Pair

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

暴力超时，优化成排序还是超时…没想到如何优化遍历，于是记录一下。

// author: SilenceZheng66
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int res = 0;
        int n = values.length;
        int[][] arr1 = new int[n][2];
        for(int i=0;i<n;i++){
            arr1[i] = new int[]{i, values[i]-i};
        }
        Arrays.sort(arr1, (a,b)->b[1]-a[1]);
        for(int[] x:arr1){
            for(int i=0;i<x[0];i++){
                res = Math.max(res, values[i]+i+x[1]);
            }
        }
        return res;
    }
}

优化遍历

其实对于每一个$values[j]-j$就是要找到$[0, j-1]$中最大的$values[i]+i$。所以其实从前往后遍历的过程中维护$mx = Max(values[i]+i)$即可。

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, mx = values[0] + 0;
        for (int j = 1; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }
}

Naming a Company

用哈希映射 names 存储所有的候选名字，它的键是首字母，值是去除首字母后，每个候选名字的剩余部分。因此，我们可以枚举两个不同的首字母 $p r e_A$ 和 $p r e_B$，计算以它们为首字母的有效的公司名字数量。

两集合$p r e_A$ 和 $p r e_B$的符合条件组合数量为：

$\left.\mid \text { names }\left[\text { pre }_A\right]-\text { names }\left[\text { pre }_B\right]|\times|{\text { names }\left[\text { pre }_B\right]-\text { names }[\text { pre }}_A\right] \mid$

其中 $|\cdot|$ 表示集合大小， $-$ 表示集合的差集运算。枚举所有不同的 $\mathrm{pre}_A$ 和 $p r e_B$, 即可得到最终的答案。

需要注意的是上式需要计算两次集合的差集，但实际上我们只需要知道差集的大小而不是差集本身。对于集合 $A, B$, 有 $A-B=A \backslash(A \cap B)$, 其中 $\backslash$ 表示将元素去除, $\cap$ 表示集合的交集运算。因此，我们只需要计算一次集合的交集即可，通过 $|A|-|A \cap B|$ 以及 $|B|-|A \cap B|$ 即可快速得到两个差集的大小。

class Solution {
    public long distinctNames(String[] ideas) {
        Map<Character, Set<String>> names = new HashMap<Character, Set<String>>();
        for (String idea : ideas) names.computeIfAbsent(idea.charAt(0), x->new HashSet<String>()).add(idea.substring(1));
        long ans = 0;
        for (Map.Entry<Character, Set<String>> entryA : names.entrySet()) {
            char preA = entryA.getKey();
            Set<String> setA = entryA.getValue();
            for (Map.Entry<Character, Set<String>> entryB : names.entrySet()) {
                char preB = entryB.getKey();
                Set<String> setB = entryB.getValue();
                if (preA == preB) {
                    continue;
                }
                int intersect = getIntersectSize(setA, setB);
                ans += (long) (setA.size() - intersect) * (setB.size() - intersect);
            }
        }
        return ans;
    }

    public int getIntersectSize(Set<String> a, Set<String> b) {
        int ans = 0;
        for (String s : a) {
            if (b.contains(s)) {
                ans++;
            }
        }
        return ans;
    }
}

Take K of Each Character From Left and Right

Take K of Each Character From Left and Right

You are given a string s consisting of the characters ‘a’, ‘b’, and ‘c’ and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

一开始的思路是模拟，然后对于左右都可取的情况需要分支尝试，这样会造成分支太多超时。其实这也是正向模拟走不通的原因，我们在选取左右两边时无法了解后续情况。

// author: SilenceZheng66
class Solution {
    int k;
    public int takeCharacters(String s, int k) {
        this.k = k;
        int n = s.length();
        int ta = 0, tb = 0, tc = 0;
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='a') ta++;
            else if(s.charAt(i)=='b') tb++;
            else tc++;
        }
        if(ta<k||tb<k||tc<k) return -1;
        // what is the problem?
        // let's define the last pick index from left to right is f(i)
        // the penultimate valid pick index is f(i-1)
        // then the picks from f(i-1) to f(i) is redundant
        // if s[f(i)] == x and there is index j from right to left
        // where s[j] == x and rightEnd - j < f(i)-f(i-1)
        // It's a better solution to pick f(i-1) and j instead of f(i)
        // Let's define f(i) is next pick, and the computation relys on following parameters:
        // 1. what we got, use count('a'), count('b') and count('c')
        // 2. 2 pointers l and r, which means where we picked now
        int l = 0, r = n-1;
        int[] cnt = new int[3];
        return pick(s, l, r, cnt);
    }

    public int pick(String s, int l, int r, int[] cnt){
        if(cnt[0]<k||cnt[1]<k||cnt[2]<k){
            int pl = l, pr = r, cl = 0, cr = 0;
            while(pl+cl<s.length()-1&&!valid(s.charAt(pl+cl), cnt)) cl++;
            while(pr-cr>0&&!valid(s.charAt(pr-cr), cnt)) cr++;
            if(cl==cr){
                int[] cnt1 = Arrays.copyOf(cnt, cnt.length);
                int[] cnt2 = Arrays.copyOf(cnt, cnt.length);
                take(s.charAt(pl+cl), cnt1);
                take(s.charAt(pr-cr), cnt2);
                return Math.min(pick(s, pl+cl+1, r, cnt1), pick(s, l, pr-cr-1, cnt2));
            }
            else if(cl>cr){
                int[] cnt1 = Arrays.copyOf(cnt, cnt.length);
                take(s.charAt(pr-cr), cnt1);
                return pick(s, l, pr-cr-1, cnt1);
            }else{
                int[] cnt1 = Arrays.copyOf(cnt, cnt.length);
                take(s.charAt(pl+cl), cnt1);
                return pick(s, pl+cl+1, r, cnt1);
            }
        }else return s.length()-(r-l+1);
    }

    public boolean valid(char ch, int[] cnt){
        if((ch=='a'&&cnt[0]<k)||(ch=='b'&&cnt[1]<k)||(ch=='c'&&cnt[2]<k)) return true;
        return false;
    }

    public void take(char ch, int[] cnt){
        if(ch=='a') cnt[0]++;
        else if(ch=='b') cnt[1]++;
        else cnt[2]++;
    } 
}

滑动窗口

可以这样考虑，假如 $s$ 中有 3 个 $\mathrm{a}, 4$ 个 $\mathrm{b}, 5$ 个 $\mathrm{c}, k=2$, 每种字母至少取走 2 个, 等价于剩下的字母至多有 1 个 $a, 2$ 个 $b$ 和 3 个 $c$ 。

由于只能从 $s$ 最左侧和最右侧取走字母, 所以剩下的字母是 $s$ 的子串。
设 $s$ 中的 $\mathrm{a}, \mathrm{b}, \mathrm{c}$ 的个数分别为 $x, y, z$, 可以转化问题为:

计算 $s$ 的最长子串长度, 该子串满足 $\mathrm{a}, \mathrm{b}, \mathrm{c}$ 的个数分别至多为 $x-k, y-k, z-k$ 。

由于子串越短越能满足要求, 越长越不能满足要求, 有单调性, 可以用滑动窗口解决。

在实现上，与其维护窗口内的字母个数, 不如直接维护窗口外的字母个数, 这也是我们取走的字母个数。

一开始, 假设我们取走了所有的字母。或者说, 初始窗口是空的, 窗口外的字母个数就是 $s$ 的每个字母的出现次数。
窗口从左向右滑动，右端点字母进入窗口后, 该字母取走的个数减一。
如果减一后, 窗口外该字母的个数小于 $k$, 说明子串太长了, 或者取走的字母个数太少了,那么就不断右移左端点, 把左端点字母移出窗口, 相当于我们取走移出窗口的字母, 直到该字母个数等于 $k$, 退出内层循环。
内层循环结束后, 用窗口长度 right - left +1 更新子串长度的最大值。

最后, 原问题的答案为 $n$ 减去子串长度的最大值。特别地, 如果 $s$ 中某个字母的个数不足 $k$, 那么无法满足题目要求, 返回 -1 。

class Solution {
    public int takeCharacters(String S, int k) {
        char[] s = S.toCharArray();
        int[] cnt = new int[3];
        for (char c : s) {
            cnt[c - 'a']++; // 一开始，把所有字母都取走
        }
        if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
            return -1; // 字母个数不足 k
        }

        int mx = 0; // 子串最大长度
        int left = 0;
        for (int right = 0; right < s.length; right++) {
            int c = s[right] - 'a';
            cnt[c]--; // 移入窗口，相当于不取走 c
            while (cnt[c] < k) { // 窗口之外的 c 不足 k
                cnt[s[left] - 'a']++; // 移出窗口，相当于取走 s[left]
                left++;
            }
            mx = Math.max(mx, right - left + 1);
        }
        return s.length - mx;
    }
}

Booking Concert Tickets in Groups

题目太长就不粘了，简单来说就是实现一个演唱会购票类，可以实现连座和散座订票。

按照题目原意写出基础解法并不难，只是会OOM。

// author: SilenceZheng66
class BookMyShow {
    // 用最后一个元素记录剩余容量, 剩余的0表示空座
    int[][] hall; 
    int n;
    int m;

    public BookMyShow(int n, int m) {
        hall = new int[n][m+1];
        this.n = n;
        this.m = m;
        for(int i=0;i<n;i++) hall[i][m] = m;
    }
    
    public void view(){
        for(int[] r:hall) System.out.println(Arrays.toString(r));
        System.out.println();
    }

    public int[] gather(int k, int maxRow) {
        if(preBook(k, maxRow, false)) return book(k, maxRow, false);
        else return new int[0];
    }
    
    public boolean scatter(int k, int maxRow) {
        if(preBook(k, maxRow, true)){
            book(k, maxRow, true);
            return true;
        }else return false;
    }

    private boolean preBook(int k, int maxRow, boolean isScatter){
        if(isScatter){
            int cnt = 0;
            for(int i=0;i<=maxRow;i++){
                cnt+=hall[i][m];
                if(cnt>=k) return true;
            }
            return false;
        }else{
            for(int i=0;i<=maxRow;i++){
                if(hall[i][m]>=k) return true;
            }
            return false;
        }
    }

    private int[] book(int k, int maxRow, boolean isScatter){
        int[] res = new int[2];
        Arrays.fill(res, -1);
        int toDo = k;
        if(isScatter){
            int p = 0;
            while(toDo>0){
                if(hall[p][m]==0){
                    p++;
                    continue;
                }
                if(hall[p][m]>=toDo){
                    doBook(p, m-hall[p][m], m-hall[p][m]+toDo);
                    toDo = 0;
                } 
                else{
                    toDo-=hall[p][m];
                    doBook(p, m-hall[p][m], m);
                }
                p++;
            }
        }else{
            for(int i=0;i<=maxRow;i++){
                if(hall[i][m]>=toDo){
                    res[0] = i;
                    res[1] = m-hall[i][m];
                    doBook(i, m-hall[i][m], m-hall[i][m]+toDo);
                    break;
                }
            }
        }
        return res;
    }

    private void doBook(int row, int s, int e){
        for(int i=s;i<e;i++) hall[row][i] = 1;
        hall[row][m]-=(e-s);
        // view();
    }
}

线段树

将每一排座位看成一个整体，可将两种操作总结如下：

gather：在前 maxRow 排中，找第一个还能至少有 k 个空座位的排，预定 k 个连续的座位。如果有这样的排，返回编号，以及在预定前有多少非空座位；如果没有这样的排，返回空列表。
scatter：在前 maxRow 个排中预定总量为 k 的座位。从左到右选择有空座位的排依次占座。如果无法预定总量为 k 的座位，则不执行操作，并返回 false；否则执行操作，并返回 true。

此时将原问题压缩为一维数组，能这样做的原因是两种操作均不会产生“间隔的空座位”。因此需要的操作如下：

求出前 maxRow 排中，第一个剩余容量 ≥k，也就是已预定量 ≤ m−k 的排。
维护每排的已预定量。
维护前 maxRow 排的已预定量之和，从而判断 scatter 能否实现。

可以用线段树处理上述操作，线段树维护每个区间（区间即某几排）已预定量的最小值 $\min$ ，以及每个区间的已预定量之和 $sum$。

对于 gather，从线段树的根节点开始递归：

如果当前区间 $\min > m-k$, 则无法预定 $k$ 个连续座位，返回 0 。
如果当前区间长度为 1 ，返回区间端点。
如果左半区间 $\min \leq m-k$, 则答案在左半区间中, 递归左半区间。
否则如果 maxRow 在右半区间内, 递归右半区间。
否则返回 -1 ，表示没有符合条件的排。

上述过程叫做线段树二分，

对于 scatter，如果区间 $[0$, maxRow] 的已预定量之和大于 $m \cdot(\operatorname{maxRow}+1)-k$ ，则无法执行操作。否则可以执行操作。从第一个没有装满，也就是已预定量 $\leq m-1$ 的排开始预定，这也可以用线段树二分求出。

class BookMyShow {
    private int n;
    private int m;
    private int[] min;
    private long[] sum;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        int size = 2 << (32 - Integer.numberOfLeadingZeros(n)); // 比 4n 更小
        min = new int[size];
        sum = new long[size];
    }

    public int[] gather(int k, int maxRow) {
        // 找第一个能预定 k 个座位的row
        int r = findFirst(1, 0, n - 1, maxRow, m - k);
        if (r < 0) { // 没有这样的row
            return new int[]{};
        }
        int c = (int) querySum(1, 0, n - 1, r, r);
        update(1, 0, n - 1, r, k); // 预定
        return new int[]{r, c};
    }

    public boolean scatter(int k, int maxRow) {
        // [0,maxRow] 的已预定量之和
        long s = querySum(1, 0, n - 1, 0, maxRow);
        if (s > (long) m * (maxRow + 1) - k) {
            return false; // 空座位不足
        }
        // 从第一个没有定满的row开始
        int i = findFirst(1, 0, n - 1, maxRow, m - 1);
        while (k > 0) {
            int left = Math.min(m - (int) querySum(1, 0, n - 1, i, i), k);
            update(1, 0, n - 1, i, left); // 预定
            k -= left;
            i++;
        }
        return true;
    }

    // 把下标 i 上的元素值增加 val
    private void update(int o, int l, int r, int i, int val) {
        if (l == r) {
            min[o] += val;
            sum[o] += val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            update(o * 2, l, m, i, val);
        } else {
            update(o * 2 + 1, m + 1, r, i, val);
        }
        min[o] = Math.min(min[o * 2], min[o * 2 + 1]);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
    }

    // 返回区间 [L,R] 内的元素和
    private long querySum(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return sum[o];
        }
        long res = 0;
        int m = (l + r) / 2;
        if (L <= m) {
            res = querySum(o * 2, l, m, L, R);
        }
        if (R > m) {
            res += querySum(o * 2 + 1, m + 1, r, L, R);
        }
        return res;
    }

    // 返回区间 [0,R] 中 <= val 的最靠左的位置，不存在时返回 -1
    private int findFirst(int o, int l, int r, int R, int val) {
        if (min[o] > val) {
            return -1; // 整个区间的元素值都大于 val
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        if (min[o * 2] <= val) {
            return findFirst(o * 2, l, m, R, val);
        }
        if (R > m) {
            return findFirst(o * 2 + 1, m + 1, r, R, val);
        }
        return -1;
    }
}

参考文献

[1] https://leetcode.cn/problems/booking-concert-tickets-in-groups/solutions/1523876/by-endlesscheng-okcu/?envType=daily-question&envId=2024-09-28
[2] https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/solutions/2031995/on-shuang-zhi-zhen-by-endlesscheng-4g9p/?envType=daily-question&envId=2024-09-27

后记

首发于 silencezheng.top，转载请注明出处。