1. LeetCode 5161. 可以输入的最大单词数

双指针统计空格,哈希表统计是否出现过

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        vector<int> hash(26);
        for(auto c : brokenLetters) hash[c - 'a'] ++;

        text += ' '; // 最后补个空格
        int n = 0, res = 0; // n统计单词个数，res统计不能输入的单词个数
        for(int i = 0; i < text.size();i ++ )
        {
            n ++;
            int j = i;
            while(j < text.size() && text[j] != ' ') j ++ ;

            for(int k = i;k < j;k ++ )
            {
                if(hash[text[k] - 'a']) {
                    res ++;
                    break;
                }
            }
            i = j;
        }
        return n - res;
    }
};

2. LeetCode 5814. 新增的最少台阶数

贪心

当间隔大于dist时，补充台阶数：(r[i + 1] - r[i] - 1) / dist

class Solution {
public:
    int addRungs(vector<int>& r, int dist) {
        int res = 0;

        if(r[0] - 0 > dist) res += (r[0] - 0 - 1) / dist;
        for(int i = 0;i + 1 < r.size();i ++ )
        {
            if(r[i + 1] - r[i] > dist) res += (r[i + 1] - r[i] - 1) / dist;
        }

        return res;
    }
};

3. LeetCode 5815. 扣分后的最大得分

参考题解:DP 优化技巧：拆项+前后缀最大值

思路分析:

难点：如何优化DP三重循环超时？（把绝对值拆开，然后预处理 前缀和后缀最大值，优化掉一重循环）

我的代码,时间复杂度O(nm),满足题目条件: 1 <= m * n <= 10^5

class Solution {
public:
    typedef long long LL;
    long long maxPoints(vector<vector<int>>& p) {
        int n = p.size(), m = p[0].size();

        vector<vector<LL>> f(n, vector<LL>(m));
        for(int i = 0;i < m;i ++ ) f[0][i] = p[0][i];

        for(int i = 1;i < n;i ++ )
        {
            LL maxl = -1e9;
            for(int j = 0;j < m;j ++ )
            {
                maxl = max(maxl, f[i - 1][j] + j);
                f[i][j] = max(f[i][j],maxl - j + p[i][j]);
            }

            LL maxr = -1e9;
            for(int j = m - 1;j >= 0;j -- )
            {
                maxr = max(maxr, f[i - 1][j] - j);
                f[i][j] = max(f[i][j],maxr + j + p[i][j]);
            }
        }

        LL res = 0;
        for(int i = 0;i < m;i ++ ) res = max(res,f[n - 1][i]);
        return res;
    }
};

附超时代码,时间复杂度O(nmm)

class Solution {
public:
    typedef long long LL;
    long long maxPoints(vector<vector<int>>& p) {
        int n = p.size(), m = p[0].size();

        vector<vector<LL>> f(n, vector<LL>(m));
        for(int i = 0;i < m;i ++ ) f[0][i] = p[0][i];

        for(int i = 1;i < n;i ++ )
            for(int j = 0;j < m;j ++ )
            {
                for(int k = 0;k < m;k ++ )
                {
                    f[i][j] = max(f[i][j],f[i - 1][k] + p[i][j] - abs(j - k));
                }
            }

        LL res = 0;
        for(int i = 0;i < m;i ++ ) res = max(res,f[n - 1][i]);
        return res;
    }
};

4. LeetCode 5816. 查询最大基因差

dfs + 字典树，时间复杂度O(nlogC),n为节点数$ 10^5 $ ,C为最大数值$ 2*10^5 $

没想清楚的点：如何保证枚举到结点的时候，父节点到该节点的链就存在了？ （dfs过程中先把父节点加进去，然后dfs返回就删除，用cnt[]标记）

const int N = 1e5 + 10, M = 16 * N; // 2 ^ 16 = 65536 > 2 * 10^5

typedef pair<int,int> PII;

int h[N],e[N],ne[N],idx1; // 数组模拟单链表的数据结构，记得h初始化为-1
int son[M][2], cnt[M], idx2; // 字典树的数据结构，cnt[]用来标记增加或删除

class Solution {
public:

    unordered_map<int,vector<PII>> qs; // 可能有多个相同的node，但求的val不同

    void add(int a,int b)
    {
        e[idx1] = b,ne[idx1] = h[a],h[a] = idx1 ++; 
    }

    void insert(int x,int v)
    {
        int p = 0;
        for(int i = 16;i >= 0;i -- )
        {
            int u = x >> i & 1;
            if(!son[p][u]) son[p][u] = ++ idx2;
            p = son[p][u];
            cnt[p] += v;
        }
    }

    int query(int x)
    {
        int p = 0, res = 0;
        for(int i = 16;i >= 0;i -- )
        {
            int u = x >> i & 1;
            if(cnt[son[p][!u]]) res = res * 2 + !u, p = son[p][!u];
            else res =  res * 2 + u, p = son[p][u]; // 相同，异或为0 
        }
        return x ^ res;
    }

    void dfs(int u, vector<int>& res) // dfs过程中就保证 链存在，然后在返回 就删除
    {
        insert(u, 1);

        if(qs.count(u))
            for(PII c : qs[u])
                res[c.second] = query(c.first);

        for(int i = h[u]; ~i; i = ne[i]) dfs(e[i], res);

        insert(u, -1);
    }


    vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
        memset(h, -1,sizeof h);
        idx1 = 0;

        memset(son,0,sizeof son);
        idx2 = 0;

        int root;
        for(int i = 0;i < parents.size();i ++ )
        {
            if(parents[i] == -1) root = i;
            else add(parents[i], i);
        }

        for(int i = 0;i < queries.size();i ++ )
        {
            int node = queries[i][0], val = queries[i][1];
            qs[node].push_back({val, i});
        }

        vector<int> res(queries.size());
        dfs(root, res);
        return res;
    }
};