leetcode contest 377

整体来说题目还算有点难度，不过倒不是特别变态的题目，难度还可以接受

2974. 最小数字游戏

你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ，同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏，游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下：

• 每一轮，Alice 先从 nums 中移除一个 最小 元素，然后 Bob 执行同样的操作。
• 接着，Bob 会将移除的元素添加到数组 arr 中，然后 Alice 也执行同样的操作。
• 游戏持续进行，直到 nums 变为空。

返回结果数组 arr 。

示例 1：

输入：nums = [5,4,2,3]
输出：[3,2,5,4]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [3,2] 。
第二轮开始时，nums = [5,4] 。Alice 先移除 4 ，然后 Bob 移除 5 。接着他们都将元素添加到 arr 中，arr 变为 [3,2,5,4] 。

示例 2：

输入：nums = [2,5]
输出：[5,2]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [5,2] 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums.length % 2 == 0

地址

https://leetcode.cn/contest/weekly-contest-377/problems/minimum-number-game/

题意

模拟

思路

1. 模拟即可，将数组按照从小到大排序，然后相邻元素交换即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        nums.sort()
        for i in range(0, len(nums), 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        return nums

2975. 移除栅栏得到的正方形田地的最大面积

显示英文描述

我的提交返回竞赛

• 通过的用户数1142
• 尝试过的用户数1915
• 用户总通过次数1170
• 用户总提交次数7471
• 题目难度****Medium

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 109 + 7 取余 后的值。

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

提示：

• 3 <= m, n <= 109
• 1 <= hFences.length, vFences.length <= 600
• 1 < hFences[i] < m
• 1 < vFences[i] < n
• hFences 和 vFences 中的元素是唯一的。

地址

https://leetcode.cn/contest/weekly-contest-377/problems/maximum-square-area-by-removing-fences-from-a-field/

题意

数学问题 + 贪心

思路

1. 假设我们知道正方形的左上方的顶点为 $(x, y)$ , 此时则其右下方的顶点一定为 $(x + l, y + l)$，此时假设统计所有位置 $x-y$ 值相同的点，即任意满足 $x_1-y_1 = x_2-y_2$ 的两点 $(x_1,y_1),(x_2,y_2)$ 一定可以构成正方形，二者构成的正方形的边长为 $|x_1-x_2|$，因此我们只需要找到满足 $x_i-y_i$ 相同的位置中最大的 $x$ 与最小的 $x$ 构成的差即为当前可以构成的最大的正方形的边长。
2. 复杂度分析：

• 时间复杂度：$O(m\times n)$，其中 $m,n$ 表示给定的两个数组的长度。
• 空间复杂度：$O(m+n)$。

代码

class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        hFences.append(1)
        hFences.append(m)
        vFences.append(1)
        vFences.append(n)
        hFences.sort()
        vFences.sort()
        cnt = {}
        mod, res = 10**9 + 7, -1
        l = 0
        for x in hFences:
            for y in vFences:
                if x - y in cnt:
                    l = max(l, x - cnt[x - y])
                else:
                    cnt[x - y] = x
        if l == 0:
            return -1
        return l * l % mod

2976. 转换字符串的最小成本 I

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。

另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。

返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe" ：
- 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。
- 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。
- 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。
- 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。
可以证明这是可能的最小成本。

示例 2：

输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
输出：12
解释：要将字符 'a' 更改为 'b'：
- 将字符 'a' 更改为 'c'，成本为 1 
- 将字符 'c' 更改为 'b'，成本为 2 
产生的总成本是 1 + 2 = 3。
将所有 'a' 更改为 'b'，产生的总成本是 3 * 4 = 12 。

示例 3：

输入：source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
输出：-1
解释：无法将 source 字符串转换为 target 字符串，因为下标 3 处的值无法从 'd' 更改为 'e' 。

提示：

• 1 <= source.length == target.length <= 105
• source、target 均由小写英文字母组成
• 1 <= cost.length== original.length == changed.length <= 2000
• original[i]、changed[i] 是小写英文字母
• 1 <= cost[i] <= 106
• original[i] != changed[i]

地址

https://leetcode.cn/contest/weekly-contest-377/problems/minimum-cost-to-convert-string-i/

题意

求最短距离

思路

1. 本质上是求任意两个字符之间的最小替换代价，此时我们可以用 floyd 算法求出任意两个不同字符之间的最小替换代价，然后按照题目局要求将 source 与 target之间进行替换即可。
2. 复杂度分析：

• 时间复杂度：$O(n + |\Sigma|^3)$，其中 $n$ 表示给定字符串的长度。
• 空间复杂度：$O(|\Sigma|)$。

代码

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        dist = [[inf] * 26 for _ in range(26)]
        for i in range(len(original)):
            x, y = ord(original[i]) - ord('a'), ord(changed[i]) - ord('a')
            dist[x][y] = min(cost[i], dist[x][y])
        
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] != inf and dist[k][j] != inf and dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        res = 0
        for i in range(len(source)):
            x = ord(source[i]) - ord('a')
            y = ord(target[i]) - ord('a')
            if x != y:
                if dist[x][y] != inf:
                    res += dist[x][y]
                else:
                    return -1
        return res

2977. 转换字符串的最小成本 II

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。

另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。 你可以执行 任意数量 的操作，但是任两次操作必须满足 以下两个 条件 之一 ：

• 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 b < c 或 d < a 。换句话说，两次操作中选择的下标 不相交 。
• 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。

返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将 "abcd" 转换为 "acbe"，执行以下操作：
- 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。
- 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。
- 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。
- 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。 
可以证明这是可能的最小成本。

示例 2：

输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
输出：9
解释：将 "abcdefgh" 转换为 "acdeeghh"，执行以下操作：
- 将子串 source[1..3] 从 "bcd" 改为 "cde" ，成本为 1 。
- 将子串 source[5..7] 从 "fgh" 改为 "thh" ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。
- 将子串 source[5..7] 从 "thh" 改为 "ghh" ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。
产生的总成本是 1 + 3 + 5 = 9 。
可以证明这是可能的最小成本。

示例 3：

输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
输出：-1
解释：无法将 "abcdefgh" 转换为 "addddddd" 。
如果选择子串 source[1..3] 执行第一次操作，以将 "abcdefgh" 改为 "adddefgh" ，你无法选择子串 source[3..7] 执行第二次操作，因为两次操作有一个共用下标 3 。
如果选择子串 source[3..7] 执行第一次操作，以将 "abcdefgh" 改为 "abcddddd" ，你无法选择子串 source[1..3] 执行第二次操作，因为两次操作有一个共用下标 3 。

提示：

• 1 <= source.length == target.length <= 1000
• source、target 均由小写英文字母组成
• 1 <= cost.length == original.length == changed.length <= 100
• 1 <= original[i].length == changed[i].length <= source.length
• original[i]、changed[i] 均由小写英文字母组成
• original[i] != changed[i]
• 1 <= cost[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-377/problems/minimum-cost-to-convert-string-ii/

题意

字符串哈希或或者字符串trie树

思路

1. 题目本身不难，但是需要优化，如何把
2. 复杂度分析:

• 时间复杂度：$O(n)$，其中 $n$ 表示树中节点的数目;
• 空间复杂度：$O(\log n)$，其中 $n$ 表示树中节点的数目;

代码

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu