素数的个数
给出一个包含n个正整数的数组a，把a[i]拆分为若干个和为a[i]的素数，求拆分后最多能有多少个素数。
第一行数据为n，表示数组长度，第二行为n个元素。
输入
3
1 1 1
输出
0 1不可拆分
输入
1 3 5 7
6 1为0个，3为1个，5为（2,3），7为（2,2,3）
分析：
这道题比较简单，当a[i]>1的时候，素数的个数为a[i]/2。但是要注意原题目的数据范围比较大，最后的总个数可能超出Int上限需要用Long来存，具体代码如下：
1public static void main(String[] args){ 2 Scanner scan = new Scanner(System.in); 3 int n = scan.nextInt(); 4 int[] a = new int[n]; 5 for(int i=0;i<n;i++){ 6 a[i] = scan.nextInt(); 7 } 8 System.out.println(chaifen(a)); 9} 10public static long chaifen(int[] a){ 11 long count = 0; 12 for(int i=0;i<a.length;i++){ 13 if(a[i] == 1) 14 continue; 15 else{ 16 count+=a[i]/2; 17 } 18 } 19 return count; 20}
字典序最小的排列
给出一个长度为m的序列T，求一个长度为n且字典序最小的排列S，要求不改变原序列中元素的相对位置。
第一行输入两个正整数n和m
第二行输入m个数，表示序列
5 3
2 1 5
输出
2 1 3 4 5
分析：这道题我采用归并排序的思路，首先枚举出T中多出来的元素，比如题目中的T相比S就多出来了3 4。
然后对两个数组2 1 5和3 4进行归并排序，具体代码如下：
1public static void main(String[] args){ 2 Scanner scan = new Scanner(System.in); 3 int n = scan.nextInt(); 4 int m = scan.nextInt(); 5 int[] s = new int[m]; 6 for(int i=0;i<m;i++){ 7 s[i] = scan.nextInt(); 8 } 9 int[] t =a(s,n); 10 for(int i=0;i<t.length-1;i++){ 11 System.out.print(t[i]); 12 System.out.print(" "); 13 } 14 System.out.print(t[n-1]); 15 System.out.print("\n"); 16} 17public static int[] a(int[] s,int n){ 18 int[] t = new int[n]; 19 int m = s.length; 20 int[] tmp = new int[n-m]; 21 HashSet<Integer> set = new HashSet<>(); 22 for(int i:s){ 23 set.add(i); 24 } 25 int index=1; 26 for(int i=0;i<tmp.length;i++){ 27 while(set.contains(index)) 28 index++; 29 tmp[i] = index++; 30 } 31 int index1 = 0; 32 int index2 = 0; 33 for(int i=0;i<t.length;i++){ 34 if(index1 <m && index2<n-m){ 35 if(s[index1] <= tmp[index2]){ 36 t[i] = s[index1++]; 37 }else{ 38 t[i] = tmp[index2++]; 39 } 40 }else if(index1<m){ 41 t[i] = s[index1++]; 42 }else{ 43 t[i] = tmp[index2++]; 44 } 45 } 46 return t; 47}
丢弃最少物品
给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。
输入
输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。
1
5
30 60 5 15 30
输出
20 丢弃5和15，把60分配给第一个人，2个30分配给第二个人。
分析：这道题我一开始想用背包做，但是不知道怎么计算背包的容量，所以就想着先用回溯过几个用例再说，结果没想到直接过了。
不知道有没有大神能够提供最优解。
1static int res; 2public static void main(String[] args) { 3 Scanner scan = new Scanner(System.in); 4 int t = scan.nextInt(); 5 while(t-->0){ 6 res = Integer.MAX_VALUE; 7 int n = scan.nextInt(); 8 int[] item = new int[n]; 9 for(int i =0;i<n;i++) 10 item[i] = scan.nextInt(); 11 a3(item, 0,0,0, 0); 12 System.out.println(res); 13 } 14} 15public static void a3(int[] item,int index,int x,int y,int r){ 16 if(index == item.length){ 17 if(x == y) 18 res = Math.min(r,res); 19 return; 20 } 21 a3(item,index+1,x+item[index],y,r) 22 a3(item,index+1,x,y+item[index],r); 23 a3(item,index+1,x,y,r+item[index]); 24}
差距最小的生成树
给出一个无向图，一共有n个点，m条边，每条边的权值为v。
求一个生成树，使得图保持联通的同时，权值的最大值和最小值之差最小。
输入
第一行为n和m，表示点的个数和边的条数
后面为m行，表示m条边的两个顶点和其权值
3 5
1 2 10
1 3 5
3 1 12
2 3 19
1 2 74
输出
2 选择边1和3，最小差值为12-10
分析：不会。
牛客大佬找到了原题，给大家分享一下：
https://blog.csdn.net/hjd_love_zzt/article/details/14525117
后记
总的来说这次运气比较好，A了3题，最后一题确实不会做，3题应该能进面试了吧，接下来好好准备阿里和雷火的面试吧。
