LeetCode --- 434周赛

一、统计元素和差值为偶数的分区方案

统计元素和差值为偶数的分区方案
本题可以直接模拟，当然我们也可以来从数学的角度来分析一下这题的本质

设 $S$ 为数组之和， $L$ 为 $[0, i]$ 的区间和，则 $S - L$ 为 $[i + 1, n - 1]$ 的区间和，对于任意的 $i$ ，左右子数组的区间和差值为 $L - (S - L) = 2 L - S$ ，题目问有几个 $i$ 的 $2 L - S$ 为偶数，显然 $2 L - S$ 是否为偶数只和 $S$ 有关，当 $S$ 为偶数时， $2 L - S$ 总是为偶数。

故本题的答案是固定的，要么所有的 $2 L - S$ 都是偶数，有 $n - 1$ 个，要么都不为偶数，有 $0$ 个，代码如下

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int n = nums.size();
        int s = accumulate(nums.begin(),nums.end(), 0);
        return s % 2 ? 0 : n - 1;
    }
};

二、统计用户被提及情况

统计用户被提及情况
本题是一个纯模拟题，关键在于如何统计每个用户被提及的次数，而这取决于该用户是否在线。这里我们可以记录每一个用户的最近一次的在线时间，在用它和消息发送的时间进行比较，从而判断出当前消息是否提及该用户，代码如下

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        // cnt 统计答案，online 记录每个用户最近一次上线时间
        vector<int> cnt(numberOfUsers), online(numberOfUsers);
        // 按时间顺序排序，注意：题目要求离线操作优先级更高
        ranges::sort(events, [](const auto& x, const auto & y){
            int tx = stoi(x[1]), ty = stoi(y[1]);
            return tx != ty ? tx < ty : x[0][0] == 'O';
        });
        for(auto e : events){
            int time = stoi(e[1]);
            if(e[0][0] == 'O'){
                online[stoi(e[2])] = time + 60; // 跟新最新上线时间
            }else if(e[2][0] == 'A'){
                for(auto& x : cnt) x++;
            }else if(e[2][0] == 'H'){
                for(int i = 0; i < numberOfUsers; i++){
                    if(online[i] <= time){
                        cnt[i]++;
                    }
                }
            }else{
                string t;
                for(stringstream ss(e[2]); ss >> t; cnt[stoi(t.substr(2))]++);
            }
        }
        return cnt;
    }
};

三、子数组操作后的最大频率

子数组操作后的最大频率
本题题意为我们可以将任意区间内值为 $x$ 的数变为 $k$ ，返回进行一次操作后， $k$ 出现的最大频率。显然，我们要分 $3$ 个部分统计 $k$ 的出现次数

假定我们让 $[l, r]$ 内的 $x$ 全部变为 $k$
$k$ 的出现次数 $= [0, l)$ 内的 $k$ 的次数 $+ [l, r]$ 内的 $x$ 的出现次数 $+ (r, n)$ 内的 $k$ 的出现次数

思路：

由于 $n u m s$ 中数字范围为 $1$ ~ $50$ ，所以我们可以暴力枚举需要改变的数字 $x$
子数组相关的问题，可以考虑用动态规划来思考
- $f [i] [0]$ 表示当 $i$ 处于 $[0, l)$ 中时， $[0, i]$ 中 $k$ 的最大出现次数
- $f [i] [1]$ 表示当 $i$ 处于 $[l, r]$ 中时， $[0, i]$ 中 $k$ 的最大出现次数
- $f [i] [2]$ 表示当 $i$ 处于 $(r, n)$ 中时， $[0, i]$ 中 $k$ 的最大出现次数

$f [i] [0] = f [i - 1] [0] + (n u m s [i] == k)$ ，因为 $i\in[0,l)$ ，则 $i-1\in[0,l)$ ，所以它只能由自己转移来
$f [i] [1] = ma x (f [i - 1] [0], f [i - 1] [1]) + (n u m s [i] == x)$ ，因为 $i\in[l,r]$ ，则 $i-1\in[l,r]$ 或者 $i - 1 = l - 1$ ，所以它可以由 $f [i - 1] [0]$ 和 $f [i - 1] [1]$ 转移来
$f [i] [2] = ma x (f [i - 1] [1], f [i - 1] [2]) + (n u m s [i] == k)$ ，因为 $i\in(r,n)$ ，则 $i-1\in(r,n)$ 或者 $i - 1 = r$ ，所以它可以由 $f [i - 1] [0]$ 和 $f [i - 1] [1]$ 转移来

代码如下

class Solution {
    // 0 1 2
    // f[i][j] 表示 i 为 j 状态时，k 出现的最大频率
    // j = 0, f[i][0] = f[i-1][0] + nums[i] == k
    // j = 1, f[i][1] = max(f[i-1][1], f[i-1][0]) + nums[i] == x
    // j = 2, f[i][2] = max(f[i-1][2], f[i-1][1]) + nums[i] == k
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        set<int> st(nums.begin(), nums.end());
        int ans = 0;
        for(auto x : st){
        	vector<array<int, 3>> f(n + 1);
            for(int i = 0; i < n; i++){
                f[i+1][0] = f[i][0] + (nums[i] == k);
                f[i+1][1] = max(f[i][1], f[i][0]) + (nums[i] == x);
                f[i+1][2] = max(f[i][2], f[i][1]) + (nums[i] == k);
            }
            // 注意：答案只可能在 f[n][1] 或者 f[n][2] 中，因为修改数字总比不修改数字更优
            ans = max({ans, f.back()[1], f.back()[2]});
        }
        return ans;
    }
};

