291 场周赛

第一题

解法：模拟
按题意来直接模拟就行

class Solution {
public:
    string removeDigit(string number, char digit) {
        string ret;
        for (int i = 0; i < number.size(); ++ i) {
            if (number[i] == digit) {
                string t = number.substr(0, i) + number.substr(i + 1, number.size() - i - 1);
                ret = max(ret, t);
            }
        }
        return ret;
    }
};

第二题

解法：模拟
对每一个数记录其上次出现的位置，每次长度就为这两次位置的最小值，具体逻辑看代码

class Solution {
public:
    static const int N = 1e6 + 5;
    int mp[N];
    int minimumCardPickup(vector<int>& c) {
        int ret = 1e5 + 2;
        memset(mp, -1, sizeof mp);
        for (int i = 0; i < c.size(); ++ i) {
            if (mp[c[i]] != -1) {
                ret = min(ret, i - mp[c[i]] + 1);
            }
            mp[c[i]] = i;
        }
        return ret == 1e5 + 2 ? -1 : ret;
    }
};

第三题

解法：枚举

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {

        unordered_set<string> st;
        for (int len = 1; len <= nums.size(); ++ len) {
            int i = 0, j = 0;
            string t;
            int cnt = 0;
            while (j < nums.size()) {
                while (j - i < len) {
                    t += to_string(nums[j]);
                    t += "_";
                    if (nums[j] % p == 0) ++ cnt;
                    ++ j;
                }
                if (cnt <= k) {
                    st.insert(t);
                }

                int u = 0;
                while (u < t.size() && t[u] != '_') ++ u;
                if (u < t.size() - 1) {
                    t = t.substr(u + 1, t.size() - u - 1);
                }else {
                    t = "";
                }
                if (nums[i] % p == 0) -- cnt; 
                ++ i;
                
            }

        }
        return st.size();
        
    }
};

第四题

解法：枚举
枚举子串的起始下标 ii。设字符 cc 在下标 ii 右边第一次出现的下标是 jj，那么对于所有 j \le k < nj≤k<n，从 ii 开始，kk 结束（含 ii 和 kk）的子串都包含字符 cc，它们的引力都 +1，也就是说答案增加 (n - j)(n−j)。整体复杂度 \mathcal{O}(n|\Sigma|)O(n∣Σ∣)，其中 |\Sigma|∣Σ∣ 是字符集大小。

class Solution {
public:
    int mp[26];
    long long appealSum(string s) {
        long long ret = 0;
        memset(mp, -1, sizeof mp);
        for (int i = 0; i < s.size(); ++ i) {
            mp[s[i] - 'a'] = max(i, mp[s[i] - 'a']);
           // priority_queue<int, vector<int>, greater<int> > q;
            vector<int> d;
            for (int j = 0; j < 26; ++ j) {
                if (mp[j] != -1) {
                    // q.push(mp[j]);
                    d.push_back(mp[j]);
                } 
            }
            sort(d.begin(), d.end(), [](int& a, int& b){
                return a > b;
            });
            int last = -1;
            // while (q.size()) {
            //     ret += (q.top() - last) * q.size();
            //     last = q.top();
            //     q.pop();
            // }
            while (d.size()) {
                ret += (d.back() - last) * d.size();
                last = d.back();
                d.pop_back();
            }
        }
        return ret;
        
        
    }
};