leetcode biweekly contest 524

leetcode contest 524

这次周赛题目总体还是偏难的，质量非常不错的题目，需要仔细思考

Q1. Minimum Deletions to Make Array Sharp

You are given an integer array nums.

You may delete any number of elements from nums. The remaining elements keep their original order.

The resulting array a is sharp if the bitwise XOR of every pair of adjacent elements is non-zero. That is, a[i] XOR a[i + 1] != 0 for every index i such that 0 <= i < a.length - 1. An array with at most one element is sharp.

Return the minimum number of deletions needed to make nums sharp.

Bitwise XOR compares the corresponding bits of two integers. A bit in the result is 1 if the corresponding bits differ, and 0 otherwise.

Example 1:

Input: nums = [1,1,2,2,2,3]

Output: 3

Explanation:

  • The pairs at indices (0, 1), (2, 3), and (3, 4) each have an XOR of 0.
  • Deleting one 1 and two 2s leaves [1, 2, 3], where 1 XOR 2 == 3 and 2 XOR 3 == 1 are both non-zero. Therefore, the answer is 3.

Example 2:

Input: nums = [4,4,9,4]

Output: 1

Explanation:

  • The pair at indices (0, 1) has an XOR of 0.
  • Deleting either of these two 4s leaves [4, 9, 4], where 4 XOR 9 == 13 and 9 XOR 4 == 13 are both non-zero.

Constraints:

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

地址

https://leetcode.com/contest/weekly-contest-524/problems/minimum-deletions-to-make-array-sharp/description/

题意

遍历，模拟

思路

  1. 题目本质是去除数组中相相同得相邻元素，使得数组中不存在相同得相邻元素。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

1
2
3
class Solution:
    def minDeletions(self, nums: list[int]) -> int:
        return sum(1 if nums[i] == nums[i - 1] else 0 for i in range(1, len(nums)))

Q2. Last Visited Cell in a Directional Grid

You are given an m x n matrix grid where each cell contains one of the following characters:

  • 'L': move one cell left.
  • 'R': move one cell right.
  • 'U': move one cell up.
  • 'D': move one cell down.

You start at cell (0, 0), which is considered visited. At each step, move to the cell indicated by the character in your current cell.

The process ends if the indicated move would either leave the grid or enter a cell that has already been visited. In either case, the move is not made.

Return an integer array [r, c] representing the row and column indices of the last visited cell. The indices are 0-based.

Example 1:

Input: grid = [[“R”,”D”],[“U”,”L”]]

Output: [1,0]

Explanation:

  • Start at cell (0, 0), which contains 'R', so move right to (0, 1).
  • At cell (0, 1), the character is 'D', so move down to (1, 1).
  • At cell (1, 1), the character is 'L', so move left to (1, 0).
  • At cell (1, 0), the character is 'U', which indicates moving to (0, 0). However, (0, 0) has already been visited, so this move is not made.
  • Therefore, the process ends at the last visited cell (1, 0), so the answer is [1, 0].

Example 2:

Input: grid = [[“R”,”R”,”R”]]

Output: [0,2]

Explanation:

  • Start at cell (0, 0), which contains 'R', so move right to (0, 1).
  • At cell (0, 1), the character is 'R', so move right to (0, 2).
  • At cell (0, 2), the character is 'R', which indicates moving to (0, 3). However, (0, 3) is outside the grid, so this move is not made.
  • Therefore, the process ends at the last visited cell (0, 2), so the answer is [0, 2].

Constraints:

  • 1 <= m == grid.length <= 105
  • 1 <= n == grid[i].length <= 105
  • m * n <= 105
  • grid[i][j] is one of 'L', 'R', 'U', or 'D'.

地址

https://leetcode.com/contest/weekly-contest-524/problems/last-visited-cell-in-a-directional-grid/description/

题意

模拟

