Leetcode 第 291 场周赛 题解

Leetcode 第 291 场周赛 题解

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

手速，场上我的做法是暴力枚举。

class Solution {
public:
    string removeDigit(string number, char digit) {
        string s;
        for (int i = 0; i < number.length(); ++i) {
            int pos = number.find(digit, i);
            if (pos != -1) {
                s = max(s, number.substr(0, pos) + number.substr(pos + 1));
            }
        }
        return s;
    }
};

很明显可以见到，赛场上复杂度写炸了，虽然数据小肯定能过，但肯定不是正解。没办法，手速题想到啥写啥。

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

同样是手速题，没啥可说的。

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        unordered_map<int, int> mp;
        int ans = numeric_limits<int>::max();
        for (int i = 0; i < cards.size(); ++i) {
            if (mp.count(cards[i])) {
                ans = min(ans, i - mp[cards[i]] + 1);
            }
            mp[cards[i]] = i;
        }
        return ans == numeric_limits<int>::max() ? -1 : ans;
    }
};

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

看了下数据范围，我直接暴力枚举，草草了事。最多加个前缀和加速一下。时间复杂度 $O(n^3logn)$，跑了 1400 ms。

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n = nums.size();

        auto sum = vector<int>(n + 1);

        auto ans = set<vector<int>>();

        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + (nums[i - 1] % p == 0);
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (sum[i] - sum[j - 1] <= k) {
                    vector<int> temp(nums.begin() + j - 1, nums.begin() + i);
                    ans.emplace(temp);
                }
            }
        }
        return ans.size();
    }
};

由于 std::vector 不支持 std::unordered_set，其实加个 std::hash 支持就可以把时间复杂度降到 $O(n^3)$ 了，跑了 500 ms。

template<>
struct std::hash<std::vector<int>> {
    size_t operator () (const std::vector<int>& x) const noexcept {
        return accumulate(x.begin(), x.end(), 0);
    }
};

最后可以通过手写一个 slice 类型，通过预计算哈希值，从而把时间和空间复杂度降到 $O(n^2)$。运行时间 176 ms。

struct Slice {
    int *left = nullptr;
    int *right = nullptr;
    size_t hashCode = 0;

    bool operator == (const Slice& s) const noexcept {
        if (hashCode != s.hashCode) return false;
        if (right - left != s.right - s.left) return false;
        return equal(left, right, s.left, s.right);
    }
};

template<>
struct std::hash<Slice> {
    size_t operator () (const Slice& s) const noexcept {
        return s.hashCode;
    }
};

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n = nums.size();
        unordered_set<Slice> ans;

        for (int i = 1; i <= n; ++i) {
            size_t hashCode = 0;
            int count = 0;
            for (int j = i; j <= n; ++j) {
                hashCode = hashCode * 57 + nums[j - 1];
                count += (nums[j - 1] % p == 0);
                if (count <= k) {
                    Slice s;
                    s.left = nums.data() + i - 1;
                    s.right = nums.data() + j;
                    s.hashCode = hashCode;
                    ans.emplace(s);
                } else {
                    break;
                }
            }
        }
        return ans.size();
    }
};

最后，可以试试玄学 双哈希，速度飞快，时间复杂度 $O(n^2)$，运行时间 116ms。

using ll = long long;
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n = nums.size();
        
        unordered_set<ll> ans;
        ans.reserve(n * n);
        
        for (int i = 1; i <= n; ++i) {
            unsigned hashCode[2] = {};
            int count = 0;
            for (int j = i; j <= n; ++j) {
                hashCode[0] = hashCode[0] * 57 + nums[j - 1];
                hashCode[1] = hashCode[1] * 31 + nums[j - 1];
                count += (nums[j - 1] % p == 0);
                if (count <= k) {
                    ans.emplace(*reinterpret_cast<ll *>(hashCode));
                } else {
                    break;
                }
            }
        }
        return ans.size();
    }
};

4. 字符串的总引力

这题想了很久，老是想着从 集合 和 后缀 的方向入手。事实证明，后缀 的方向是对的，但总体思考方向错了，导致想题想了很久。

赛场的解法: 枚举 引力，找 引力 为 $x$ 的子字符串的个数 $count(x)$，答案就是 $\sum x \times count(x)$。

那么怎么求 $count(x)$ 呢： 可以通过 两个滑动窗口 来解决，分别表示以 $s[i]$ 结尾的子串， 引力 为 $x$ 的最大窗口和最小窗口，过程中统计两个窗口大小的差值 $delta$，并累加答案 $ans = ans + delta \times x$。时间复杂度 $O(26* n)$。

using ll = long long;

class Solution {
public:
    ll appealSum(string s) {
        int n = s.length();

        ll ans = 0;
        for (int x = 1; x <= 26; ++x) {
            int cnt[128] = {}, sum = 0;
            int minLeft = 0;
            int maxLeft = 0;
            ll temp = 0;
            for (int i = 0; i < n; ++i) {
                if (cnt[s[i]]++ == 0) {
                    sum++;
                }
                while (sum > x) {
                    if (--cnt[s[maxLeft]] == 0) {
                        sum--;
                    }
                    maxLeft++;
                    minLeft = maxLeft;
                }
                while (cnt[s[maxLeft]] > 1) {
                    cnt[s[maxLeft]]--;
                    maxLeft++;
                }
                if (sum == x) {
                    temp += maxLeft - minLeft + 1;
                }
            }
            ans += temp * x;
        }
        return ans;
    }
};

正确解法: 设字符串 $x$ 的 引力 为 $f(x)$。由于子串 $s[:i]$ 总是由 $s[:i-1] + s[i]$ 构成，不妨考虑加入 $s[i]$ 后，总引力如何发生改变。

• 假如 s[i] 从来没有在前面的子串出现过，那么对 $0 \le j \lt i$，都有 $f(s[j:i])=f(s[j:i-1]) + 1$。
• 假如 s[i] 最近在 $k$ 出现过，那么对 $0 \le j \le k$，都有 $f(s[j:i])=f(s[j:i-1])$，对 $k \lt j \lt i$，都有 $f(s[j:i])=f(s[j:i-1]) + 1$。

以上都是显然的，只要大家在纸上写写过程，很快都能推导出来。根据以上结论，我们设 $dp(i)$ 为以 s[i] 结尾的子串的引力和，那么有：

• 假如 s[i] 从来没有在前面的子串出现过，那么 $dp(i) = dp(i-1) + i$
• 假如 s[i] 最近在 $k$ 出现过，那么 $dp(i) = dp(i-1) + (i - k)$

只需要记录最近出现的 s[i]，然后 DP 即可，时间复杂度 $O(n)$。

class Solution {
public:
    long long appealSum(string s) {
        int n = s.length();
        auto last = vector<int>(128);
        auto dp = vector<long long>(n + 1);

        long long ans = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + (i - last[s[i - 1]]);
            last[s[i - 1]] = i;
            ans += dp[i];
        }

        return ans;
    }
};