且听疯吟

leetcode weekly contes 367

2023-10-17

leetcode weekly contes 367

周末基本上在医院，在医院带小朋友打针的环节中间竟然把比赛做完了，人到中年不容易。对于自己喜欢的事情一定要坚持写去，比如参加周赛，比如写题解，对于自己是一种思维的总结也是一种放松。人到中年只有越来越努力，不容退缩。

2903. 找出满足差值条件的下标 I

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

  • abs(i - j) >= indexDifference 且
  • abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。 
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。 
因此，[0,0] 是一个符合题目要求的答案。 
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

提示：

  • 1 <= n == nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= indexDifference <= 100
  • 0 <= valueDifference <= 50

地址

https://leetcode.cn/contest/weekly-contest-367/problems/find-indices-with-index-and-value-difference-i/

题意

枚举

思路

  1. 直接枚举所有可能的小标对即可，找到满足要求的小标对返回即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        for i, a in enumerate(nums):
            for j, b in enumerate(nums):
                if abs(i - j) >= indexDifference and abs(a - b) >= valueDifference:
                    return [i, j]
        return [-1, -1]

2904. 最短且字典序最小的美丽子字符串

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

  • 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

示例 1：

输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "100011001" 。
2. 子字符串 "100011001" 。
3. 子字符串 "100011001" 。
4. 子字符串 "100011001" 。
5. 子字符串 "100011001" 。
6. 子字符串 "100011001" 。
7. 子字符串 "100011001" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。

示例 2：

输入：s = "1011", k = 2
输出："11"
解释：示例中共有 3 个美丽子字符串：
1. 子字符串 "1011" 。
2. 子字符串 "1011" 。
3. 子字符串 "1011" 。
最短美丽子字符串的长度是 2 。
长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。

示例 3：

输入：s = "000", k = 1
输出：""
解释：示例中不存在美丽子字符串。

提示：

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

地址

https://leetcode.cn/contest/weekly-contest-367/problems/shortest-and-lexicographically-smallest-beautiful-string/

题意

枚举

思路

  1. 首先要找到连续出现 $k$ 个 $1$ 的字符串，此时我们统计找到连续出现 $1$ 的情况，找到以当前位置为结尾且有 $k$ 个 $1$ 的最短子串，同时选择字典序最小的子串返回即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度。

代码

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        n, curr = len(s), 0
        cnt = [-1] * (n + 1)
        res = ""
        for i, c in enumerate(s):
            if c == '1':
                curr += 1
            if curr >= k:
                now = i - cnt[curr - k]
                t = s[cnt[curr - k] + 1 : cnt[curr - k] + now + 1]
                if res == "":
                    res = t
                else:
                    if now < len(res):
                        res = t
                    elif now == len(res):
                        if t < res:
                            res = t
            cnt[curr] = i
        return res

2905. 找出满足差值条件的下标 II

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

  • abs(i - j) >= indexDifference 且
  • abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。 
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。 
因此，[0,0] 是一个符合题目要求的答案。 
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

提示：

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= indexDifference <= 105
  • 0 <= valueDifference <= 109

地址

https://leetcode.cn/contest/weekly-contest-367/problems/find-indices-with-index-and-value-difference-ii/

题意

滑动窗口

思路

  1. 题目比较有意思的，假设遍历当前位置为 $i$, 则所有满足与 $i$ 的差值大于等于 $indexDifference $ 的索引区间为 $[0,i-indexDifference]$, 因此我们只需要在区间 $[0,i-indexDifference]$ 找到元素 $nums[j]$ ，使得其与当前元素 $nums[i]$ 差的绝对值大于等于 $valueDifference $ 即可，此时我们可以找到差的绝对值的最大值，只需要检测最大值是否满足大于等于 $valueDifference$ 即可，此时 $nums[i]$ 一定与区间 $[0,i-indexDifference]$ 中的最小的元素或者最大的元素的差的绝对值最大，再此不再证明，我们直接求出即可。
  2. 采用滑动窗口即可，每次保存当前的最大值与最小值的索引 $maxIdx, minIdx$，每次比较当前值与最大值和最小值的差的绝对值。
  3. 复杂度分析：
  • 时间复杂度：$O(n)$，其中$n$ 表示数组的长度；
  • 空间复杂度：$O(1)$；

代码

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        maxIdx, minIdx = -1, -1
        j = 0
        for i, num in enumerate(nums):
            while i - j >= indexDifference:
                if maxIdx < 0 or nums[maxIdx] < nums[j]:
                    maxIdx = j
                if minIdx < 0 or nums[minIdx] > nums[j]:
                    minIdx = j
                j += 1
            if maxIdx >= 0 and abs(num - nums[maxIdx]) >= valueDifference:
                return [maxIdx, i]
            if minIdx >= 0 and abs(num - nums[minIdx]) >= valueDifference:
                return [minIdx, i]
        return [-1, -1]

2906. 构造乘积矩阵

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

  • 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

提示：

  • 1 <= n == grid.length <= 105
  • 1 <= m == grid[i].length <= 105
  • 2 <= n * m <= 105
  • 1 <= grid[i][j] <= 109

地址

https://leetcode.cn/contest/weekly-contest-366/problems/apply-operations-on-array-to-maximize-sum-of-squares/

题意

前后缀

思路

  1. 题目出的比较有意思，但是不是很难的题目。拿到题目就想用乘法逆元来做，结果发现由于 $12345$ 不是质数，无法使用乘法逆元，只能另想其他方法。仔细分析了一下，可以将数组展开，利用前后缀即可，$prefix[i]$ 表示前 $i$ 个元素相乘的结果， $suffix[i]$ 表示从 $i$ 开始后缀的乘积，此时 $p[x] = prefix[x-1] * suffix[x + 1] \bmod 12345$, 题目就非常简单了。

  2. 复杂度分析：

  • 时间复杂度：$O(mn)$，其中 $m,n$ 表示矩阵的行数与列数；
  • 空间复杂度：$O(1)$；

代码

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        mod = 12345
        m, n = len(grid), len(grid[0])
        suffix = [[0] * n for _ in range(m)]
        cur = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                suffix[i][j] = cur
                cur = cur * grid[i][j] % mod
        pre = 1
        for i in range(m):
            for j in range(n):
                suffix[i][j] = suffix[i][j] * pre % mod
                pre = pre * grid[i][j] % mod
        return suffix

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

Tags: 题解 力扣周赛赛
← leetcode weekly contes 365 leetcode weekly contes 366 →

扫描二维码，分享此文章