共计 3978 个字符，预计需要花费 10 分钟才能阅读完成。
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解法一：原地哈希
思路剖析
这种找反复数字的题目还挺常见的。最间接的办法是用哈希表存储数字，遇到新数字判断它是否在哈希表里，若在就阐明反复。
不过题目要求空间复杂度为 $O(1)$。那么就不能用内置哈希表了。
留神到数字范畴是 [1, n]，并且数组长度为 n + 1，因而咱们能够把原数组当成哈希表，通过替换，将数字放到对应下标的地位即可。
例如：遇到了数字 10，那么咱们就去看看下标为 10 的数字是不是 10，是的话阐明数字反复了，否则替换这两个数字。
代码实现
public int search (int n, int[] a) {while(a[0] != a[a[0]]){int temp = a[0];
a[0] = a[a[0]];
a[temp] = temp;
}
return a[0];
}解法二：求和相减
思路剖析
记卧底选的数字是 b，那么 $\sum_{i \in [0,n]} a[i] = \sum_{x \in [1,n]} x + b$。显然求出两个求和的后果，相减即可失去答案。
代码实现
public int search (int n, int[] a) {
int sum = 0;
for(int i = 0; i <= n; i++) sum += a[i];
for(int i = 1; i <= n; i++) sum -= i;
return sum;
}解法三：位运算
思路剖析
剑指 offer 里有一道很经典的题：给一个数组，只有一个数字仅呈现一次，其余数字都呈现了两次，问如何找到这个数字。
那题是利用了异或运算失去答案的。并且咱们晓得异或的后果与奇偶次无关，并不局限于一次两次的限定。
这题是只有一个数字呈现了两次，其余数字都仅呈现一次。如何与那题关联起来呢？
很简略，就让 1 ～ n 再呈现一次，这样只有一个数字呈现了三次，其余数字都呈现了两次。这样就能够用异或来解决啦。
代码实现
public int search (int n, int[] a) {
int x = 0;
for(int i = 1; i <= n; i++) x ^= i;
for(int i = 0; i <= n; i++) x ^= a[i];
return x;
}B. 父子情深
题目形容
在一颗有 n 个结点且以 1 为根节点树上，起初每个结点的初始权值为 0。
当初有 q 次操作，每次操作抉择将以 $r_i$ 为根节点的子树上的所有结点权值减少 $x_i$。
求 q 次操作后从 1 到 n 每个结点的权值。
输出
第一个参数为 n，1 ≤ n ≤ 100,000
第二个参数为边 $(u_i, v_i)$ 的汇合，其中 $(u_i, v_i)$ 示意结点 $u_i$ 与结点 $v_i$ 之间有一条边，$1 ≤ u_i, v_i ≤ n$
第三个参数为 q，1 ≤ q ≤ 100,000
第四个参数为 q 次询问的 $(r_i,v_i)$ 的汇合，$1≤r_i≤n,0≤∣v_i∣≤1000,000$
返回
从 1 到 n 每个结点的权值。
示例 1
输出
5,[(2,5),(5,3),(5,4),(5,1)],2,[(1, 3), (2, -1)]输入
[3,2,3,3,3]阐明
第一次操作，将以 1 为根节点的子树上的所有结点权值减少 3，此时结点的权值别离为 [3, 3, 3, 3, 3]；第二次操作，将以 2 为根节点的子树上的所有结点权值减少 -1，此时结点的权值别离为 [3, 2, 3, 3, 3]；解法：BFS
思路剖析
本题难点在于：
- 输出中给的边是无向边，如何简便的分辨出父节点与子节点
- 如何在线性复杂度内计算出所有节点的权值
对于第一点，因为是树结构，遍历的时候必定是从根节点往子节点遍历，因而能够用布尔数组 visited 记录拜访过的节点，用列表数组 next记录节点 i 的相邻节点。若 next[i] 中的某节点 node 已拜访，阐明 node 是 i 的父节点。
对于第二点，用数组 ans 保留每个节点的权值：
- 先遍历一次询问汇合 Query, 并仅记录子树根节点 $r_i$ 的权值，不对其子树进行操作。
- 咱们发现，节点 $r_i$ 的最终权值 $ans[r_i] = ans[r_i] + ans[fa(i)]$。$fa(i)$ 是 节点 $r_i$ 的父节点。因而能够通过一次遍历实现权值的计算。
用 Java 的小伙伴们留神，树的遍历通常用 BFS 或 DFS。然而这里的节点是十万个，如果最坏状况下树进化成了单链表，应用 DFS 意味着须要 十万个 栈空间，显然会栈溢出。因而咱们应用 BFS 来进行遍历。
工夫复杂度：$O(n)$
空间复杂度：$O(n)$
代码实现
public long[] solve (int n, Point[] Edge, int q, Point[] Query) {long[] ans = new long[n];
List<Integer>[] next = new List[n];
boolean[] visited = new boolean[n];
for(int i = 0; i < n; i++) next[i] = new LinkedList<Integer>();
for(Point p: Edge){next[p.x - 1].add(p.y - 1);
next[p.y - 1].add(p.x - 1);
}
for(Point p: Query) ans[p.x - 1] += p.y;
Queue<Integer> queue = new LinkedList();
queue.offer(0);
while(!queue.isEmpty()){int root = queue.poll();
visited[root] = true;
for(Integer node: next[root]){if(visited[node]) continue;
ans[node] += ans[root];
queue.offer(node);
}
}
return ans;
}C. 旋转跳跃
题目形容
牛牛有一个长为 n 的排列 p，与 m 对 $(x_i,y_i)$.
每对 $(x_i,y_i)$ 示意能够将 $p_{x_i}$ 的值与 $p_{y_i}$ 的值调换。
m 对 $(x_i,y_i)$ 的应用程序与次数不限。
牛牛想晓得，任意次操作之后他能失去的字典序最小的排列是什么
字典序定义：对于数字 1、2、3……n 的排列，不同排列的先后关系是从左到右一一比拟对应的数字的先后来决定的。例如对于 5 个数字的排列 12354 和 12345，排列 12345 在前，排列 12354 在后。依照这样的规定，5 个数字的所有的排列中最后面的是 12345，最初面的是 54321。(来自百度百科)
输出
第一个参数为 n，1 ≤ n ≤ 100,000
第二个参数为 m，1 ≤ m ≤ 100,000
第三个参数为初始排列 p，$1 ≤p_i≤n$
第四个参数为 m 对 $(x_i,y_i)$，$1≤x_i,y_i≤n,x_i≠y_i$
返回
字典序最小的排列
示例 1
输出
5,3,[5,2,3,4,1],[(2,4),(1,4),(3,4)]输入
[2,3,4,5,1]阐明
1. 替换 (3, 4), 替换后的序列为：5, 2, 4, 3, 1
2. 替换 (2, 4), 替换后的序列为：5, 3, 4, 2, 1
3. 替换 (1, 4), 替换后的序列为：2, 3, 4, 5, 1解法：并查集
思路剖析
把下标看作图中的节点，$(x_i,y_i)$ 示意节点 $p_{x_i}$ 和 $p_{y_i}$ 间接相连。因为 m 对 $(x_i,y_i)$ 的应用程序与次数不限，因而同一连通重量中的节点能够任意排列。
例如：对原排列 a, b, c, 给定 (a, b), (b, c)，我能够排列成 b, a, c(仅用到 (a, b))，也能够排列成 a, c, b(仅用到 (b, c))。
显然应用并查集能够不便的失去所有的连通重量。之后对每一个连通重量外部进行排序，小的值放在小的下标上。
工夫复杂度：$O(nlogn)$.
空间复杂度：$O(n)$.
代码实现
class Solution {public int[] solve (int n, int m, int[] perm, Point[] Pair) {int[] ans = new int[n];
Union un = new Union(n);
for(Point p: Pair) un.union(p.x - 1, p.y - 1);
Map<Integer, Queue<Integer>> valueMap = new HashMap();
for(int i = 0; i < n; i++){int fa = un.find(i);
if(!valueMap.containsKey(fa)) valueMap.put(fa, new PriorityQueue());
valueMap.get(fa).add(perm[i]);
}
for(int i = 0; i < n; i++){Queue<Integer> valueSet = valueMap.get(un.find(i));
ans[i] = valueSet.poll();}
return ans;
}
}
class Union{private int[] parent;
public Union(int size){parent = new int[size];
for(int i = 0; i < size; i++) parent[i] = i;
}
public int find(int x){if(x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y){parent[find(x)] = find(y);
}
}写在最初
大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请动动小手指点个赞????。你的反对是我创作路上的最大能源。谢谢大家！
也欢送来公众号【往西汪】找我游玩～
