• LeetCode笔记：Weekly Contest 291
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现
    • 3. 算法优化

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

1. 题目一

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

• 2259. Remove Digit From Number to Maximize Result

1. 解题思路

这一题要想获得最大的数，那么只需要遵循如下规则即可：

1. 如果这个数邻接的下一个数比这个数更大，那么就可以直接删除这个数即可；
2. 如果一直找不到这个数，那么就删除最后一次出现的数即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        last = -1
        n = len(number)
        for i in range(n-1):
            if number[i] == digit:
                if number[i] < number[i+1]:
                    return number[:i] + number[i+1:]
                last = i
        if number[-1] == digit:
            last = n-1
        return number[:last] + number[last+1:] 

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

2. 题目二

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

• 2260. Minimum Consecutive Cards to Pick Up

1. 解题思路

这题我的思路就是先记录下每一个卡出现的位置，然后只要看连续两个位置出现的间隔，找出其中的最小值然后进行返回即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        cnt = defaultdict(list)
        res = math.inf
        for i, x in enumerate(cards):
            cnt[x].append(i)
            if len(cnt[x]) >= 2:
                res = min(res, cnt[x][-1] - cnt[x][-2]+1)
        return res if res != math.inf else -1

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

3. 题目三

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

• 2261. K Divisible Elements Subarrays

1. 解题思路

这一题坦率地说没啥很好的思路，就是直接暴力地二重循环进行了一下求解。

万幸的是，还在题目允许的时间复杂度范围内。

2. 代码实现

给出python代码实现如下：

class Solution:
    def countDistinct(self, nums: List[int], k: int, p: int) -> int:
        n = len(nums)
        r = [x % p for x in nums]
        res = set()
        for i in range(n):
            cnt = 0
            for j in range(i, n):
                if r[j] == 0:
                    cnt += 1
                if cnt <= k:
                    res.add(tuple(nums[i:j+1]))
                else:
                    break
        return len(res)

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

4. 题目四

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

• 2262. Total Appeal of A String

1. 解题思路

这一题坦率地说我没有想到很好的解法，不过看了其他大佬们的解答之后大受震撼，真的是很精妙的一道题。

我们这里给出榜一大佬的解法。

本质上来说，这里还是一个二重循环，找到每一个字符作为最后一个字符时所有的子串能够贡献的计数。

不过如果直接使用一个二重循环那么必然会直接把时间复杂度搞爆炸，因此这里大佬做了一个非常牛逼的优化，就是直接同个26个字符各自贡献的计数，这样，我们的时间复杂度就只是$O(26N)$。

由此，问题就变成了如何直接用$O(1)$的复杂度求取每一个字符贡献的计数，这个事实上也简单，事实上就是找到这个字符在前序当中最后一次出现的位置idx，那么包含这个字符的子串总数就是idx+1。

由此，问题得解。

2. 代码实现

给出python代码实现如下：

class Solution:
    def appealSum(self, s: str) -> int:
        cnt = [0 for _ in range(26)]
        res = 0
        for idx, ch in enumerate(s):
            cnt[ord(ch) - ord('a')] = idx+1
            for i in range(26):
                res += cnt[i]
        return res

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

3. 算法优化

后续看了一下别人提交的code，发现还有一种更加优雅的解答，可以将算法复杂度进一步减到$O(N)$。

本质上来说，其思路还是和上述一样，就是求每一个位置上的元素作为最后一个元素的情况下所有的子串能够贡献的计数。

不过，这里可以直接使用迭代的思路，即:

$$f(n+1)=f(n)+index-inde{x}_{last}$$

其中，$f(n)$表示最后一个字符为第i个字符的子串能够提供的总的计数值，其值就是$f(n-1)$加上之前不包含这个字符的子串的字符串的数目。

我们翻译成代码语言就是：

class Solution:
    def appealSum(self, s: str) -> int:
        last_index = [-1 for _ in range(26)]
        res = 0
        cnt = 0
        for idx, ch in enumerate(s):
            cnt = cnt + idx - last_index[ord(ch) - ord('a')]
            res += cnt
            last_index[ord(ch) - ord('a')] = idx
        return res

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