这是上上周的周赛了...

这场周赛依然是双题选手...

2259. Remove Digit From Number to Maximize Result

Analysis

给定一个字符串，在不改变字符顺序的情况下，返回删除一个给定字符后，能得到的十进制下的最大结果。

Code

这是当时提交的代码：

class Solution {
public:
    string removeDigit(string number, char digit) {
        vector<int> indices;
        int len = number.length();
        for(int i = 0; i < len; i++) {
            if(number[i] == digit) indices.push_back(i);
        }
        if(indices.size() == 1) {
            number.erase(number.begin() + indices[0]);
            return number;
        } else {
            string max = number;
            max.erase(max.begin() + indices[0]);
            for(int i = 1; i < indices.size(); i++) {
                string t = number;
                t.erase(t.begin() + indices[i]);
                if(max < t) max = t;
            }
            return max;
        }
    }
};

看了下别人的思路，其实这个题完全可以不重新构造子串。
需要考虑的问题是对于有多个 digit 的字符串而言，删除哪一个位置的 digit 后得到的数是最大的。
分析一下，被删除的 digit 可能靠前，比如 1231，删除 1；也可能靠后，比如 1323，删除 3。这两种情况其实有个很容易忽略的细节在内，即删除的 digit 的后面的字符一定是大于 digit 的，或者删除的是末尾的 digit。
为什么会出现这种情况呢？因为前面的数字是在高位的，减少了一位后，每一位上的数字就变了，实际改变的就是结果数字的大小。比如 1231，如果删除后面的 1，那么 2 就变成了百十位，3 就变成了个位，但是如果删除前面的 1 ，2 就变成了百位，3 就变成了十位。结果就是，这个数字是删除后的数字中最大的。

class Solution {
public:
    string removeDigit(string number, char digit) {
        int len = number.length(), pos = -1;
        for(int i = 0; i < len; i++) {
            if(number[i] == digit) {
                pos = i;
                if(i + 1 < len && number[i] < number[i + 1]) break;
            }
        }
        number.erase(number.begin() + pos);
        return number;
    }
};

实质上是一种贪心的过程。

2260. Minimum Consecutive Cards to Pick Up

Analysis

找出左右边界相等的最短连续子序列。

Code

method 1

这是当时提交的代码：

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int size = cards.size();
        map<int, vector<int>> ht;
        for(int i = 0; i < size; i++) {
            ht[cards[i]].push_back(i);
        }
        int minimum = INT_MAX;
        for(auto &[x, v]: ht) {
            if(v.size() > 1) {
                int tmp = v[1] - v[0] + 1, s = v.size();
                for(int i = 1; i < s - 1; i++) {
                    if(tmp > v[i + 1] - v[i]) tmp = v[i + 1] - v[i] + 1;
                }
                if(minimum > tmp) minimum = tmp;
            }
        }
        if(minimum == INT_MAX) return -1;
        else return minimum;
    }
};

本质上是哈希 + 暴力搜索的思路，即找出每一对边界相同的子列，比较它们的大小，返回最小值。
换成 unordered_map 应该会好一些：

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int size = cards.size();
        unordered_map<int, vector<int>> ht;
        for(int i = 0; i < size; i++) {
            ht[cards[i]].push_back(i);
        }
        int minimum = INT_MAX;
        for(auto &[x, v]: ht) {
            if(v.size() > 1) {
                int tmp = v[1] - v[0] + 1, s = v.size();
                for(int i = 1; i < s - 1; i++) {
                    if(tmp > v[i + 1] - v[i]) tmp = v[i + 1] - v[i] + 1;
                }
                if(minimum > tmp) minimum = tmp;
            }
        }
        if(minimum == INT_MAX) return -1;
        else return minimum;
    }
};