思路

  1. 我们直接模拟即可，从起点 $(0, 0)$ 开始模拟，遇到上下左右四个方向分别模拟移动即可，并记录最终停留的位置返回即可。
  2. 复杂度分析：
  • 时间复杂度：$O(mn)$，其中 $m,n$ 矩阵的行数与列数。
  • 空间复杂度：$O(mn)$；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
        m, n = len(grid), len(grid[0])
        visit = [[False] * n for _ in range(m)]

        r, c = 0, 0
        cx, cy = 0, 0
        while r >= 0 and c >= 0 and r < m and c < n and not visit[r][c]:
            visit[r][c] = True
            cx, cy = r, c
            if grid[r][c] == 'U':
                r -= 1
            elif grid[r][c] == 'D':
                r += 1
            elif grid[r][c] == 'L':
                c -= 1
            elif grid[r][c] == 'R':
                c += 1

        return [cx, cy]

Q3. Find Root of a Colored Tree

You are given an undirected tree of n nodes labeled from 0 to n - 1, represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an undirected edge between nodes ui and vi.

You are also given a string colors of length n, where colors[i] is one of 'R', 'B', or 'W', and denotes the color of node i.

A node chosen as root must satisfy both of the following conditions once the tree is oriented away from it:

  1. Binary-tree property: Every node has at most two children.
  2. Layered color pattern: All nodes at the same depth have the same color. Starting at depth 0, these colors follow one of the three repeating sequences:
    • R → B → W → R → B → W → ...
    • B → W → R → B → W → R → ...
    • W → R → B → W → R → B → ...

Return the index of any root that satisfies both conditions, or -1 if no such root exists.

A tree is a connected undirected graph with no cycles.

The depth of a node is the number of edges on the path from the root to that node. The root has depth 0. A child of a node is an adjacent node whose depth is one greater.

The degree of a node is the number of edges incident to it.

Example 1:

Input: edges = [[3,1],[3,2],[1,4],[2,0]], colors = “BRRWB”

Output: 3

Explanation:

img

Rooting at node 3 gives each node at most two children and every edge advances to the next color in the cycle (W → R → B), so return 3.

Example 2:

Input: edges = [[0,1],[1,2],[2,3]], colors = “RBRB”

Output: -1

Explanation:

img

No root satisfies the required color step on every edge, so return -1.

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ui, vi]
  • 0 <= ui, vi < n
  • colors.length == n
  • colors[i] is one of 'R', 'B', 'W'.
  • The input graph is a tree and every node has degree at most three.

地址

https://leetcode.com/contest/weekly-contest-524/problems/find-root-of-a-colored-tree/description/

题意

1
图

思路

  1. 我们主要观察到一个主要问题，我们看到所有的颜色一直按照 “R->B->W->R->B->W”, 此时则表示图中任意一条边则存在方向，此时我们根据每条边对应的节点的颜色，即可统计每个节点的入度与出度，如果为根节点的节点，则其入度为 $0$，且出度不超过 $2$，此时我们直接找到根节点即可，如果不存在则返回 $-1$，且如果一条边上的两个颜色如果相同的话，则认为不合法，直接返回 $-1$。
  2. 复杂度分析：
  • 时间复杂度：$𝑂(n)$，其中 $n$ 表示给定节点的数目；
  • 空间复杂度：$𝑂(n)$，其中 $n$ 表示给定节点的数目；

代码

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
class Solution:
    def findColoredRoot(self, edges: list[list[int]], colors: str) -> int:
        n = len(colors)
        next = {'R':'B', 'B':'W', 'W':'R'}

        indeg = [0] * n
        deg = [0] * n
        for x, y in edges:
            cx, cy = colors[x], colors[y]
            deg[x] += 1
            deg[y] += 1
            if cx == cy:
                return -1
            if next[cx] == cy:
                indeg[y] += 1
            else:
                indeg[x] += 1

        root, cnt = -1, 0
        for i in range(n):
            if indeg[i] == 0:
                root = i
                cnt += 1

        if cnt != 1 or deg[root] == 3 or deg[root] == 0:
            return -1

        return root

Q4. Minimum Interval Selection to Cover Target Intervals

You are given two 2D integer arrays, availableIntervals and targetIntervals, each representing a list of closed intervals.

Select a subset of intervals from availableIntervals so that every real point contained in any interval in targetIntervals belongs to at least one selected interval.

Points outside the target intervals do not need to be covered. Selected intervals may overlap or extend beyond the target intervals.

Return the minimum number of intervals you need to select. If it is impossible to cover all the target intervals, return -1.

Example 1:

