周赛小结：leetcode第324场周赛

这次后两题都没做出来

这次其实每道题都有思路，但是因为没有刻意的训练过这方面的题目，导致在代码实现的时候一头雾水

这次倒着来分析：

第四题

提示：

2 <= n <= 30
m == queries.length
1 <= m <= 105
queries[i].length == 2
1 <= ai, bi <= 2n - 1
ai != bi

这道题可以说算是模板题了，在做的时候是有思路的，也知道实际上就是求公共祖先

这样一道模板题，大概在暑假的时候看y总直播有写过这类题（在这里不知道该夸自己记性好还是不好。。）

看了一眼第一名做的题，瞬间就想起来了。。当时根本就没有整理

c++
class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& qs) {
        vector<int> ans;
        for(auto& q : qs){
            int u = q[0], v = q[1];
            int res = 1;
            while(u != v){
                if(u < v) swap(u, v);
                u /= 2;
                res ++;
            }
            ans.push_back(res);
        }
        return ans;
    }
};

第三题

提示：

3 <= n <= 105
2 <= edges.length <= 105
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
图中不会有重边

做题的时候想的是染色体二分问题，因为没有看到“最多加两条边的条件”！

加上这个条件以后，这个题目就变成了分类讨论的问题！

图论，分类讨论)O(n+m)O(n+m)

从图论常识中得知，奇度数点的个数一定是偶数。

如果原图奇度数的点的个数为 0，则直接返回成功。
如果原图奇度数的点的个数大于 4 个，则直接返回失败，因为两条边肯定无法全部将其修改为偶度数。
如果原图奇度数的点的个数为 2，则以下两种情况需要满足一种：
如果奇度数的两个点之间没有边，则直接在其之间加一条边解决。
如果奇度数的两个点之间已经存在了一条边，则寻找另外一个点，满足与这两个点之间都不存在边。
如果原图奇度数的点的个数为 44，设为 x0,x1,x2,x3x0,x1,x2,x3，则以下三种情况需要满足一种：

时间复杂度遍历图一遍，故时间复杂度为 O(n+m)O(n+m)。空间复杂度需要 O(n+m)O(n+m) 的额外空间存储图和度数数组。

c++
typedef long long LL;
int d[1000010];

class Solution {
public:
    
    LL get(int a, int b){
        if(a > b) swap(a, b);
        LL ans = 1000000LL * b + a;
        return ans;
    }
    
    bool isPossible(int n, vector<vector<int>>& qs) {
        memset(d, 0, sizeof d);
        unordered_set<LL> hush;
        vector<int> ans;
        for(auto& q : qs){
            d[q[0]] ++;
            d[q[1]] ++;
            hush.insert(get(q[0], q[1]));
        }
        vector<int> p;
        for(int i = 1; i <= n; i ++){
            if(d[i] % 2) p.push_back(i);
        }
        if(p.size() == 0) return true;
        else if(p.size() == 2){
            int a = p[0], b = p[1];
            if(!hush.count(get(a, b))) return true;
            for(int i = 1; i <= n; i ++){
                if(i != a && i != b && !hush.count(get(i, a)) && !hush.count(get(i, b))) return true;
            }
        }else if(p.size() == 4){
            for(int i = 0; i < 24; i ++){
                int a = p[0], b = p[1], c = p[2], d = p[3];
                if(!hush.count(get(a, b)) && !hush.count(get(c, d))) return true;
                next_permutation(p.begin(), p.end());
            }
        }
        return false;
    }
};

技巧：

next_permutation 的使用
手写哈希函数
图论的分类讨论思路

第二题

简单的模拟题

提示：

2 <= n <= 105

暴力枚举即可，这里复习一下有关于质数的内容

c++
class Solution {
public:

    int trans(int n){
        int i = 2, sum = 0;
        while(i * i <= n){
            if(n % i == 0){
                sum += i;
                n /= i;
            }else{
                i ++;
            }
        }
        if(n != 1) sum += n;
        return sum;
    }

    int smallestValue(int n) {
        int nxt = trans(n);
        while(nxt < n){
            n = nxt;
            nxt = trans(n);
        } 
        return n;
    }
};

第一题

记住字符串去重过程：

c++
string s;
sort(s.begin(), s.end());
s.erase(unique(s.beigin(),s.end()), s.end());

总结

认真看题，认真看题！！！！！！
复习之前见过的模板
哈希函数的使用
多见题