LeetCode 第291场周赛

题目 1：移除指定数字得到的最大结果

思路

遍历一遍字符串，当遇到指定字符时，使用 erase 函数删除该字符，然后使用 compare()函数进行字符串比较，因为字符串的长度都是相等的，所以就相当于比较的是对应整型的大小。最后保存最大的即可。

题解

题解

class Solution {
public:
    string removeDigit(string number, char digit) {
        string res = "";
        for(int i = 0; i < number.length(); i ++){
            if(number[i] == digit){
                string str = number;  // 用于临时保存原来的string
                str.erase(i, 1); // 删除该字符，从i开始删除，删除1个字符
                if(res == ""){
                    res = str;
                }
                else if(res.compare(str) < 0){  // 比较字符串大小
                    res = str;
                }
            }
        }
        return res;
    }
};

时间复杂度：O(n ^ 2)，其中 n 为 number 的长度，我们只需要对 number 进行一次遍历，但是erase函数的时间复杂度为O(n)。
空间复杂度：O(n)，即为存储标结果需要使用的空间。

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：112 / 112

题目 2：必须拿起的最小连续卡牌数

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

思路

使用队列存储元素，若将要加入的元素已经存在于队列中，则开始出队，知道队列中不存在该元素，然后和res比较大小，若res大于队列元素个数加 2（因为此时当前元素还没加入，并且和其相同的元素也已经出队了，所以需要加 2）。然后将当前元素入队，继续往后遍历。

判断当前元素是否存在于队列中需要使用unordered_map<int, int>哈希表进行存储，表示 K 在哈希表中的个数为 V 。

题解

题解

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        queue<int> que; // 队列
        unordered_map<int, int> hsp;  // 哈希表
        que.push(cards[0]);
        hsp[cards[0]] ++;
        int i = 1;
        int res = -1;
        while(i < cards.size()){
            if(hsp[cards[i]] > 0) {
                while(hsp[cards[i]] > 0){
                    int top = que.front();
                    hsp[top] --;
                    que.pop();
                }
                if(res == -1 || res > (que.size() + 2)) res = que.size() + 2;
                hsp[cards[i]] ++;
                que.push(cards[i++]);
            }
            else{
                hsp[cards[i]] ++;
                que.push(cards[i++]);
            }
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 为 cards 的长度，我们只需要对 cards 进行一次遍历.
空间复杂度：O(2 \ n)*，即为队列和哈希表所需要的空间。

执行用时：372 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：116.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：78 / 78

题目 3：含最多 K 个可整除元素的子数组 ⭐

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

思路

对 nums 数组进行双重循环，第一重确定开始的位置（0 ~ nums.size() - 1） ，然后依次遍历数组，使用整型变量 count 记录出现能整除 p 的个数，当 count 大于 k 时，就跳出循环。否则将该元素转为字符串加入 str 中，注意需要在每个数后面加个 ,，是为了防止出现连续加入 1,9和直接加入19造成的歧义。最后将str 直接加入unordered_map 中进行去重。最后结果为unordered_map的个数。

去重也可以使用map<vector<int>, int>

unordered_map 和 map 的区别

map，set底层是红黑树，有序的，存储的数据类型可以自定义，空间时间复杂度比较高
unordered_map，unordered_set底层实现的时哈希表，无序存储，查询、插入时间空间复杂度比较低（相较于上面两个），但是缺点就是数据类型只能是基本数据类型，比如：int，char，float，string等。

class Solution {
public:
    
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_map<string, int> hsp;
        for(int i = 0; i < nums.size(); i ++){
            int count = 0;  // 记录能被p整除的个数
            string str = "";
            for(int j = i; j < nums.size(); j ++){
                if(nums[j] % p == 0) count ++;
                if(count > k) break;
                str += to_string(nums[j]); // 将整型转为string类型，并添加到str中
                str += ","; // 防止出现 1 9  和 19 一样的情况
                hsp[str] ++;  // 使用unordered_map进行去重
            }
            // cout << hsp.size() << endl;
        }
        return hsp.size();
    }
};

时间复杂度：O(n ^ 2)，其中 n 为 nums 的长度
空间复杂度：O((1 + n) \ n / 2)，即为 unordered_map* 做多需要使用的空间。

执行用时：492 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：204.6 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：129 / 129

class Solution {
public:
    
    int countDistinct(vector<int>& nums, int k, int p) {
        map<vector<int>, int> res;
        for(int i = 0; i < nums.size(); i ++){
            int count = 0;  // 记录能被p整除的个数
            for(int j = i; j < nums.size(); j ++){
                if(nums[j] % p == 0) count ++;
                if(count > k) break;
                res[vector<int>(nums.begin() + i, nums.begin() + j + 1)] = 1; // 添加入map
            }
            // cout << hsp.size() << endl;
        }
        return res.size();
    }
};

时间复杂度：O(n ^ 2)，其中 n 为 nums 的长度
空间复杂度：O((1 + n) \ n / 2)，即为 map* 做多需要使用的空间。

执行用时：1220 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：261 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：129 / 129

题目 4：字符串的总引力 ⭐⭐

字符串的总引力

思路

分类讨论：

如果 s[i] 之前没有遇到过，那么致谢子串的引力值都会增加 1，这些子串的引力值之和会增加 i，再加上1，即 s[i] 单独组成的子串的引力值。
如果 s[i] 之前遇到过，设其上次出现的下标为 j，那么向子串 s[0...i - 1], s[1...i - 1], s[2...i - 1], ..., s[j...i - 1] 的末尾添加s[i]后，这些子串的引力值是不会变化的，因为 s[i] 已经在 s[j] 出现过了；而子串s[j + 1 .. i - 1], s[j + 2 .. i - 1], .. ,s[i - 1 .. i - 1]由于不包含 s[i],这些子串的引力值都会增加 1，因此有 i - j - 1个子串的引力值会增加 1，这些子串的引力值之和会增加 i - j -1，在加上 1，即 s[i] 单独组成的子串的引力值。

题解

题解

class Solution {
public:
    long long appealSum(string s) {
        long long res = 0;
        vector<int> pos(26, -1);
        for(int i = 0, sum = 0; i < s.size(); i++){
            int a = s[i] - 'a';
            sum += i - pos[a];
            res += sum;
            pos[a] = i;
        }
        return res;
    }
};

时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，所以 ∣Σ∣=26。

执行用时：20 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：10.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：76 / 76

Atopos's Blog