A、找卧底

题目描述
牛牛今天和大家玩了一个新游戏，除了牛牛以外还有n个人参加游戏，现在这n个人中的每个人从[1,n]中选择一个数字，保证选出的数字均不重复。牛牛作为第n+1个人，充当卧底的角色，要求卧底从1到n中选择一个数字，现在将n+1个数字重新打乱顺序，请找出卧底选择的数字是多少。
备注:
其中1<=n<=100000。
要求时间复杂度为O(n)，额外空间复杂度为O(1)

示例1
输入
4,[1,2,1,4,3]
输出
1

解题方法

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int cnt[100005];
    int search(int n, vector<int>& a) {
        // write code here
        int ans = 0;
        for(auto it:a)    ans^=it;
        for(int i=1;i<=n;++i)    ans^=i;
        return ans;
    }
};

B、父子情深

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
public:
    /**
     * 从 1 到 n 每个结点的权值。
     * @param n int整型 
     * @param Edge Point类vector (u, v) 集合
     * @param q int整型 
     * @param Query Point类vector Point.x 为题中 r, Point.y为题中 v
     * @return long长整型vector
     */
    int fa[100005];
    vector<long> dp;
    vector<int> e[100005];

    void dfs2(int x, int y) {
        if(x)    dp[x] += dp[y];
        for (auto it : e[x]) {
            if (it == y)    continue;
        dfs2(it, x);
    }
}

    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        // write code here
        for(int i=0;i<100005;++i)    e[i].clear();
        for (auto it : Edge) {
            e[it.x-1].push_back(it.y-1);
            e[it.y-1].push_back(it.x-1);
        }
        dp.clear();
        for(int i=0;i<n;++i)    dp.push_back(0);
        for (auto it : Query)
            dp[it.x-1] += it.y;
        dfs2(0, -1);
        return dp;
    }
};

C、旋转跳跃

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型
     * @param m int整型
     * @param perm int整型vector
     * @param Pair Point类vector
     * @return int整型vector
     */
    int fa[100007], a[100007];
    vector<int> e[100007];
    int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        // write code here
        for (int i = 1; i <= n; ++i)    a[i] = perm[i-1], fa[i] = i;
        for (auto it : Pair)    fa[find(it.x)] = find(it.y);
        for (int i = 1; i <= n; ++i)    e[find(i)].push_back(i);
        for (int i = 1; i <= n; ++i) {
            vector<int>    tmp;
            for (auto it : e[i])    tmp.push_back(a[it]);//第i个人掌管的点现在的权值放进去
            sort(tmp.begin(), tmp.end());//排序
            for (int j = 0; j < e[i].size(); ++j)    a[e[i][j]] = tmp[j];//更新
        }
        vector<int> ans;
        for (int i = 1; i <= n; ++i)
            ans.push_back(a[i]);
        return ans;
    }
};