果然，时间减少了大约一半。
多用了一个 hashmap，时间没怎么减少，内存倒是减少了：

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int size = cards.size();
        unordered_map<int, set<int>> ht1;
        unordered_map<int, int> ht2;
        for(int i = 0; i < size; i++) {
            if(ht2.count(cards[i])) ht1[cards[i]].insert(i - ht2[cards[i]] + 1);
            ht2[cards[i]] = i;
        }
        int minimum = INT_MAX;
        for(auto &[x, s]: ht1) {
            if(minimum > *s.begin()) minimum = *s.begin();
        }
        if(minimum == INT_MAX) return -1;
        else return minimum;
    }
};

理论分析时间复杂度应该是要优于上面只用一个 hashmap 的解法。
仔细想想，有必要把每一个左右边界相等的子序列的长度都算出来吗？
其实是没有的，只需要 hashmap 保存上一次的相等元素的下标即可，要得到最近的两个相等元素的长度，直接作差就可以了，然后再从这些值中找出最小值即可。

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int size = cards.size();
        unordered_map<int, int> ht;
        int minimum = INT_MAX;
        for(int i = 0; i < size; i++) {
            if(ht.count(cards[i])) minimum = min(minimum, i - ht[cards[i]] + 1);
            ht[cards[i]] = i;
        }
        if(minimum == INT_MAX) return -1;
        else return minimum;
    }
};

...还是自己太憨了😓。

method 2

看了下这道题的标签，好像也是个滑动窗口的题目。

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int size = cards.size();
        unordered_set<int> ht;
        int left, right, ans;
        left = right = 0;
        ans = INT_MAX;
        while(right < size) {
            while(ht.count(cards[right])) {
                ans = min(ans, right - left + 1);
                ht.erase(cards[left]);
                left++;
            }
            ht.insert(cards[right]);
            right++;
        }
        if(ans == INT_MAX) return -1;
        else return ans;
    }
};

滑动窗口也需要用一个 hashmap 来判断，当前数字是不是之前出现过（出现过才可以构成符合条件的子序列）。
PS：这个题的 $cards[i]$ 的范围是 $[0, 10^6]$，所以直接开个很大的数组当 hashmap 来用，运行时间会快很多。

2022年5月14日，消停了几天，我又回来了。

2261. K Divisible Elements Subarrays

Analysis

虽然题目很短，但是感觉是个比较麻烦的题目。首先需要找出符合条件的子数组，但是为了确保唯一性，还需要检查是否子数组是否出现过，所以这个题不能简单的用滑动窗口的思路来处理。

Code

暴力解法还是很容易想到的（当时比赛怎么没想到啊😂）。

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        map<vector<int>, bool> ht;
        int ret = 0, size = nums.size();
        for(int i = 0; i < size; i++) {
            vector<int> tmp;
            int cnt = 0;
            for(int j = i; j < size; j++) {
                tmp.push_back(nums[j]);
                if(nums[j] % p == 0) cnt++;
                if(cnt > k) break;
                else {
                    if(!ht.count(tmp)) {
                        ht[tmp] = true;
                        ret++;
                    }
                }
            }
        }
        return ret;
    }
};

本以为 nums 的长度范围只有 $[1, 200]$，暴力解法应该也可以通过，结果还是无法通过。
为了确保解的唯一性，hash 表没办法拿掉，想要提高时间效率，就得在找解的方法上下功夫。
看了下官方题解，没有用子数组来作为哈希的 key，而是将子数组序列化为字符串，让这个字符串作为哈希元素，其他的思路基本上是一致的。

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_set<string> arrs;
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            string s;
            int cnt = 0;
            for(int j = i; j < size; j++) {
                if(nums[j] % p == 0) cnt++;
                if(cnt > k) break;
                s.append(to_string(nums[j]));
                s.push_back('#');
                arrs.insert(s);
            }
        }
        return arrs.size();
    }
};

这段代码是可以通过的。回头想想，应该是直接将子数组作为 map 的 key 导致消耗的时间太多了。更要命的是，我还用了count函数，不如直接ht[cnt] = xxx;，最后直接返回ht.size()。

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        map<vector<int>, bool> ht;
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            vector<int> tmp;
            int cnt = 0;
            for(int j = i; j < size; j++) {
                tmp.push_back(nums[j]);
                if(nums[j] % p == 0) cnt++;
                if(cnt > k) break;
                ht[tmp] = true;
            }
        }
        return ht.size();
    }
};