// 空间优化
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        set<int> st(nums.begin(), nums.end());
        int ans = 0;
        for(auto x : st){
            int f[3]{};
            for(int i = 0; i < n; i++){
                f[2] = max(f[2], f[1]) + (nums[i] == k);
                f[1] = max(f[1], f[0]) + (nums[i] == x);
                f[0] = f[0] + (nums[i] == k);
            }
            ans = max({ans, f[1], f[2]});
        }
        return ans;
    }
};

四、最短公共超序列的字母出现频率

最短公共超序列的字母出现频率
在这里插入图片描述
由于 $w or d s [i] . l e n g t h == 2$ ，所以对于任意字符来说，只要它的出现次数为 2，则可以组成任意一个包含该字符的 $w or d$ ，前提是我们将出现了两次的字符都对称的放在两侧，比如字符 $a 、 b$ ，如果我们的公共超序列为 $ab c d e ba$ ，则 $ab 、 a c 、 a d 、 a e 、 ba 、 c a 、 d a 、 e a 、 aa$ 所有包含 $a$ 的组合都能得到，同理 $b$ 也是一样

简单的证明如下
对于字符串 $a * * * * * a$ ，显然能组成任意包含字符 $a$ 的长度为 $2$ 的子序列
对于字符串 $ab * * * ba$ ，去掉字符 $a$ 后得字符串 $b * * * b$ ，显然能组成任意包含 $b$ 的长度为 $2$ 的子序列，除了 $ab 、 ba$ ，但是我们在计算字符 $a$ 的组合时，已经计算过 $ab 、 ba$ 了，故我们能得出包含字符 $a$ 或 $b$ 的任意组合的长度为 $2$ 的子序列
当字符串为 $ab c * * * c ba 、 ab c d * * * d c ba 、 ...$ 时，同上
通过数学归纳法，得出结论：如果给定的一个或多个字符的个数为 $2$ ，则我们可以通过上述的构造形式，得到长度为 $2$ 的包含这些字符的所有子序列组合

所以最短公共超序列中每个字符的出现次数要么为 $1$ ，要么为 $2$ 。而 $w or d s$ 中最多只有 $16$ 种不同的字符，我们可以枚举每种字符的出现次数的所有可能情况。 $($ 最多有 $2^{16}$ 种可能 $)$

故我们的问题变为判断每种情况是否合法，即是否满足题目要求。根据上面的结论，我们只要关心出现一次的字符即可。
比如对于 $ab c$ 这样的最短公共超序列，如果 $words =\{ab、bc、ca \}$ ，则不能满足条件，因为一个 $a$ 不能同时出现在 $c$ 的两边，我们可以将 $w or d s$ 抽象成一个有向图，其中 $ab$ 表示 $a\rightarrow b$ 这样一条边，我们只要判断对于出现次数为 $1$ 的字符，在 $w or d s$ 抽象成的有向图中是否有环即可。如果有环则不合法，反之，则合法。

代码如下

class Solution {
public:
    vector<vector<int>> supersequences(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> g(26);
        int all = 0; // 用 bit 位是否为 1，表示字符是否出现过
        for(auto s : words){
            int x = s[0] - 'a', y = s[1] - 'a';
            all |= (1 << x) | (1 << y);
            g[x].push_back(y);
        }
        auto has_cycle = [&](int sub)->bool{
            int color[26]{};
            // 判断是否有环
            auto dfs = [&](this auto&& dfs, int x)->bool{
                color[x] = 1;
                for(int y : g[x]){
                    if(sub >> y & 1) // 只关注出现次数为 1 次的字符
                        continue;
                    if(color[y] == 1 || color[y] == 0 && dfs(y))
                        return true;
                }
                color[x] = 2;
                return false;
            };
            // 有向图不一定连通，所以要字符都要遍历一遍
            for(int i = 0; i < 26; i++){
                if(color[i] == 0 && (sub >> i & 1) == 0 && dfs(i)) // 只关注出现次数为 1 次的字符
                    return true;
            }
            return false;
        };
        unordered_set<int> st;
        int min_size = INT_MAX;
        int sub = all; // sub 中用 bit 位是否为 1，表示字符是否出现了 2 次
        // 遍历字符的出现次数的所有可能情况
        do{
            int size = __builtin_popcount((unsigned) sub);
            if(size <= min_size && !has_cycle(sub)){
                if(size < min_size){
                    min_size = size;
                    st.clear();
                }
                st.insert(sub);
            }
            sub = all & (sub - 1);
        }while(sub != all);
        // 记录答案
        vector<vector<int>> ans;
        for(int sub : st){
            vector<int> cnt(26);
            for(int i = 0; i < 26; i++){
                cnt[i] = (all >> i & 1) + (sub >> i & 1);
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};