leetcode weekly-contest-291

发布于 2022-05-01  720 次阅读


leetcode第291周赛解析

6047. 移除指定数字得到的最大结果

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

number恰好 移除 一个 等于 digit 的字符后,找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digitnumber 中出现至少一次。

  • 2 <= number.length <= 100
  • number 由数字 '1''9' 组成
  • digit'1''9' 中的一个数字
  • digitnumber 中出现至少一次
输入:number = "123", digit = "3"
输出:"12"
解释:"123" 中只有一个 '3' ,在移除 '3' 之后,结果为 "12" 。

这个题呢,用C++有一点点麻烦,所以呢。上py,发现digit就切片,换整数,比较大小,记录最小的。

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        ans=-1
        for i in range(len(number)):
            if number[i] == digit:
                ans = max( int (number[0:i]+number[i+1:]) , ans)
        return str(ans)

6048.必须拿起的最小连续卡牌数

给你一个整数数组 cards ,其中 cards[i] 表示第 i 张卡牌的 。如果两张卡牌的值相同,则认为这一对卡牌 匹配

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

  • 1 <= cards.length <= 105
  • 0 <= cards[i] <= 106
输入:cards = [3,4,2,3,4,7]
输出:4
解释:拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意,拿起 [4,2,3,4] 也是最优方案。

这说白了不就是找相邻两个相同的数之间的距离吗,然后比较个最小值,哈希表去记录位置,然后下一次遇到比较大小。

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        map<int,vector<int>> mp;
        int n = cards.size();
        int ans = 0x3f3f3f3f;
        for(int i = 0; i < n ; i++){
            if(mp[cards[i]].size() == 0){
                mp[cards[i]].push_back(i);
            }else{
                ans = min(ans,i-mp[cards[i]].back()+1);
                mp[cards[i]].push_back(i);
            }

        }
        if(ans == 0x3f3f3f3f){
            ans = -1;
        }
        return ans;
    }
};

6049.含最多K个可整除元素的子数组

给你一个整数数组 nums 和两个整数 kp ,找出并返回满足要求的不同的子数组数,要求子数组中最多 k 个可被 p 整除的元素。

如果满足下述条件之一,则认为数组 nums1nums2不同 数组:

  • 两数组长度 不同 ,或者
  • 存在 至少 一个下标 i 满足 nums1[i] != nums2[i]

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

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length
输入: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 整除。

一开始读错题了,数组不能重复,所以出了岔子,怎么做呢,数据量这么小,set去重玩

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int ans = 0;
        set<vector<int>> m;
        for(int i =0 ;i < nums.size(); i++){
            int cnt=0;
            for(int j = i; j<nums.size() ; j++){
                if(nums[j]%p == 0){
                    cnt++;
                }
                if(cnt <= k){
                    vector<int> tmp(nums.begin()+i,nums.begin()+j+1);
                    m.insert(tmp);
                }
                if(cnt > k){
                    break;
                }
            }
        }
        return m.size();
    }
};

6050. 字符串的总引力

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

  • 例如,"abbca" 的引力为 3 ,因为其中有 3 个不同字符 'a''b''c'

给你一个字符串 s ,返回 其所有子字符串的总引力

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

  • 1 <= s.length <= 105
  • s 由小写英文字母组成
输入: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 。

是哪儿的题我不说,什么子串分值和啊,不知道啊

class Solution {
public:
    int l[26];
    long long appealSum(string s) {
        int len = s.size();
        memset(l, -1, sizeof l);
        long long ans = 0;
        for(int i = 0; i < len; ++i){
            ans += (long long)(i - l[s[i] - 'a']) * (len - i);
            l[s[i] - 'a'] = i;
        }
        return ans;
    }
};

绝对不是恋爱脑!