LC_291

第三题

1. 枚举子串开头位置 $i$，然后枚举子串结束位置 $j$，动态计算出当前子数组组成的字符串 $s$。
2. 注意，组成 $s$ 的过程需要在每一个数字后添加一个特殊分隔符来区分，避免冲突。
3. 如果哈希表中不存在 $s$，则答案加一，然后存入哈希表。
4. 可以用字典树实现哈希表的功能，字典树节点的分支数量可以设为四个，三进制存储数字，剩一位存储特殊分隔符。

也可以不用特殊分隔符来区分，因为要求序列不重复，所以计算一个哈希前缀和即可；

方法一：暴力枚举+哈希表

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n=nums.size();
        set<string> s;
        for(int i=0;i<n;i++)
        {
            int cnt=0;
            string t="";
            for(int j=i;j<n;j++)
            {
                if(nums[j]%p==0) ++cnt;
                if(cnt<=k){
                    t+=',';
                    t+=to_string(nums[j]);
                    s.insert(t);
                }
                else {
                    break;
                }
            }
        }
        return s.size();

    }
};

方法二：哈希前缀和+双哈希

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_set<long long> s;
        int n = nums.size(), mod = 1e9 + 7, power1 = 233, power2 = 2333;
        for(int i = 0; i < n; ++i) {
            for(int j = i, cnt = 0, hash1 = 0, hash2 = 0; j < n; ++j) {
                if(nums[j] % p == 0) ++cnt;
                if(cnt > k) {
                    break;
                }
                hash1 = (1ll * hash1 * power1 + nums[j]) % mod;
                hash2 = (1ll * hash2 * power2 + nums[j]) % mod;
                s.insert(((long long)hash1 << 32) | hash2);
            }
        }
        return s.size();
    }
};

第四题

方法一: DP

1. 提示 1-1
   将所有子串按照其末尾字符的下标分组。

2. 提示 1-2
   考虑两组相邻的子串：以 s[i-1]s[i−1] 结尾的子串、以 s[i]s[i] 结尾的子串。

3. 提示 1-3
   以 s[i]s[i] 结尾的子串，可以看成是以 s[i-1]s[i−1] 结尾的子串，在末尾添加上 s[i]s[i] 组成。

上面这一串提示是思考子串统计类问题的通用技巧之一。

从左往右遍历 $s$，考虑将 $s[i]$ 添加到以$ s[i-1]$ 结尾的子串的末尾。添加后，这些子串的引力值会增加多少？

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

模拟上述过程，遍历 $s$ 的过程中用一个变量$ \textit{sumG} $维护以 $s[i]$ 结尾的子串的引力值之和，同时用一个数组 $\textit{last}$ 记录每个字符上次出现的下标。

累加遍历中的 $\textit{sumG}$ 即为答案。

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

方法二： (思维题) $O(n + |\Sigma|)$

1. 独立统计每个字符的贡献。
2. 进一步逆向思维，统计子串中未出现当前字符的数量，然后用全量子串减去这个数量就是这个字符的贡献。
3. 未出现当前字符的子串一定出现在相邻两个该字符的位置之间，以及首次出现的位置之前以及最后一次出现的位置之后。

时间复杂度

• 遍历字符串一次，遍历所有字符一次，故总时间复杂度为 $O(n + |\Sigma|)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储每个字符的出现位置。

#define LL long long

class Solution {
public:
    LL appealSum(string s) {
        const int n = s.size();
        vector<int> seen(26, -1);

        LL ans = 0;
        for (int i = 0; i < n; i++) {
            int last = seen[s[i] - 'a'];

            seen[s[i] - 'a'] = i;

            if (last == -1)
                ans += (LL)(n) * (n + 1) / 2;

            ans -= (LL)(i - last - 1) * (i - last) / 2;
        }

        for (int i = 0; i < 26; i++)
            if (seen[i] >= 0)
                ans -= (LL)(n - seen[i]) * (n - seen[i] - 1) / 2;

        return ans;
    }
};

方法三：独立统计每个字符的贡献。

记录每一个字符的位置，只统计第一次出现的贡献，后面出现的统计两者之间的字符，

#define LL long long 
class Solution {
public:
    vector<int> pos[30];
    long long appealSum(string s) {
        int n=s.size();
        for(int i=0;i<n;i++) pos[s[i]-'a'].push_back(i);

        LL ans=0;
        for(int i=0;i<26;i++){
            int m=pos[i].size();
            for(int k=0;k<m;k++){
                LL res=1;
                if(k==0) res=res*(pos[i][k]+1);
                else res=res*(pos[i][k]-pos[i][k-1]);

                res=res*(n-pos[i][k]);
                ans+=res;
            }
        }
        return ans;
    }
};

LC_292

第三题

f[i] 长度为 i的字符串有多少中信息

