LeetCode-372

Q1

100131. 使三个字符串相等

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

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

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

示例 1：

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

示例 2：

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

提示：

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

直接模拟找到最左匹配即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        if s1[0] != s2[0] or s1[0] != s3[0] or s2[0] != s3[0]:
            return -1
        n = min(len(s1), len(s2), len(s3))
        i = 0
        while i < n and s1[i] == s2[i] == s3[i]:
            i += 1
        ans = 0
        ans += len(s1) - i
        ans += len(s2) - i
        ans += len(s3) - i
        return ans

Q2

100122. 区分黑球与白球

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

本质上就是求逆序对，但是我没有直接想到，我想到的是一个模拟的过程，大致思想如下图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minimumSteps(self, s: str) -> int:
        c = Counter(list(s))
        zero = c['0']
        one = c['1']
        print(one, zero)
        ans = 0
        for i in range(zero):
            if s[i] == '1':
                ans += zero - i
        for j in range(len(s) - 1, len(s) - one - 1, -1):
            if s[j] == '0':
                ans += (j - len(s) + one)
        return ans

Q3

100119. 最大异或乘积

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

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

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

示例 1：

1
2
3
4
输入：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：

1
2
3
4
输入：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：

1
2
3
4
输入：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

贪心思想，不知道该怎样证明。从低到高只要能将结果变大就要这位，要么不要，还有一种就是从高位到低位哪个小就给哪个异或。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10 ** 9 + 7
        result = a * b
        for i in range(n):
            xx, yy = a ^ (1 << i), b ^ (1 << i)
            if xx * yy > a * b:
                a, b = xx, yy
            result = max(result, a * b)

        return result % MOD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maximumXorProduct(long long a, long long b, int n) {
        const int MOD = 1e9 + 7;
        // 把输入数据大于等于第 n 位的部分先截出来，它们不受异或操作的影响
        long long p = (a >> n) << n, q = (b >> n) << n;
        for (int i = n - 1; i >= 0; i--) {
            // 看 a 和 b 第 i 位是否相同
            int x = a >> i & 1;
            int y = b >> i & 1;
            // 相同则两者都可以获得一个 1
            if (x == y) p |= 1LL << i, q |= 1LL << i;
            // 不同则谁小谁获得 1
            else if (p < q) p |= 1LL << i;
            else q |= 1LL << i;
        }
        // 先取个模防止乘法溢出
        p %= MOD;
        q %= MOD;
        return p * q % MOD;
    }
};

作者：TsReaper
链接：https://leetcode.cn/problems/maximum-xor-product/
来源：力扣（LeetCode）

Q4

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：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
3
4
5
6
7
8
9
输入：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

因为两人的顺序对结果无关，所以可以先对ai,bi进行排序，设x,y为两人位置, x <= y,若x == y,则ans[i] = x,若height[y] > height[x]则ans[i] = y,对于其他情况问题的转换就成了下标第一个大于y的坐标z且height[z] > height[x],这就成为了一个二维偏序问题，可以采用离线查询，按照y从到大到小排序，反向过滤height,利用树状数组就可以解决本问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights)
        m = len(queries)
        tree = [inf] * (n + 1)
        ans = [0] * m
        unique_queries = sorted(list(set(heights)))
        query_map = {e: idx + 1 for idx, e in enumerate(unique_queries)}  # 离散化

        remaining_queries = []

        for i in range(m):
            x, y = min(queries[i]), max(queries[i])
            if x == y or heights[y] > heights[x]:
                ans[i] = y
            else:
                remaining_queries.append((x, y, i))

        def low_bit(a: int) -> int:
            return a & -a

        def update(i: int, v: int) -> None:
            while i < len(tree):
                tree[i] = min(tree[i], v)
                i += low_bit(i)

        def get(i: int) -> int:
            ret = inf
            while i > 0:
                ret = min(ret, tree[i])
                i -= low_bit(i)
            return -1 if ret == inf else ret

        remaining_queries.sort(key=lambda e: e[1], reverse=True)
        i = n - 1

        for e in remaining_queries:
            v, idx = len(unique_queries) + 1 - query_map[heights[e[0]]], e[2]
            while i > e[1]:
                update(len(unique_queries) + 1 - query_map[heights[i]], i)
                i -= 1
            ans[idx] = get(v - 1)

        return ans
算法
#leetcode
LeetCode-372
http://example.com/2023/11/19/LeetCode-372/
作者
ykexc
发布于
2023年11月19日
许可协议