周赛372（正难则反、枚举+贪心、异或位运算、离线+单调栈）

文章目录

周赛372
- [2937. 使三个字符串相等](https://leetcode.cn/problems/make-three-strings-equal/)
- - 模拟（正难则反）
- [2938. 区分黑球与白球](https://leetcode.cn/problems/separate-black-and-white-balls/)
- - 枚举 + 贪心
- [2939. 最大异或乘积](https://leetcode.cn/problems/maximum-xor-product/)
- - 位运算 - 异或性质
- [2940. 找到 Alice 和 Bob 可以相遇的建筑](https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/)
- - 离线 + 单调栈

周赛372

2937. 使三个字符串相等

简单

给你三个字符串 s1、s2 和 s3。你可以根据需要对这三个字符串执行以下操作 任意次数 。

在每次操作中，你可以选择其中一个长度至少为 2 的字符串并删除其 最右位置上 的字符。

如果存在某种方法能够使这三个字符串相等，请返回使它们相等所需的最小操作次数；否则，返回 -1。

示例 1：

输入：s1 = "abc"，s2 = "abb"，s3 = "ab"
输出：2
解释：对 s1 和 s2 进行一次操作后，可以得到三个相等的字符串。
可以证明，不可能用少于两次操作使它们相等。

示例 2：

输入：s1 = "dac"，s2 = "bac"，s3 = "cac"
输出：-1
解释：因为 s1 和 s2 的最左位置上的字母不相等，所以无论进行多少次操作，它们都不可能相等。因此答案是 -1 。

提示：

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

模拟（正难则反）

class Solution {
    /**
    要求三个字符串相等，删除比较困难
    则直接从i=0开始比较字符是否相等
     */
    public int findMinimumOperations(String s1, String s2, String s3) {
        int minlen = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int res = 0;
        int samepos = 0;
        for(; samepos < minlen; samepos++){
            if(s1.charAt(samepos) != s2.charAt(samepos) ||
                     s1.charAt(samepos) != s3.charAt(samepos)){
                break;
            }
        }
        if(samepos == 0) return -1;
        return s1.length() - samepos + s2.length() - samepos + s3.length() - samepos;
    }
}

比赛写的正的丑陋代码

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        String[] strs = new String[3];
        strs[0] = s1;
        strs[1] = s2;
        strs[2] = s3;
        Arrays.sort(strs, (a, b) -> a.length() - b.length());
        int cnt = 0, len = strs[0].length();
        if(strs[0].length() != strs[2].length()){
            int tmp = strs[2].length();
            cnt += tmp - len;
            strs[2] = strs[2].substring(0, len);
        }
        if(strs[0].length() != strs[1].length()){
            int tmp = strs[1].length();
            cnt += tmp - len;
            strs[1] = strs[1].substring(0, len);
        }
        while(len > 0 && (!strs[0].equals(strs[1]) || !strs[0].equals(strs[2]))){
            len -= 1;
            strs[0] = strs[0].substring(0, len);
            strs[1] = strs[1].substring(0, len);
            strs[2] = strs[2].substring(0, len);
            cnt += 3;
        }
        if(len == 0) return -1;
        return cnt;
    }
}

2938. 区分黑球与白球

中等

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

提示：

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

枚举 + 贪心

class Solution {
    /**
    倒序枚举，什么时候会将黑色球进行移动？
    当枚举到i位时是黑球，就要移动到靠近黑球的位置
    移动几次？ i右边白球出现的次数
     */
    public long minimumSteps(String s) {
        long res = 0;
        int cntw = 0, n = s.length();
        for(int i = n-1; i >= 0; i--){
            if(s.charAt(i) == '0'){
                cntw += 1;
                continue;
            }
            res += cntw;
        }
        return res;
    }
}

2939. 最大异或乘积

中等

给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2n。

由于答案可能会很大，返回它对 109 + 7 取余后的结果。

注意，XOR 是按位异或操作。

示例 1：

输入：a = 12, b = 5, n = 4
输出：98
解释：当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。
98 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

示例 2：

输入：a = 6, b = 7 , n = 5
输出：930
解释：当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。
930 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

示例 3：

输入：a = 1, b = 6, n = 3
输出：12
解释： 当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。
12 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

提示：

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

位运算 - 异或性质

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

class Solution {
    /**
    位运算  (a XOR x) * (b XOR x) 
    1. a和b 对于同一个比特位 如果一个是0 另一个是1，那么无论x填0还是1，这个比特位的结果总是0或者1
    2. 推论1： 在把同为 0 的比特位 改成 1 后，1 的总数是不变的
    3. 推论2： ax = a^x ; bx = b^x     ax + bx 是一个定值
     
     ==> 问题转化为：在 ax + bx是一个定值的情况下，求 ax * bx 的最大值
     均值定理 基本不等式
     ==> 让 ax 和 bx 尽量接近（差的绝对值尽量小）

     分配方案：
     如果大于等于n的比特位 a=b，那么把最高位的1给ax，其余的1给bx
     如果大于等于n的比特位 a>b，那么把低于n的1都给b
     */
    public int maximumXorProduct(long a, long b, int n) {
        if (a < b) {
            // 保证 a >= b
            long temp = a;
            a = b;
            b = temp;
        }

        long mask = (1L << n) - 1;
        long ax = a & ~mask; // 第 n 位及其左边，无法被 x 影响，先算出来
        long bx = b & ~mask;
        a &= mask; // 低于第 n 位，能被 x 影响
        b &= mask;

        long left = a ^ b; // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
        long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1
        ax |= one; // 先加到异或结果中
        bx |= one;

        // 现在要把 left 分配到 ax 和 bx 中
        // 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
        if (left > 0 && ax == bx) {
            // 尽量均匀分配，例如把 1111 分成 1000 和 0111
            long highBit = 1L << (63 - Long.numberOfLeadingZeros(left));
            ax |= highBit;
            left ^= highBit;
        }
        // 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
        bx |= left;

        final long MOD = 1_000_000_007;
        return (int) (ax % MOD * (bx % MOD) % MOD); // 注意不能直接 long * long，否则溢出
    }
}

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

困难

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

示例 1：

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

示例 2：

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

提示：

1 <= heights.length <= 5 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 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 {
    /**
    给定一组询问，通常可思考离线做法，将询问分组，按某一种顺序进行回答
    题意：左边矮跳到右边高
    分类讨论 对于每个询问 i 和 j，假设 i <= j
      1. 如果 i == j，答案就是 j
      2. 如果 heights[i] < heights[j], i 可以直接跳到j，答案就是j
      3. 如果 heights[i] > heights[j],左边高右边矮，怎么跳？

    按照j分类 [0,1],[0,3],[2,4],[3,4],[2,2]
    j = 1   [0, 1]
    j = 2   无需回答，答案就是2
    j = 3   [0, 3]
    j = 4   [2, 4],[3, 4]
    整理好询问后，从左到右遍历建筑，如果发现当前 idx 建筑高度 > 之前需要回答的一个询问的建筑高度
            那么，这个询问的答案就是 idx
    需要一个最小堆去维护这些询问，每次取出最小的 heights[i]，去和 heights[idx] 比较
    如果 heights[i] < heights[idx] 就立刻回答 (答案就是 idx)
    最后堆中剩下的询问 答案都是-1
     */
    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];
            if(i > j){ // 保证 i <= j
                int tmp = i; i = j; j = tmp;
            }
            if(i == j || heights[i] < heights[j]){
                ans[qi] = j; // i 直接跳到 j
            }else{
                left[j].add(new int[]{heights[i], qi});
            }
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < heights.length; i++) { // 从小到大枚举下标 i
            while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
                ans[pq.poll()[1]] = i; // 可以跳到 i（此时 i 是最小的）
            }
            for (int[] p : left[i]) {
                pq.offer(p); // 后面再回答
            }
        }
        return ans;
    }
}