顺丰科技-Java笔试编程题-均ac
第一题：并查集
总共有m种语言，我们的并查集数组parent就是根据语言数来建立的。
对于没有任何人用过的语言，是不需要考虑的。
对于某一个人，如果其会用2种及以上的语言，那么这些语言就可以用并查集的unionTwo操作。
最后，我们的结果应该是：
对于不会任何语言的人，其至少需要学一门语言。
如果我们的并查集得到的父亲数量不为0，那么需要加上该数量减1的值。
import java.util.*;
public class Main {
private static int n; //人数
private static int m; //语言数
private static int k; //已知的信息数
private static int[] parent; //并查集
private static int[] peopleToLanguage;
private static Map<Integer, List<Integer>> peopleToLanguageMap = new HashMap<>(); //根据人将语言分群
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
k = scanner.nextInt();
peopleToLanguage = new int[n];
Arrays.fill(peopleToLanguage, -1);
parent = new int[m];
for (int i = 0; i < parent.length; i++) {
parent[i] = i; //每一种语言单独一个集合
}
boolean[] show = new boolean[m];
for (int i = 0; i < k; i++) {
int people = scanner.nextInt();
int language = scanner.nextInt() - 1;
peopleToLanguage[people - 1] = language;
if (peopleToLanguageMap.containsKey(people - 1)) {
peopleToLanguageMap.get(people - 1).add(language);
} else {
List<Integer> list = new ArrayList<>();
list.add(language);
peopleToLanguageMap.put(people - 1, list);
}
show[language] = true;
}
int result = 0;
for (int i = 0; i < peopleToLanguage.length; i++) {
if (peopleToLanguage[i] == -1) { //不会任何语言的人，肯定需要学习一种语言
result++;
}
}
for (List<Integer> list : peopleToLanguageMap.values()) {
for (int i = 0; i < list.size() - 1; i++) {
unionTwo(list.get(i), list.get(i + 1));
}
}
Set<Integer> parentSet = new HashSet<>();
for (int i = 0; i < parent.length; i++) {
if (show[i]) {
parentSet.add(findParent(i));
}
}
if (parentSet.size() != 0) {
result += parentSet.size() - 1;
}
System.out.print(result);
}
private static int findParent(int x) {
int a = x;
while (x != parent[x]) {
x = parent[x];
}
while (a != parent[x]) {
int z = a;
a = parent[a];
parent[z] = x;
}
return x;
}
private static void unionTwo(int a, int b) {
int aParent = findParent(a), bParent = findParent(b);
if (aParent != bParent) {
parent[aParent] = bParent;
}
}
} 第二题：最长非下降子序列
先来看经典的最长上升子序列问题：LeetCode——300。
本题的特殊点在于子序列中的数可以相等，没关系，自定义一个Point类，先比较数，再比较索引，复用最长上升子序列的代码即可。
import java.util.Scanner;
public class Main {
private static class Point implements Comparable {
int num;
int index;
Point(int num, int index) {
this.num = num;
this.index = index;
}
public int compareTo(Object o) {
Point p = (Point) o;
if (p.num == this.num) {
return this.index - p.index;
}
return this.num - p.num;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int num = scanner.nextInt();
points[i] = new Point(num, i);
}
System.out.print(maxLengthOfRisingSubArray(points));
}
private static int maxLengthOfRisingSubArray(Point[] nums) {
int n = nums.length;
Point[] array = new Point[n];
int index = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
array[index++] = nums[i];
} else {
int ceilIndex = ceil(array, index, nums[i]);
if (ceilIndex == index) {
array[index++] = nums[i];
} else if (array[ceilIndex].compareTo(nums[i]) > 0) {
array[ceilIndex] = nums[i];
}
}
}
return index;
}
private static int ceil(Point[] array, int index, Point target) {
int left = 0, right = index;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (array[mid].compareTo(target) <= 0) {
left = mid + 1;
} else {
right = mid;
}
}
if (left - 1 >= 0 && array[left - 1].compareTo(target) == 0) {
return left - 1;
}
return left;
}
} 