class Solution {
public: 
    const int N = 100000;
    int f[100007],v[100007];
    int countTexts(string s) {

        long long ans=1;
        int mod=1e9+7;
        // dp 转移
        // 对于第i个字符，有可能是一个数字，有可能是两个数字，有可能是三个数字，这样算贡献
        f[0]=1;
        for(int i=0;i<N;i++)
            for(int j=i+1;j<=i+3 && j<=N;j++)
                f[j]+=f[i],f[j]%=mod;
        v[0]=1;
        for(int i=0;i<N;i++)
            for(int j=i+1;j<=i+4 && j<=N;j++)
                v[j]+=v[i],v[j]%=mod;

        int n = s.size();
        char t=s[0];
        int cnt=0;
        for(char c:s)
        {
            if(c!=t)
            {
                if(t=='7' || t=='9')
                    ans=(ans*v[cnt])%mod;
                else
                    ans=(ans*f[cnt])%mod;
                cnt=0;
                t=c;
            }
            ++cnt;
        }
        if(t=='7' || t=='9')
            ans=(ans*v[cnt])%mod;
        else
            ans=(ans*f[cnt])%mod;
        return ans;
    }
};

第四题：

合法序列的核心：任一时刻左括号大于右括号的数量，最后左括号等于右括号的数量。

f[i][j]][k] 表示第i行，第j列，k = 左括号数量-右括号数量

class Solution {
public:
    bool f[101][101][201];
    bool hasValidPath(vector<vector<char>>& s) {
        if(s[0][0]=='(')
            f[0][0][1]=true;
        else 
            return false; 

        int l=0,r=0;
        int n=s.size(),m=s[0].size();
        // dp 三角形模型
        // 从当前合法状态，想办法转移到下一个合法状态
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<200;k++)
                    if(f[i][j][k]){
                        if(i+1<n){
                            int l=k;
                            if(s[i+1][j]=='(')
                                ++l;
                            else 
                                --l;
                            if(l>=0)
                                f[i+1][j][l]=true;
                        }
                        if(j+1<m){
                            int l=k;
                            if(s[i][j+1]=='(')
                                ++l;
                            else 
                                --l;
                            if(l>=0)
                                f[i][j+1][l]=true;
                        }
                    }
            return f[n-1][m-1][0];

    }
};

LC_303

2022年7月24日

T3：

堆（优先队列）和平衡树（set）支持找最小值的操作

平衡树修改任一值，优先队列只支持修改最小值

hash：string –> 平衡树

双关键字排序，所以用 pair 存储，且 平衡树 按照 pair 的递增方式排序，依据题目规则所以存储的时候 存为 {-rating，food} ，rating 越大 值越小，越在前面,第二关键字 food 按照字典序排列

代码

class FoodRatings {
public:
    // hash: string --> set
    // set 中存储了所有的食物的 rating 和名称
    unordered_map<string,set< pair<int,string> > > q;

    // c 是从食物到烹饪方式的对应
    unordered_map<string,string> c;

    // r 是从食物到rating 的对应
    unordered_map<string,int> r;
    FoodRatings(vector<string>& f, vector<string>& co, vector<int>& ra) {
        int n =f.size();

        for(int i=0;i<n;i++){
            string food = f[i];
            q[co[i]].insert({-ra[i],f[i]});
            c[food]=co[i];
            r[food]=ra[i];
        }

    }
    void changeRating(string food, int newRating) {
        q[c[food]].erase(make_pair(-r[food],food));
        r[food]=newRating;
        q[c[food]].insert(make_pair(-r[food],food));

    }

    string highestRated(string cuisine) {
        return  q[cuisine].begin()->second;
    }
};

T4

考虑两个数 $a$ 和 $b$,题目要求 a&b 和 a|b 的二进制二进制表示中值为 1 的位数之和大于等于 k ，所以肯定要将 $a$ 和 $b$ 二进制表示

对于 a&b 和 a|b 每一位上的数字是相互独立的

对于 第 $i$ 位 来说

1. a&b = 1 和 a|b = 1 ，贡献 为 2 –》a = b = 1
2. a&b = 1 和 a|b = 0 ，贡献 为 1 –》a=1,b=0/ a=0,b=1
3. a&b = 0 和 a|b = 1 ，贡献 为 1 –》a=1,b=0/ a=0,b=1
4. a&b = 0 和 a|b = 0 ，贡献 为 0 –》a = b = 0

四种情况正好对应了 a 和 b 的四种情况，即每个数中 1 的个数等于 贡献

所以我们 开一个数组 c[i] 表示 1的个数为i 在数组中出现的次数

重复的值会多算一遍，所以要先去重。

由数据范围是 int 的，只会有 30 位

$(i,j)$ 和 $(j,i)$ 计为两个数对

故 两重循环

// c[i] 表示 1的个数为i 在数组中出现的次数
// i+j>=k 即可满足题意，使得数对为 “ 优质数对 ”
for(int i=0;i<30;i++)
    for(int j=0;j<30;j++)
        if(i+j>=k)
            ans += c[i]*c[j];

代码

typedef long long LL;
class Solution {
public:
    int c[30];
    long long countExcellentPairs(vector<int>& nums, int k) {

        // 去重
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());

        // 计算数位和
        for(auto x:nums){
            int s =0;
            while(x) s+=x&1,x>>=1;
            c[s]++;
        }
        // 统计贡献
        LL ans =0;
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                if(i+j>=k)
                    ans += (LL) c[i]*c[j];
        return ans;
    }
};