【力扣周赛】第 372 场周赛（ ⭐查询离线做法）TODO

文章目录

竞赛链接
Q1：2937. 使三个字符串相等
- 竞赛时代码——检查三个字符串的最长公共前缀子串
Q2：2938. 区分黑球与白球
- 竞赛时代码
Q3：2939. 最大异或乘积
- 竞赛时代码——位运算
- 解法2—— $O (1)$ 做法👍（大量位运算技巧）
Q4：2940. 找到 Alice 和 Bob 可以相遇的建筑⭐⭐⭐⭐⭐
- 解法1——离线做法+最小堆
- 解法2——在线做法+线段树二分（TODO）
- 相关题目（强制在线）——2286. 以组为单位订音乐会的门票（TODO）
成绩记录

竞赛链接

https://leetcode.cn/contest/weekly-contest-372/

Q1：2937. 使三个字符串相等

https://leetcode.cn/problems/make-three-strings-equal/description/
在这里插入图片描述

提示：

1 <= s1.length, s2.length, s3.length <= 100
s1、s2 和 s3 仅由小写英文字母组成。

竞赛时代码——检查三个字符串的最长公共前缀子串

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        int n = Math.min(Math.min(n1, n2), n3);
        int i = 0;
        while (i < n) {
            char a = s1.charAt(i), b = s2.charAt(i), c = s3.charAt(i);
            if (a != b || b != c || a != c) break;
            i++;
        }
        if (i == 0) return -1;
        return n1 + n2 + n3 - 3 * i;
    }
}

Q2：2938. 区分黑球与白球

https://leetcode.cn/problems/separate-black-and-white-balls/description/
在这里插入图片描述

提示：

1 <= n == s.length <= 10^5
s[i] 不是 '0'，就是 '1'。

竞赛时代码

对于每个 0，它左边有多少个 1，就移动多少次。

class Solution {
    public long minimumSteps(String s) {
        long ans = 0, c = 0;
        for (char ch: s.toCharArray()) {
            if (ch == '1') c++;
            else ans += c;
        }
        return ans;
    }
}

Q3：2939. 最大异或乘积

https://leetcode.cn/problems/maximum-xor-product/description/
在这里插入图片描述

提示：

0 <= a, b < 250
0 <= n <= 50

竞赛时代码——位运算

要想乘积最大，两个数字在总和一定的情况下最好相差不大。

class Solution {
    final long MOD = (long)1e9 + 7;
    
    public int maximumXorProduct(long a, long b, int n) {
        // aa和bb记录a xor x 和 b xor x 的结果
        long aa = 0, bb = 0;
        for (int i = 62; i >= n; --i) {
            if ((a >> i & 1) == 1) aa |= 1L << i;
            if ((b >> i & 1) == 1) bb |= 1L << i;
        }
        // 为a和b尽量均匀分配
        for (int i = n - 1; i >= 0; --i) {
            boolean x = (a >> i & 1) == 1, y = (b >> i & 1) == 1;
            if (x == y) {           // 如果x和y可以同时为1
                aa |= 1L << i;
                bb |= 1L << i;
            } else{                 // 不能，就分配给当前小的
                if (aa <= bb) {
                    aa |= 1L << i;
                } else {
                    bb |= 1L << i;
                }
            }
        }
        return (int)(((aa % MOD) * (bb % MOD)) % MOD);
    }
}

解法2—— $O (1)$ 做法👍（大量位运算技巧）

https://leetcode.cn/problems/maximum-xor-product/solutions/2532915/o1-zuo-fa-wei-yun-suan-de-qiao-miao-yun-lvnvr/

其实所谓的均匀分配，对于二进制来说，当最高位分配给一个之后，其它的所有位都要分配给另一个了。
在这里插入图片描述

class Solution {
    public int maximumXorProduct(long a, long b, int n) {
        // 保证 a >= b
        if (a < b) {
            long temp = a;
            a = b;
            b = temp;
        }

        long mask = (1L << n) - 1;
        // 取出被n异或截断之前的
        long ax = a & ~mask;
        long bx = b & ~mask;
        // 低于第n位的，能被x影响
        a &= mask;
        b &= mask;

        // left是可分配的位置，a xor x和b xor x一个是1，另一个是0
        long left = a ^ b;
        long one = mask ^ left; // 这些是不需要分配的
        ax |= one;
        bx |= one;

        // 现在把left分配到ax和bx
        // 根据基本不等式（均值定理），分配后应当使ax和bx尽量接近，乘积才能尽量大
        if (left > 0 && ax == bx) {
            long highBit = 1L << (63 - Long.numberOfLeadingZeros(left));
            ax |= highBit;
            left ^= highBit;
        }
        // 如果 a & ~mask 更大，则应当全部分给bx
        bx |= left;
        final long MOD =1_000_000_007;
        return (int)(ax % MOD * (bx % MOD) % MOD);
    }
}

确实是 $O (1)$ 的，里面用到了很多位运算的技巧。

Q4：2940. 找到 Alice 和 Bob 可以相遇的建筑⭐⭐⭐⭐⭐

https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/description/
在这里插入图片描述

提示：

1 <= heights.length <= 5 * 10^4
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 10^4
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1

解法1——离线做法+最小堆

https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/solutions/2533058/chi-xian-zui-xiao-dui-pythonjavacgo-by-e-9ewj/

离线：按照自己定义的某种顺序回答询问（而不是按照输入顺序一个个地回答）。

在这里插入图片描述

class Solution {
    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int[] ans = new int[queries.length];
        Arrays.fill(ans, -1);
        // 记录该位置 作为右边下标 需要回复的左边下标 和 对应的查询下标
        List<int[]>[] left = new ArrayList[heights.length];
        Arrays.setAll(left, e -> new ArrayList<>());
        // 枚举查询
        for (int qi = 0; qi < queries.length; qi++) {
            int i = queries[qi][0], j = queries[qi][1];
            // 保证 i <= j
            if (i > j) {
                int temp = i;
                i = j;
                j = temp;
            }
            if (i == j || heights[i] < heights[j]) {
                // 如果能回答就先回答
                ans[qi] = j;
            } else {
                // 还不能回答，离线
                left[j].add(new int[]{heights[i], qi});   
            }
        }

        // 最小堆，因为高度更小的位置更容易回答
        PriorityQueue<int[]> pq  = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // 从小到大枚举下标 i
        for (int i = 0; i < heights.length; ++i) {
            // 当前位置更高，可以作为答案
            while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
                ans[pq.poll()[1]] = i;
            }
            // 该部分的答案之后可以回答
            for (int[] p: left[i]) {
                pq.offer(p);
            }
        }
        return ans;
    }
}