leetcode weekly contes 372

T3 是个好题目，虽然没有什么复杂的算法，但是主要是涉及到数学的问题。T4 就是一个模板题目，反而没什么太大难度。

100131. 使三个字符串相等

给你三个字符串 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 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-372/problems/make-three-strings-equal/

题意

枚举

思路

由于题目本质就是找到三个字符串的最长前缀，假设最长前缀为 $n$，则三个字符串除相同的前缀之外全部删除即可，我们直接计算即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定的三个字符串的长度之和。
空间复杂度：$O(1)$。

代码

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        tot = 0
        for x, y, z in zip(s1, s2, s3):
            print(x, y, z)
            if x == y and y == z:
                tot += 1
            else:
                break
        return len(s1) + len(s2) + len(s3) - 3 * tot if tot > 0 else -1

100122. 区分黑球与白球

桌子上有 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'。

地址

https://leetcode.cn/contest/weekly-contest-372/problems/separate-black-and-white-balls/

题意

枚举

思路

直接枚举即可，每次找到左右两端需要进行交换的两个字符 $s[l],s[r]$ 进行交换，统计需要移动的步骤即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度。
空间复杂度：$O(1)$，其中 $n$ 表示给定字符串的长度。

代码

class Solution:
    def minimumSteps(self, s: str) -> int:
        l, r = 0, len(s) - 1
        res = 0
        while l < r:
            while l < r and s[l] == '0':
                l += 1
            while l < r and s[r] == '1':
                r -= 1
            if l < r:
                res += r - l
                l += 1
                r -= 1
        return res

100119. 最大异或乘积

给你三个整数 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/contest/weekly-contest-372/problems/maximum-xor-product/

题意

贪心

思路

难得遇到好的题目，还是非常不容易的题目。贪心的思路比较好想，对于 $a$ 与 $b$ 都相同的位上此时 $x$ 则取与其相反的数，但是对于 $a$ 与 $b$ 不同的第 $i$ 位上时此时该如何取呢？这就需要贪心策略了：

对于所有低于 $n$ 位的 $1$ 我们可以随意分配，假设为 $a$ 分配了 $i$ 个元素为 $1$, 为 $b$ 分配了 $j$ 个元素为 $1$，此时 $ax + bx = a \oplus b$，此时要使得 $ax$ 与 $bx$ 尽量的接近才行，实际我们可以将最高位分配给 $a$，其余位分配给 $b$ 即可。
但是由于可能存在高于 $n$ 位的 $1$ 需要分配，此时假设 $a$ 的高位与 $b$ 的高位相等，则此时等价于情况 $1$，否则如果 $a > b$, 则将 $n$ 位以下的 $1$ 全部分配给 $b$；
时间复杂度：$O(n)$，其中$n$ 表示给定的元素；
空间复杂度：$O(1)$；

代码

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        ax = (a >> n) << n
        bx = (b >> n) << n
        for i in range(n - 1, -1, -1):
            x = a >> i & 1
            y = b >> i & 1
            if x == y:
                ax |= 1 << i
                bx |= 1 << i
            elif ax > bx:
                bx |= 1 << i
            else:
                ax |= 1 << i
        return ax * bx % (10**9 + 7)

100110. 找到 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/contest/weekly-contest-372/problems/find-building-where-alice-and-bob-can-meet/

题意

二分查找

思路

题目本质不算很难，假设当前给定的查询位置为 $(i,j)$，此时处理如下：

如果 $i = j$ 时，此时则二者不需要移动，直接返回 $i$ 即可；
如果 $i > j，heights[i] > heights[j]$ 时，此时 $j$ 移动到 $i$ 即可，此时返回 $i$ 即可；
如果 $i < j，heights[i] < heights[j]$ 时，此时 $i$ 移动到 $j$ 即可，此时返回 $j$ 即可；
其余情况下，此时则在区间 $[\max(i,j),n-1]$ 找到大于 $\max(heights[i], heights[j])$ 且索引最小的元素即可，此时我们想到了线段树上二分查找，在区间 $[\max(i,j),n-1]$ 找到第一个大于等于 $\max(heights[i], heights[j])$ 的元素索引即可。
- 线段树本身保存当前区间的最大元素，假设查询区间为 $[l,r]$，此时如果我们先再左半区间查找，如果找到大于 $val$ 的值则直接返回，否则再查找右半区间即可；
- 线段树的二分查找就比较简单了。

复杂度分析:

时间复杂度：$O(n \log U)$，其中 $n$ 表示数组的长度，$U$ 表示数组中的最大长度，我们分别存储
空间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度，$U$ 表示数组中的最大长度;

代码

class SegNode:
    def __init__(self):
        self.l = 0
        self.r = 0
        self.maxVal = 0

class SegTree:
    def __init__(self, nums):
        self.tree = [SegNode()] * (4 * len(nums) + 7)
        self.buildTree(1, 0, len(nums) - 1, nums)
    
    def buildTree(self, idx, l, r, nums):
        if l > r:
            return
        self.tree[idx].l = l
        self.tree[idx].r = r
        if l == r:
            self.tree[idx].maxVal = nums[l]
            return
        
        mid = (l + r) // 2
        self.buildTree(2 * idx, l, mid, nums)
        self.buildTree(2 * idx + 1, mid + 1, r, nums)
        self.pushUpTree(idx)
    
    def pushUpTree(self, idx):
        self.tree[idx].maxVal = max(self.tree[idx * 2].maxVal, self.tree[idx * 2 + 1].maxVal)
    
    def queryTree(self, idx, l, r, val):
        if r < self.tree[idx].l or l > self.tree[idx].r or self.tree[idx].maxVal <= val:
            return -1
        if self.tree[idx].l == self.tree[idx].r:
            return l
        mid = (self.tree[idx].l + self.tree[idx].r) // 2
        if r <= mid:
            return self.queryTree(idx * 2, l, r, val)
        elif l > mid:
            return self.queryTree(idx * 2 + 1, l, r, val)
        else:
            if self.tree[idx * 2].maxVal > val:
                ret = self.queryTree(idx * 2, l, mid, val)
                if ret == -1:
                    return self.queryTree(idx * 2 + 1, mid + 1, r, val)
                else:
                    return ret
            else:
                return self.queryTree(idx * 2 + 1, mid + 1, r, val)

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        tree = SegTree(heights)
        ans = []
        for x, y in queries:
            if x == y:
                ans.append(x)
            elif x > y and heights[x] > heights[y]:
                ans.append(x)
            elif x < y and heights[x] < heights[y]:
                ans.append(y)
            else:
                j, val = max(x, y), max(heights[x], heights[y])
                ans.append(tree.queryTree(1, j + 1, len(heights) - 1, val))
        return ans

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 370 leetcode biweekly contes 117 →

扫描二维码，分享此文章