LeetCode笔记：Weekly Contest 348

LeetCode笔记：Weekly Contest 348
- 1. 题目一
  - 1. 解题思路
  - 2. 代码实现
- 2. 题目二
  - 1. 解题思路
  - 2. 代码实现
- 3. 题目三
  - 1. 解题思路
  - 2. 代码实现
- 4. 题目四
  - 1. 解题思路
  - 2. 代码实现

比赛链接：https://leetcode.com/contest/weekly-contest-348/

1. 题目一

给出题目一的试题链接如下：

2716. Minimize String Length

1. 解题思路

这一题其实最终的结果就是其原字符串当中unique的字符的个数，我们将其返回即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minimizedStringLength(self, s: str) -> int:return len(set(s))

提交代码评测得到：耗时66ms，占用内存16.3MB。

2. 题目二

给出题目二的试题链接如下：

2717. Semi-Ordered Permutation

1. 解题思路

这一题其实就是考虑将1移动到开头的操作数目以及将n移动到末尾的操作数目，将两者相加即可得到我们最终的答案。

不过需要注意的是，如果两者的初始位置有交叉，那么我们需要将最终答案减一，因为操作完了1之后，n的位置事实上是后退了一位的。

2. 代码实现

给出python代码实现如下：

class Solution:def semiOrderedPermutation(self, nums: List[int]) -> int:n = len(nums)i = nums.index(1)j = nums.index(n)return i + n-1-j if i < j else i + n-1-j - 1

提交代码评测得到：耗时86ms，占用内存16.3MB。

3. 题目三

给出题目三的试题链接如下：

2718. Sum of Matrix After Queries

1. 解题思路

这一题的思路可以采用倒推的思路，显然，考虑最后一次操作，有：

如果这次操作是针对行的，那么只有考虑当前未被改变的列的数目乘以目标的val就是最终会对结果产生贡献的值，在此操作之后，后续会被改变的行总数减一；
同理，如果这次操作是针对列的，那么只有考虑当前未被改变的行的数目乘以目标的val就是最终会对结果产生贡献的值，在此操作之后，后续会被改变的列总数减一；

需要注意的是，如果某一行或者某一列之前已经被操作过了，那么跳过此次操作即可，因为他不会对最终结果产生影响。

综上，我们只需要反向倒推即可得到我们最终的答案。

2. 代码实现

给出python代码实现如下：

class Solution:def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:cols, rows = n, nseen_cols, seen_rows = set(), set()res = 0for _type, idx, val in queries[::-1]:if _type == 0:if idx in seen_rows:continueseen_rows.add(idx)res += val * colsrows -= 1else:if idx in seen_cols:continueseen_cols.add(idx)res += val * rowscols -= 1return res

提交代码评测得到：耗时1979ms，占用内存39.4MB。

4. 题目四

给出题目四的试题链接如下：

2719. Count of Integers

1. 解题思路

这一题思路上其实还是挺简单的，我们首先定义一个函数gn(num, s)，表示所有不大于n，然后各个位上的数字之和不大于s的数的个数，那么，对应的问题的答案就可以直接写作：

res = (gn(num2, max_sum) - gn(num2, min_sum-1)) - (gn(num1-1, max_sum) - gn(num1-1, min_sum-1))

由此，我们只需要给出上述gn(num, s)的实现即可，其中不妨令num的位数为n。

这个其实也不复杂，我们可以将其拆分为两个部分：

如果第一位与num相同，那么对应的数字个数就是gn(num[1:], s-int(num[0]))
如果第一位小于num的第一个数d，那么对应的结果就是将第一位i遍历0到d-1，然后将所有位数不大于n，然后各个位上的的数字之和不大于s-i的结果进行一下累加即可。

因此，我们只需要再给出一个函数fn(n, s)，表示所有位数不多于n，然后各个位上的数字之和不大于s的数字的个数。

这样，我们就能够给出gn(num, s)的构造。

剩下的，我们只需要在给出fn(n, s)的构造即可，而这个事实上就是一个简单的动态规划问题，这里就不需要额外进行展开了。

2. 代码实现

我们给出最终的python代码实现如下：

class Solution:MOD = 10**9 + 7@lru_cache(None)def fn(self, n, s):if s < 0:return 0elif s == 0 or n == 0:return 1res = sum(self.fn(n-1, s-i) for i in range(10))return res % self.MOD@lru_cache(None)def gn(self, num, s):n = len(num)if s < 0:return 0elif s == 0:return 1elif n == 1:res = min(10, min(int(num), s)+1)return resd = int(num[0])res = self.gn(num[1:], s-d)for j in range(d):res += self.fn(n-1, s-j)return res % self.MODdef count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:num1 = str(int(num1) - 1)s1 = self.gn(num2, max_sum) - self.gn(num2, min_sum-1)s2 = self.gn(num1, max_sum) - self.gn(num1, min_sum-1)return (s1 - s2 + self.MOD) % self.MOD