Input: availableIntervals = [[1,4],[1,7],[3,9],[5,10],[10,15]], targetIntervals = [[1,3],[2,5],[7,8],[10,13],[11,15],[12,13]]

Output: 3

Explanation:

The target intervals cover the ranges [1, 5], [7, 8], and [10, 15]. By selecting [1, 4], [3, 9], and [10, 15] from availableIntervals, all target intervals can be fully covered with three intervals.

Example 2:

Input: availableIntervals = [[4,6],[1,4],[2,5]], targetIntervals = [[3,4],[2,5],[6,7]]

Output: -1

Explanation:

It is impossible to select intervals from availableIntervals to cover all the intervals in targetIntervals.

Example 3:

Input: availableIntervals = [[1,2],[3,4]], targetIntervals = [[1,4]]

Output: -1

Explanation:

Selecting both available intervals leaves every real point strictly between 2 and 3 uncovered. For example, 2.5 belongs to the target interval but to neither available interval.

Constraints:

  • 1 <= availableIntervals.length, targetIntervals.length <= 5 * 104
  • availableIntervals[i].length == targetIntervals[j].length == 2
  • 1 <= availableIntervals[i][0] <= availableIntervals[i][1] <= 105
  • 1 <= targetIntervals[j][0] <= targetIntervals[j][1] <= 105

地址

https://leetcode.com/contest/weekly-contest-524/problems/minimum-interval-selection-to-cover-target-intervals/description/

题意

优先队列

思路

  1. 为了计算方便，首先我们需要对 targetIntervals 进行合并，存在重叠的空间则进行合并，并将 availableIntervals 按照区间的左端点大小进行排序。
  2. 我们设当前已经覆盖的区间的右端点为 $covered$，此时我们从左到右遍历 targetIntervals的每个区间 $[L,R]$:
    • 此时当 $covered$ 已经大于等于右端点 $R$ 时，则我们可以直接跳过该区间，遍历下个区间；
    • 此时当 $covered$ 小于 $R$ 时，此时我们需要尝试添加区间，由于此时区间一定需要覆盖 $[\max(covered, L),R]$，我们尝试将所有左端点小于等于 $\max(L, covered)$ 的区间加入到待选序列中，此时如果待选的区间中如果存在右端点最大覆盖的区间 $[l,r]$，如果 $r < \max(covered, L)$ 或者仍然小于 $covered$ ，则表示当前不存在合法的区间可以完成区间 $[L,R]$ 的覆盖，直接返回 $-1$ 即可，否则选择覆盖最右的区间，并更新$covered = r$，接着贪心搜索下一个区间，直接完全把 $R$ 覆盖完成，则继续检测下一个区间。
  3. 复杂度分析：
  • 时间复杂度：$𝑂(n \log n + (m + n) \cdot \log m)$，其中 $m,n$ 表示给定的数组的长度.
  • 空间复杂度：$𝑂(m + n)$，其中 $m,n$ 表示给定的数组的长度.

代码

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 minSelection(self, availableIntervals: List[List[int]], targetIntervals: List[List[int]]) -> int:
        n = len(availableIntervals)
        # 合并目标区间
        targetIntervals.sort()
        merged = []
        for t in targetIntervals:
            if not merged or t[0] > merged[-1][1]:
                merged.append([t[0], t[1]])
            else:
                merged[-1][1] = max(merged[-1][1], t[1])

        availableIntervals.sort()
        # Python 的 heapq 是小根堆，取相反数模拟大根堆
        pq = []
        ans = 0
        i = 0
        covered = -1

        # 滑动窗口
        for L, R in merged:
            if covered >= R:
                continue

            while covered < R:
                # 当前区间的最左需要覆盖点
                x = max(L, covered)

                # 优先选择区间右端点最大的区间
                while i < n and availableIntervals[i][0] <= x:
                    heapq.heappush(pq, -availableIntervals[i][1])
                    i += 1

                if not pq:
                    return -1

                last = -heapq.heappop(pq)
                if last < x or last <= covered:
                    return -1

                covered = last
                ans += 1

        return ans

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

力扣周赛
#题解 #力扣周赛赛
leetcode biweekly contest 524
http://example.com/2026/10/21/力扣周赛题解/238/
Author
Mike Meng
Posted on
October 21, 2026
Licensed under