【力扣周赛】第291场周赛

文章目录

• • • • 题目一
      • • 题目描述
      • 代码
      • 题目二
      • • 题目描述
      • 代码
      • 题目三
      • • 题目描述
      • 代码
      • 题目四
      • • 题目描述
      • 代码

先来汇报一下本周的周赛情况：前2题做出来了，后两题能看懂，不会做（具体说是不会一种很快的方法，只能用暴力，但暴力肯定会超时，就没有写）

题目一

题目描述

给你一个表示某个正整数的字符串

number

和一个字符

digit

。

从

number

中 恰好 移除 一个 等于

digit

的字符后，找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足

digit

在

number

中出现至少一次。

示例 1：

输入：number = "123", digit = "3"
输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。
           

示例 2：

输入：number = "1231", digit = "1"
输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。
           

示例 3：

输入：number = "551", digit = "5"
输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。
           

提示：

• 2 <= number.length <= 100

• number

  由数字

  '1'

  到

  '9'

  组成

• digit

  是

  '1'

  到

  '9'

  中的一个数字

• digit

  在

  number

  中出现至少一次

简单，直接模拟，用Python来看比较方便。

代码

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        res = "0"
        numLs = list(number)
        for i in range(len(numLs)):
            if numLs[i] == digit:
                curNum = "".join(numLs[:i])+"".join(numLs[i+1:])
                if eval(res)<eval(curNum):
                    res = curNum
        return res

           

题目二

题目描述

给你一个整数数组

cards

，其中

cards[i]

表示第

i

张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。

返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回

-1

。

示例 1：

输入：cards = [3,4,2,3,4,7]
输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。
           

示例 2：

输入：cards = [1,0,5,3]
输出：-1
解释：无法找出含一对匹配卡牌的一组连续卡牌。
           

提示：

• 1 <= cards.length <= 105

• 0 <= cards[i] <= 106

这个题目我一开始思考了一会，想着如何通过匹配两个相同的数字，后来我想到了哈希表内对数字索引的更新。具体的是，遇到没加入哈希表的，就以"值：索引"的形式加入，如果已经加入了，则先算出这两个之间的距离，然后更新索引。这样就相当于把所有的相邻的相同数的距离都遍历了一遍，从中取出最小值即可。

代码

class Solution {
    public int minimumCardPickup(int[] cards) {
        int res = cards.length;
        Map<Integer,Integer> map = new HashMap();
        boolean flag = false;
        for(int i=0;i<cards.length;i++){
            if (!map.containsKey(cards[i])){
                map.put(cards[i],i);
            }
            else{
                int curDis = i-map.get(cards[i]);
                res = res<curDis ? res : curDis;
                flag = true;
                map.put(cards[i],i);
            }
        }
        return flag ? res+1 : -1;
    }
}
           

题目三

题目描述

给你一个整数数组

nums

和两个整数

k

和

p

，找出并返回满足要求的不同的子数组数，要求子数组中最多

k

个可被

p

整除的元素。

如果满足下述条件之一，则认为数组

nums1

和

nums2

是 不同 数组：

• 两数组长度 不同 ，或者
• 存在 至少 一个下标

  i

  满足

  nums1[i] != nums2[i]

  。

子数组 定义为：数组中的连续元素组成的一个 非空 序列。

示例 1：

输入：nums = [2,3,3,2,2], k = 2, p = 2
输出：11
解释：
位于下标 0、3 和 4 的元素都可以被 p = 2 整除。
共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素：
[2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。
注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。
子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。
           

示例 2：

输入：nums = [1,2,3,4], k = 4, p = 1
输出：10
解释：
nums 中的所有元素都可以被 p = 1 整除。
此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。
因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。
           

提示：

• 1 <= nums.length <= 200

• 1 <= nums[i], p <= 200

• 1 <= k <= nums.length

看完大佬们的解题后，我明白这题其实并不难，一个思路是：由于这里的子数组的定义是由连续元素组成的，所以我们可以确定一个开头，然后不断向后索引，依次增加长度，直到不满足为止。每次增加长度都将这样的一个子数组加入答案集合中，而集合保证了其中每个数组元素的不重复性。

代码

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

题目四

题目描述

字符串的 引力 定义为：字符串中 不同 字符的数量。

• 例如，

  "abbca"

  的引力为

  3

  ，因为其中有

  3

  个不同字符

  'a'

  、

  'b'

  和

  'c'

  。

给你一个字符串

s

，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

示例 1：

输入：s = "abbca"
输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。
           

示例 2：

输入：s = "code"
输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。
           

提示：

• 1 <= s.length <= 105

• s

  由小写英文字母组成

这题看似和上面一题很相似，关于子字符串，还定义连续。但是，如果真的按照上面的做法去写，肯定会超时。因为二者的break条件不一样，题目三是能被整除的数超过了一定限制，即break，但此题确每一次遍历都要遍历到底，中途不会break。

去看了一下大佬的解答，果然大佬的思路都不一样。人家没有拘泥于如何去求什么不重复的字符之类的东西，人家直接在研究递推的规律——就是当一个新的字符添加到末尾时，会对前面的字符的引力和造成什么影响。这应该是受到汉诺塔问题的启发，不去从宏观上直接把握整个问题的求解流程，而是一步步地推导，用递归的思路去解决问题。

大佬发现了两个规律：

1. 当s[i]在s[0:i-1]中不存在时，此时s[i]加入到其中，s[0:i-1]，s[1:i-1] … s[i-1:i-1]都会加上1，总共加i，再加上其本身s[i]的引力值也是1，所以总共引力值加i+1,也就是i-(-1)。
2. 当s[i]在s[0:i-1]中存在时，假设最后一次出现是在s[j]处，那么s[0:j]，s[1:j]…s[j:j]都不会有引力值增加，但s[j+1:i-1]，s[j+2:i-1]…s[i-1:i-1]会有引力值增加，增加量为i-1-j，再加上s[i]本身，即i-j。

所以这个解法从头到尾根本没有去判断字符重复的问题，仅仅是做简单的加法和判断，就解出了题目。不愧是大佬啊。

代码

class Solution {
    public long appealSum(String s) {
        long res = 0,sumG = 0;
        int[] pos = new int[26];
        Arrays.fill(pos,-1);
        for(int i=0;i<s.length();i++){
            int idx = s.charAt(i)-'a';
            sumG += i - pos[idx];//sumG一直在自身上增加
            res += sumG;//res也一直在自身上增加
            pos[idx] = i;//更新索引下标
        }
        return res;
    }
}
           

当然，这个思路不经历一大堆题目的洗礼是无法想到的，即使现在我也没有完全明白sumG的含义和迭代的详细过程，但贵在坚持，多去参加周赛，多看看别人的代码，多思考，总会有提升的。