没想到，改了下还真的可以通过了😂，就是时间、空间消耗惨不忍睹。就这个题而言，没办法通过的原因，很大一部分是对 map、set 这类容器的不了解...

2262. Total Appeal of A String

Analysis

这个题是前面几个题的进化版😂，感觉用第 3 个题的思路，完全可以。不过数据范围是 $10^5$，$O(n^2)$ 铁定得超时。

Code

这是当时提交的超时代码：

class Solution {
public:
    long long appealSum(string s) {
        long long ret = s.length();
        int len = s.length();
        unordered_set<char> ht;
        for(int i = 0; i < len; i++) {
            ht.insert(s[i]);
        }
        ret += ht.size();
        for(int step = 2; step < len; step++) {
            for(int i = 0; i <= len - step; i++) {
                unordered_set<char> ht;
                int start = i, end = i + step;
                while(start < end) {
                    ht.insert(s[start]);
                    start++;
                }
                ret += ht.size();
            }
        }
        return ret;
    }
};

现在看，感觉当时想复杂了，思路是按照不同长度来枚举子字符串，结果死在 52 个用例了。
这是刚刚写的：

class Solution {
public:
    long long appealSum(string s) {
        long long ret = 0;
        int len = s.length();
        unordered_map<string, int> ht;
        for(int i = 0; i < len; i++) {
            string tmp;
            for(int j = i; j < len; j++) {
                tmp.push_back(s[j]);
                ht[tmp]++;
            }
        }
        for(auto &[str, times]: ht) {
            vector<int> cnt(26);
            int l = str.length();
            for(int i = 0; i < l; i++) {
                cnt[str[i] - 'a']++;
            }
            int count = 0;
            for(int i = 0; i < 26; i++) {
                if(cnt[i] > 0) count++;
            }
            ret += count * times;
        }
        return ret;
    }
};

用了下哈希的思路，死在 55 个用例了，尽量一个循环就把单个字符串的引力算出。

class Solution {
public:
    long long appealSum(string s) {
        long long ret = 0;
        int len = s.length();
        unordered_map<string, int> ht;
        for(int i = 0; i < len; i++) {
            string tmp;
            for(int j = i; j < len; j++) {
                tmp.push_back(s[j]);
                ht[tmp]++;
            }
        }
        for(auto &[str, times]: ht) {
            vector<int> cnt(26);
            int l = str.length();
            int count = 0;
            for(int i = 0; i < l; i++) {
                if(cnt[str[i] - 'a'] == 0) {
                    count++;
                }
                cnt[str[i] - 'a']++;
            }
            ret += count * times;
        }
        return ret;
    }
};

结果死在 53 个用例了，等等，用 set 不是更香😂？

class Solution {
public:
    long long appealSum(string s) {
        long long ret = 0;
        int len = s.length();
        unordered_map<string, int> ht;
        for(int i = 0; i < len; i++) {
            string tmp;
            for(int j = i; j < len; j++) {
                tmp.push_back(s[j]);
                ht[tmp]++;
            }
        }
        for(auto &[str, times]: ht) {
            unordered_set<char> se;
            for(auto &c: str) {
                se.insert(c);
            }
            ret += se.size() * times;
        }
        return ret;
    }
};

结果死在 52 个用例了😂，set 比 vector 省事了不少，就是时间消耗越来越多了。
看了下别人的题解，这个题好像是 dp 和字符串的结合题。

class Solution {
public:
    long long appealSum(string s) {
        long long ret = 0;
        int len = s.length();
        vector<int> last(26, -1);
        for(int i = 0, sum_g = 0; i < s.length(); i++) {
            int c = s[i] - 'a';
            sum_g += i - last[c];
            ret += sum_g;
            last[c] = i;
        }
        return ret;
    }
};