Leetcode 97场双周赛

Q1 6303. 分割数组中数字的数位 [Easy] 题解

Q2 6304. 从一个范围内选择最多整数 I [Medium] 题解

Q3 6331. 两个线段获得的最多奖品 [Medium] 题解

Q4 6305. 二进制矩阵中翻转最多一次使路径不连通 [Medium] 题解

Q1

6303. 分割数组中数字的数位 - 力扣（Leetcode）

给你一个正整数数组 nums ，请你返回一个数组 answer ，你需要将 nums 中每个整数进行数位分割后，按照 nums 中出现的 相同顺序 放入答案数组中。对一个整数进行数位分割，指的是将整数各个数位按原本出现的顺序排列成数组。

• 比方说，整数 10921 ，分割它的各个数位得到 [1,0,9,2,1] 。

示例 1：

输入：nums = [13,25,83,77]
输出：[1,3,2,5,8,3,7,7]
解释：
- 分割 13 得到 [1,3] 。
- 分割 25 得到 [2,5] 。
- 分割 83 得到 [8,3] 。
- 分割 77 得到 [7,7] 。
answer = [1,3,2,5,8,3,7,7] 。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。

示例 2：

输入：nums = [7,1,3,9]
输出：[7,1,3,9]
解释：nums 中每个整数的分割是它自己。
answer = [7,1,3,9] 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100000

思路

​ 简单模拟

代码

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        ans = []
        for i in nums:
            t = i
            tp = []
            while t > 0:
                tp.append(t%10)
                t //= 10
            for j in tp[::-1]:
                ans.append(j)
        return ans

复杂度分析

• 时间复杂度：O(nlog m), m = max(nums)
• 空间复杂度：O(1)

Q2

6304. 从一个范围内选择最多整数 I - 力扣（Leetcode）

给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：

被选择整数的范围是 [1, n] 。每个整数 至多 选择 一次 。被选择整数不能在数组 banned 中。 被选择整数的和不超过 maxSum 。请你返回按照上述规则 最多 可以选择的整数数目。

示例 1：

输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。

示例 2：

输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：按照上述规则无法选择任何整数。

示例 3：

输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。

提示：

1 <= banned.length <= 10000 1 <= banned[i], n <= 10000 1 <= maxSum <= 10^9

思路

​ 选的数的总和有限制，又要选的数最多，那肯定是从小到大选择。即遍历 [1, n] 遇到在banned里的数就跳过，直到遍历结束或者总和大于maxSum。

代码

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        hs = set(banned)
        ans = 0
        s = 0
        for i in range(1, n+1):
            if i in hs: continue
            if i+s > maxSum: break
            s += i
            ans += 1
        return ans

复杂度分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(m)

Q3

6331. 两个线段获得的最多奖品 - 力扣（Leetcode）

在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

• 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。

请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

示例 1：

输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。

示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。

提示：

• 1 <= prizePositions.length <= 10^5
• 1 <= prizePositions[i] <= 10^9
• 0 <= k <= 10^9
• prizePositions 有序非递减。

思路

用双指针处理第二条线段，同时，用一个数组 ms[i] 记录线段右端点不超过 p[i] 时最多可以覆盖多少个奖品。 第二条线段处理时，需要用二分找到最左边可以覆盖到的端点 l ，这样第二条线段可获得的奖品为 i − l + 1 。再加上 ms[l − 1]，就是第一条线段右端点不超过 p[l − 1] 时最大奖品数量。用这个更新 ans。 ans = max (ans, i − l + 1 + ms[l − 1]) 不要忘了跟新 ms ms[i] = max(i − l + 1, ms[i − 1])

代码

class Solution:
    def maximizeWin(self, p: List[int], k: int) -> int:
        n, ans = len(p), 0
        ms = [0]*(n+1)
        for i in range(1, n+1):
            l = 1
            r = i
            while l <= r:
                m = l+r >> 1
                if p[i-1]-p[m-1]<=k: r = m-1
                else: l = m+1
            ans = max(ans, i-l+1+ms[l-1])
            ms[i] = max(i-l+1, ms[i-1])
        return ans

复杂度分析

• 时间复杂度：O(nlog n)， 主要是二分的时间复杂度。
• 空间复杂度：O(n)

Tips

这题也可以用双指针，可以做到 O(n)时间复杂度。

Q4

6305. 二进制矩阵中翻转最多一次使路径不连通 - 力扣（Leetcode）

给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。

如果可以使矩阵不连通，请你返回 true ，否则返回 false 。

注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。

示例 1：

输入：grid = [[1,1,1],[1,0,0],[1,1,1]] 输出：true 解释：按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。

示例 2：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：false 解释：无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 10^5
• grid[0][0] == grid[m - 1][n - 1] == 1

思路

赛时想到了求割点，但发现不会写。

这题其实用不到割点，因为这个图的路径走法是很固定的，只有往右下方走。

所以我们只要求出是否有一个点，所有合法路径都要经过它（割点），那我们翻转成0就可以使得所有路径不通。

记 f(i, j) 表示从 (0, 0) 走到 (i, j) 的方案数。记 g(i, j) 表示从 (n − 1, m − 1) 倒着走到 (i, j) 的方案数。 由这两个值很容易算出从 (0, 0) 走到 (i, j) ，且中途必须经过 (i, j) 的方案数，即为 f(i, j) × g(i, j) 因此只要找到 i，j 满足 f(i, j) × g(i, j) = f(n − 1, m − 1) ，就说明想要从 (0, 0) 走到 (n − 1, m − 1) ，则必须经过 (i, j) ，即找到了答案。

代码

class Solution {
    public boolean isPossibleToCutPath(int[][] g) {
        int n = g.length, m = g[0].length;
        int M1 = (int)1e9+777777, M2 = (int)1e9+133333;
        int[][][] f = new int[n+2][m+2][2];
        int[][][] h = new int[n+2][m+2][2];
        f[0][1][0] = f[0][1][1] = 1;
        h[n+1][m][0] = h[n+1][m][1] = 1;
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                if (g[i-1][j-1] == 0) continue;
                f[i][j][0] = (f[i-1][j][0]+f[i][j-1][0])%M1;
                f[i][j][1] = (f[i-1][j][1]+f[i][j-1][1])%M2;
            }
        }
        for (int i = n;i >= 1;i--){
            for (int j = m;j >= 1;j--){
                if (g[i-1][j-1] == 0) continue;
                h[i][j][0] = (h[i+1][j][0]+h[i][j+1][0])%M1;
                h[i][j][1] = (h[i+1][j][1]+h[i][j+1][1])%M2;
            }
        }
        long x = f[n][m][0], y = f[n][m][1];
        if (x==0&&y==0) return true;
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                if (i+j==2 || i+j==m+n) continue;
                long t1 = f[i][j][0]*1L*h[i][j][0]%M1;
                long t2 = f[i][j][1]*1L*h[i][j][1]%M2;
                if (x==t1 && y==t2) return true;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(nm)
• 空间复杂度：O(nm)

Tips

计算方法数时可能溢出，所以要取模。考虑到哈希冲突，可以使用两个模数来降低冲突概率。一般算法题中两个哈希的冲突概率已经非常小了。

还有一种类似贪心的dfs算法，详见6305. 二进制矩阵中翻转最多一次使路径不连通 - 力扣（Leetcode）