共计 3538 个字符，预计需要花费 9 分钟才能阅读完成。
A. 牛牛爱奇数
题目形容
在牛牛背后放着 n 个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特地想让这些数都变成奇数。
当初牛牛取得了一种能力，他能够执行一种操作：每次选中一个偶数，而后把这些数中与该数相等的数都除以 2，例如当初有一个数组为 [2, 2, 3]，那么牛牛能够执行一次操作，使得这个数组变为 [1, 1, 3]。
牛牛当初想晓得，对于任意的 n 个数，他起码须要操作多少次，使得这些数都变成奇数？
备注:
1 ≤ n ≤ 10^6，代表一个有多少数字
a1, a2, a3 ... an(1 ≤ ai ≤ 10^9)代表数字的大小示例 1
输出
3,[2,2,3]输入
1阐明
只需做一次操作，会将其中的偶数 2 都变成 1，满足了所有的数都是奇数的要求。示例 2
输出
3,[1,3,7]输入
0阐明
不须要做任何操作，因为所有的数本来就是奇数。解法：大顶堆 + 哈希汇合
思路剖析
每次能够让 所有雷同的偶数 变成一半，问起码操作次数。
一次操作所有雷同数，显然要应用哈希汇合进行去重。
而要使得操作次数起码，必然对偶数从大到小进行操作，这样才能够防止对某个偶数进行反复的操作。
想要从大到小操作，显然应用大顶堆保留偶数。每次从堆顶取一个数字进行操作，若失去的新的数字是偶数并且未在哈希汇合中呈现过，就把它再退出大顶堆中。
工夫复杂度：O(max(n, logm))。这里的 m 是最大的偶数。遍历一遍数字须要 O(n)，把偶数全变成奇数须要 O(logm)。
空间复杂度：O(n)。
代码实现
public int solve (int n, int[] a) {Set<Integer> set = new HashSet();
int ans = 0;
for(int i: a)
if((i & 1) == 0) set.add(i);
Queue<Integer> q = new PriorityQueue<Integer>((x,y) -> y - x);
q.addAll(set);
while(!q.isEmpty()) {int num = q.poll() >> 1;
ans++;
if((num & 1) == 0 && !set.contains(num)) q.add(num);
}
return ans;
}B. 牛牛摆放花
题目形容
牛牛有 n 朵须要摆放的花，然而每朵花呢，高度都不一样，牛牛不喜爱相邻的花高度相差太多，这样会影响美感。
所以牛牛提出了一个“俊俏度”的概念，“俊俏度”意思为在一个摆放序列中，相邻花高度差的最大值。而且牛牛是一个完满主义者，所以他心愿:
1. 将这些花摆成首尾相接的圆形
2. 为了好看，他心愿摆放的花“俊俏度”最小
程序应返回：依照这些花排成一个圆的程序，输入在多个摆放花的序列中，最小的“俊俏度”。
备注:
第一个参数为一个整数 n(2 ≤ n ≤ 10^5)，代表花的数量。第二个参数为蕴含 a1, a2, a3 ... an(1 ≤ ai ≤ 10^9) 的数组，代表每朵花的高度。示例 1
输出
5,[2,1,1,3,2]输入
1阐明
能够摆成 1 2 3 2 1 这样的序列，最小的“俊俏度”为 1 示例 2
输出
3,[30,10,20]输入
20阐明
能够摆成 10 30 20 这样的序列，最小的“俊俏度”为 20解法：排序
思路剖析
如果不思考首尾相接的话，要想俊俏度最小，显然摆放序列为升序 / 降序。
当初要求首尾相接，因而首尾的高度差也要小一些，显然 V 型 序列或者 ^ 型 序列满足要求。
故而进行排序，升序 / 降序都能够。这里以升序为例，高度差 = arr[i] – arr[i – 2]。首尾高度差 = arr[1] – arr[0]。
工夫复杂度：O(nlogn)。
空间复杂度：O(1)。
代码实现
public int solve (int n, int[] array) {Arrays.sort(array);
int ans = array[1] - array[0];
for(int i = 2; i < n; i++)
ans = Math.max(ans, array[i] - array[i - 2]);
return ans;
}C. 星球游戏
题目形容
牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下：
游戏地图内共有 n 个星球，共有 m 条隧道连贯这些星球。每条隧道都是双向的，每两个星球间不肯定只有一条隧道。当初牛牛霸占了这 n 个星球中的 p 个星球，牛妹霸占了这 n 个星球中的 q 的星球（每个星球最多只能被一个人霸占）。当初牛牛想晓得他霸占的 p 个星球中任意一个星球，到牛妹霸占的 q 个星球中任意一个星球，这两个星球的最短距离是多少。
备注:
2 ≤ n ≤ 1e5, 0 ≤ m ≤ 2e5, 1 ≤ p ≤ 1e5, 1 ≤ q ≤ 1e5, p + q ≤ n, min(p, q) ≤ 10, 1 ≤ wi ≤ 1e4
相干参数意义如下
niuniu 牛牛霸占的 p 个星球的编号
niumei 牛妹霸占的 q 个星球的编号
path m 条隧道，每条隧道有三个数别离是 ui,vi,wi。ui,vi 别离是隧道的两边星球的编号，wi 是它们之间的间隔
nn int 整型 星球个数 n 示例 1
输出
[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4输入
10阐明
间隔最近的牛牛星和牛妹星是 1 和 4，他们之间的间隔为 10示例 2
输出
[1],[2],[],2输入
-1阐明
所有的牛牛星和牛妹星都不联通，故输入 -1解法：dijkstra 算法
思路剖析
显然这题是单源最短路问题，间接应用 dijkstra 算法可解。
有人可能要问了：“汪汪，牛牛不是霸占了 p 个星球吗，怎么会是单源最短路问题？”
留神到题目中说的是 p 个星球中 任意一个 ，所以法力无边的 本汪 发明了一个超级星球 X，从 X 登程能够瞬移到牛牛的 p 个星球，因而本题就等价于问从星球 X 登程，到牛妹霸占的星球中最近间隔是多少。就这样轻轻松松地变成一个单源最短路问题了。
本汪 默认聪慧博学的小伙伴们都会 dijkstra 算法，在这就不多赘述了。（才不是因为我懒）
如果有小伙伴对 dijkstra 算法还有疑难，能够在下方留言，有需要的话 本汪 就专门出一期 dijkstra 算法的博客。
代码实现
public class Solution {
/**
*
* @param niuniu int 整型一维数组 牛牛霸占的 p 个星球的编号
* @param niumei int 整型一维数组 牛妹霸占的 q 个星球的编号
* @param path int 整型二维数组 m 条隧道，每条隧道有三个数别离是 ui,vi,wi。ui,vi 别离是隧道的两边星球的编号，wi 是它们之间的间隔
* @param nn int 整型 星球个数 n
* @return int 整型
*/
final int INF = 10001;
public int Length (int[] niuniu, int[] niumei, int[][] path, int nn) {List<Pair>[] edges = new List[nn + 1];
int[] dis = new int[nn + 1];
Arrays.fill(dis, INF);
boolean[] vis = new boolean[nn + 1];
for(int i = 0; i <= nn; i++) edges[i] = new ArrayList();
for(int[] edge: path) {edges[edge[0]].add(new Pair(edge[2],edge[1]));
edges[edge[1]].add(new Pair(edge[2],edge[0]));
}
Queue<Pair> q = new PriorityQueue<Pair>((a, b) -> a.d - b.d);
for(int u: niuniu) {dis[u] = 0;
q.add(new Pair(0, u));
}
while(!q.isEmpty()) {Pair p = q.poll();
if(vis[p.v]) continue;
vis[p.v] = true;
for(Pair e: edges[p.v]) {if(dis[e.v] > dis[p.v] + e.d) {dis[e.v] = dis[p.v] + e.d;
q.offer(new Pair(dis[e.v],e.v));
}
}
}
int ans = INF;
for(int u: niumei) ans = Math.min(ans, dis[u]);
return ans == INF ? -1 : ans;
}
}
class Pair{
int d; // 间隔
int v; // 另一个顶点
public Pair(int d, int v) {
this.d = d;
this.v = v;
}
}写在最初
「牛客编程巅峰赛系列题解」也写了八期了，每篇文章都要消耗大量的工夫进行撰写、排版、纠错。但对小伙伴们的帮忙却不大，本汪 也是产生了一丢丢的挫败感。
暂不打算持续更新这个系列的文章了。
新的打算是更新「解题办法系列」的文章。第一期的题目我都想好了：【遇到「最值问题」无脑动静布局？二分法考虑一下呗】。预计一周内更新。
如果小伙伴想理解其余方面的常识，能够在下方评论区留言哦。本汪 会视状况决定是否新开这个系列。
