Leetcode 361 周赛题解

1
统计对称整数的数目
这个题目直接暴力枚举从low-> high的每个数字，判断是否满足条件。
可以用c++ 的数字和字符串的转换stoi函数实现。
代码如下:
```class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for(int i = low;i<=high;++i){
            string t = to_string(i);
            if(t.size()%2 == 0){
                string c1 = t.substr(0,t.size()/2);
                string c2 = t.substr(t.size()/2);
                int s1 = 0, s2 = 0;
                for(auto c: c1){
                    s1 += c-'0';
                }
                for(auto c: c2){
                    s2 += c-'0';
                }
                if(s1 == s2) ans ++;
            }
        }
        return ans;
    }
};
```


第二题：生成特殊数字的最少操作
这个题目只有几种
以25 ，50,00 ,75结尾。或者最终只剩一个0.
那么针对5后缀和0后缀分别写一个函数。
我们一直删除数字，直到后缀为5 或者0。
后缀为5的时候： 看一下倒数第二位是否有可能为2 或者7
后缀为0的时候： 看一下倒数第二位是否有可能为0或者5
coner case:
如果出现0那么最少需要删除num.length()-1个（因为可以保留这个0）。
代码：
class Solution {
public:
    int findfive(string num){
        int tot = num.size();
        while(num.size() && num.back() != '5') {num.pop_back();}
        if(num.size() == 0) return tot;
        int n = num.size();

        string ans = "";
        for(int i = n-2;i>=0;--i) {
            if(num[i] == '2' || num[i] == '7'){
                ans = num.substr(0,i+1) + num.back();
                break;
            }
        }
        return tot - ans.size();
    }
    int findzero(string num){
        int tot = num.size();
        bool haszero = false;
        int number = tot;
        for(auto c: num){
            if(c == '0') haszero = true;
        }
        if(haszero) {
            number = tot - 1;
        }
        while(num.size() && num.back() != '0') {num.pop_back();}
        int n = num.size();

        string ans = "";
        for(int i = n-2;i>=0;--i) {
            if(num[i] == '0' || num[i] == '5'){
                ans = num.substr(0,i+1) + num.back();
                break;
            }
        }

        return min(tot - (int)ans.size(), number);
    }

    int minimumOperations(string num) {
        int ans= min(findzero(num), findfive(num));
        return ans;
    }
};


第三题： 统计趣味子数组的数目
这个题目我们看到统计区间个数以后，立刻想到暴力做法（扫描区间两个端点，然后判断）O(n^3)。但是看一眼时间复杂度不够。
因此，我们看一下是否可以做到以r为终结点，当前前缀和为sum，然后看有多少个pre前缀和满足
sum + pre =  modole * n + k
那么我们只需要对等式两边同时mod modulo即可。
对应的pre = (sum - k )%modulo
复杂度为O(n)
代码如下：
```class Solution {
public:
    typedef long long ll;
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        long long ans =0;
        int n = nums.size();
        map<int,int> pre;
        int sum = 0;
        pre[0]++;
        for(int i = 0;i<n;++i){
            if(nums[i] % modulo == k){
                sum++;
            }
            ans += pre[(sum - k + modulo)%modulo];
            pre[sum%modulo]++;
        }
        return ans;
    }
};
```


第四题：
我们看到路径以后想到LCA。
由于是无根树，所以我们先以0号节点为根
我们先对树求出来LCA（求LCA的过程大致就是倍增法，以f[u][i]表示从u号节点开始条2^i次能到达的节点是哪个，在查询lca的时候，我们需要先跳到同一个深度，然后从大到小去循环看x,y能不能同时跳（如果下一次跳两个值相等，那么就不能跳，因为这时候我们没法保证是不是会跳过），接下来对每个查询求出来lca
然后我们本质上是对于一个查询u,v ， 想要求出来u->v的路径上最多有多少条边边权相同。
我们对于每一种边权，求出来以0号节点为根，到达每个节点的前缀和。
复杂度为O(w*n + q * w + qlog(n))
这样最终结果就是：
d1 = depth[u] + depth[v] - depth[lcauv] * 2 ;
d2 = p[u][w] + p[v][w] - p[lcauv]*2;
ans = min(d1 - d2,ans);
这里有一些实现的细节需要注意
1 可以预先处理出来每个查询的LCA
2 可以一遍dfs求出来26种边权的结果（这里比较关键，我因为这一点没有过比赛） 主要是dfs的复杂度理论是O(N),但实际上要大很多，因为最坏情况下（这个树会退化成一条链），我们需要压1e4次的栈，那么这个时候复杂度会非常非常高。


