leetcode weekly contest 413

t3,t4难度确实越来越高了，感觉有些难度的题目了。

3274. 检查棋盘方格颜色是否相同

给你两个字符串 coordinate1 和 coordinate2，代表 8 x 8 国际象棋棋盘上的两个方格的坐标。

以下是棋盘的参考图。

如果这两个方格颜色相同，返回 true，否则返回 false。

坐标总是表示有效的棋盘方格。坐标的格式总是先字母（表示列），再数字（表示行）。

示例 1：

输入： coordinate1 = “a1”, coordinate2 = “c3”

输出： true

解释：

两个方格均为黑色。

示例 2：

输入： coordinate1 = “a1”, coordinate2 = “h3”

输出： false

解释：

方格 "a1" 是黑色，而 "h3" 是白色。

提示：

• coordinate1.length == coordinate2.length == 2
• 'a' <= coordinate1[0], coordinate2[0] <= 'h'
• '1' <= coordinate1[1], coordinate2[1] <= '8'

地址

https://leetcode.cn/contest/weekly-contest-413/problems/check-if-two-chessboard-squares-have-the-same-color/

题意

模拟

思路

1. 如果单元格的行数与列数相加的奇偶性相同，则单元格的颜色相同，否则则不同；
2. 复杂度分析：

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def checkTwoChessboards(self, coordinate1: str, coordinate2: str) -> bool:
        x1 = ord(coordinate1[0]) - ord('a')
        y1 = ord(coordinate1[1]) - ord('a')
        x2 = ord(coordinate2[0]) - ord('a')
        y2 = ord(coordinate2[1]) - ord('a')
        return (x1 + y1) % 2 == (x2 + y2) % 2

3275. 第 K 近障碍物查询

有一个无限大的二维平面。

给你一个正整数 k ，同时给你一个二维数组 queries ，包含一系列查询：

• queries[i] = [x, y] ：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询 不会 在这个坐标处建立任何障碍物。

每次查询后，你需要找到离原点第 k 近 障碍物到原点的 距离 。

请你返回一个整数数组 results ，其中 results[i] 表示建立第 i 个障碍物以后，离原地第 k 近障碍物距离原点的距离。如果少于 k 个障碍物，results[i] == -1 。

注意，一开始 没有 任何障碍物。

坐标在 (x, y) 处的点距离原点的距离定义为 |x| + |y| 。

示例 1：

输入：queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2

输出：[-1,7,5,3]

解释：

最初，不存在障碍物。

• queries[0] 之后，少于 2 个障碍物。
• queries[1] 之后， 两个障碍物距离原点的距离分别为 3 和 7 。
• queries[2] 之后，障碍物距离原点的距离分别为 3 ，5 和 7 。
• queries[3] 之后，障碍物距离原点的距离分别为 3，3，5 和 7 。

示例 2：

输入：queries = [[5,5],[4,4],[3,3]], k = 1

输出：[10,8,6]

解释：

• queries[0] 之后，只有一个障碍物，距离原点距离为 10 。
• queries[1] 之后，障碍物距离原点距离分别为 8 和 10 。
• queries[2] 之后，障碍物距离原点的距离分别为 6， 8 和10 。

提示：

• 1 <= queries.length <= 2 * 105
• 所有 queries[i] 互不相同。
• -109 <= queries[i][0], queries[i][1] <= 109
• 1 <= k <= 105

地址

https://leetcode.cn/contest/weekly-contest-413/problems/k-th-nearest-obstacle-queries/

题意

优先队列，topk问题

思路

1. 题目为经典的 TOPK 问题，我们按照题目要求模拟即可，每次选择第 $k$ 近的坐标即可。

2. 复杂度分析：

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

代码

class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        pq = []
        ans = []
        for x, y in queries:
            dis = abs(x) + abs(y)
            heapq.heappush(pq, -dis)
            if len(pq) > k:
                heapq.heappop(pq)
            if len(pq) < k:
                ans.append(-1)
            else:
                ans.append(-pq[0])
        
        return ans

3276. 选择矩阵中单元格的最大得分

给你一个由正整数构成的二维矩阵 grid。

你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：

• 所选单元格中的任意两个单元格都不会处于矩阵的 同一行。
• 所选单元格的值 互不相同。

你的得分为所选单元格值的总和。

返回你能获得的 最大 得分。

示例 1：

输入： grid = [[1,2,3],[4,3,2],[1,1,1]]

输出： 8

解释：

选择上图中用彩色标记的单元格，对应的值分别为 1、3 和 4 。

示例 2：

输入： grid = [[8,7,6],[8,3,2]]

输出： 15

解释：

选择上图中用彩色标记的单元格，对应的值分别为 7 和 8 。

提示：

• 1 <= grid.length, grid[i].length <= 10
• 1 <= grid[i][j] <= 100

地址

https://leetcode.cn/contest/weekly-contest-413/problems/select-cells-in-grid-with-maximum-score/

题意

优先队列 + 数学

思路

2. 复杂度分析：

• 时间复杂度：$𝑂(𝑛log⁡ 𝑛+ n \log U)$，其中 𝑛 表示给定数组的长度. 𝑈 表示数字中的最大值 。
• 空间复杂度：$𝑂(𝑛)$；

代码

3277. 查询子数组最大异或值

给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每一个查询，你需要找出 nums[li..ri] 中任意 子数组 的 最大异或值。

数组的异或值 需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是 异或值：

• 对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。
• 移除数组的最后一个元素。

返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。

示例 1：

输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

输出： [12,60,60]

解释：

在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。

在第二个查询中，nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

在第三个查询中，nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

示例 2：

输入： nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

输出： [7,14,11,14,5]

解释：

提示：

• 1 <= n == nums.length <= 2000
• 0 <= nums[i] <= 231 - 1
• 1 <= q == queries.length <= 105
• queries[i].length == 2
• queries[i] = [li, ri]
• 0 <= li <= ri <= n - 1

地址

https://leetcode.cn/contest/weekly-contest-413/problems/maximum-xor-score-subarray-queries/

题意

排序哈希表

思路

2. 复杂度分析：

• 时间复杂度：$𝑂(𝑛log⁡ 𝑛+ n \log^4 U)$，其中 𝑛 表示给定数组的长度. 𝑈 表示数字中的最大值 。
• 空间复杂度：$𝑂(𝑛)$；

代码

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

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

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

• 关注我的微信公众号: 哪些奋斗者