```class Solution {
public:
    typedef pair<int,int> pii;
    const static int T = 13;
    const static int N = 1e4 + 10;
    int f[N][T+1];
    int p[N];
    int depth[N];
    vector<pii> adj[N];
    void dfs(int u, int fa, int cw, int lastw){
        p[u] = 0;
        p[u] = (fa == -1 ? 0 : p[fa]) + (lastw == cw);
        for(auto [v,dist]: adj[u]) {
            if(v == fa) continue;
            dfs(v,u,cw,dist);
        }
    }
    void build(int u, int fa, int dep){
        f[u][0] = fa;
        depth[u] = dep;
        for(int i = 1;i<=T;++i) {
            if(f[u][i-1] != -1)
                f[u][i] = f[f[u][i-1]][i-1];
        }
        for(auto [v,dist]: adj[u]) {
            if(v == fa) continue;
            build(v,u, dep+1);
        }
    }
    void bfs(int root){
        queue<int> q;
        q.push(root);
        
        for(int i = 0;i<N;++i)depth[i] = 1e9;
        depth[root] = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto [v,dist]: adj[u]) {
                if(depth[v] > depth[u] + 1){
                    depth[v] = depth[u] + 1;
                    f[v][0] = u;
                    for(int k = 1;k<=T;++k) // 从小到大{
                        if(f[v][k-1] != -1)
                            f[v][k] = f[f[v][k-1]][k-1];
                    
                    q.push(v);
                }
            }
        }
    }


    int lca(int x, int y) {
        if(depth[x] > depth[y]) swap(x,y);
        for (int i = T; i >= 0; i--)
        {
            if (f[y][i] != -1 && depth[f[y][i]] >= depth[x])
                y = f[y][i];
        }
        if (x == y)
            return x;
        for (int i = T; i >= 0; i--)
            if (f[x][i] != -1 && f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    void init(int n) {
        memset(f,-1,sizeof(f));
    }
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        int q = queries.size();
        vector<int> ans(q, 1e9);
        init(n);
        set<int> s;
        
        for(auto e: edges){
            adj[e[0]].push_back({e[1],e[2]});
            adj[e[1]].push_back({e[0],e[2]});
            s.insert(e[2]);
        }
        vector<int> mws;
        for(auto x: s) mws.push_back(x);
        // build(0,-1,0);
        bfs(0);
        dfs(0,-1,0,-1);
        vector<int> lcaq(q,0);
        for(int i = 0;i<q;++i)
            lcaq[i] = lca(queries[i][0], queries[i][1]);
        
        for(int j = 0;j<q;++j) {
            auto qr = queries[j];
            int u = qr[0], v = qr[1];
            int common_lca = lcaq[j];
            int d1 = depth[u] + depth[v] - 2 * depth[common_lca];
            int d2 = p[u] + p[v] - 2 * p[common_lca];
            ans[j] = min(ans[j], d1-d2);
        }            

        
        for(int i = 0;i<mws.size();++i) {
            int mw = mws[i];
            dfs(0,-1,mw,-1);
            for(int j = 0;j<q;++j) {
                auto qr = queries[j];
                int u = qr[0], v = qr[1];
                int common_lca = lcaq[j];
                int d1 = depth[u] + depth[v] - 2 * depth[common_lca];
                int d2 = p[u] + p[v] - 2 * p[common_lca];
                ans[j] = min(ans[j], d1-d2);
            }            

        }
        return ans;
    }
};

```