2019年CVTE秋招提前批Web后台开发编程题

深藏阁楼爱情的钟 2022-05-18 07:38 172阅读 0赞

1、CVTE最近组织了一场趣味知识竞赛，由于场地大小，参赛者被分到两个场地分别进行比赛，活动结束后，组织者小明却犯愁了，两个场地参赛者是分开进行排名的，现在需要把这两组有序的分数排名合并成一个总的排名表，于是小明求助于WEB的同时小张编写一个排名算法实现。假如你是小张，你会如何设计这个算法。

样例：

两组的分数排名分别为：\[99, 92, 87, 80\] \[98, 90, 82\]

汇总得到的排名结果：\[99, 98, 92, 90, 87, 82, 80\]

**思路分析:**

1、合并两个有序数组，注意此处为有序，那么就应该充分利用有序的特点，按顺序比较数组元素，使用下标控制比较元素的位置，直至某一个数据元素全部加入结果集；此时只需要将未遍历完的数组元素全部加入结果集。

2、如果将数组转换为list，使用Collections提供的sort方法进行排序，此时虽然可以完成相关的功能，但效率毕竟不高。

下面用上述两种思路实现相关代码：

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * 
     * @author LXH
     *
     */
    public class Merge {
    	/**
    	 * @param ary1 有序子数组1
    	 * @param ary2 有序子数组2
    	 * @return 合并之后的数组
    	 */
    	public static int[] mergeAnother(int[] array1, int[] array2) {
    		long begin = System.currentTimeMillis();
    		
    		int[] result = new int[array1.length + array2.length];
    		
    		int i = 0;//子数组1的下标
    		int j = 0;//子数组2的下标
    		int k = 0;//合并数组的下标
    		
    		//通过while循环先将一个子数组给全部放入新数组中
    		while(i < array1.length && j < array2.length) {
    			//通过这个if判断将有序数组从大到小或从小到大排序
    			if(array1[i] > array2[j]) {
    				result[k++] = array1[i];
    				i++;
    			} else {
    				result[k++] = array2[j];
    				j++;
    			}
    		}
    		
    		//根据下标将剩余部分的数组按照顺序依次复制到新数组中
    		while(i < array1.length) {
    			result[k++] = array1[i++];
    		}
    		while(j < array2.length) {
    			result[k++] = array2[j++];
    		}
    		long end = System.currentTimeMillis();
    		System.out.println("使用while循环耗时：" + (end-begin) + " ms");
     
    		return result;
    	}
    
    	public static int[] merge(int[] A, int[] B) {
    		long begin = System.currentTimeMillis();
    		List<Integer> list = new ArrayList<>();
    		int[] result = new int[A.length + B.length];
    		for(int i = 0; i < A.length; i++) {
    			list.add(A[i]);
    		}
    		for(int i = 0; i < B.length; i++) {
    			list.add(B[i]);
    		}
    		Collections.sort(list);
    		for(int i = list.size(), index = 0; i > 0; i--) {
    			result[index++] = list.get(i-1);
    		}
    		long end = System.currentTimeMillis();
    		System.out.println("使用Collections.sort耗时：" + (end-begin) + " ms");
    		
    		return result;
    	}
    	
    	public static void main(String[] args) {
    		int[] ary1 = {99, 92, 87, 80};
    		int[] ary2 = {98, 90, 82};
    		int[] result = merge(ary1, ary2);
    		for(int i = 0; i < result.length; i++) {
    			System.out.println(result[i]);
    		}
    		result = mergeAnother(ary1, ary2);
    		for(int i = 0; i < result.length; i++) {
    			System.out.println(result[i]);
    		}
    	}
    }

运行结果如下：

![70][]

可以看到，使用while循环的方法效率确实比Collections的方法效率高。

2、CVTE某后台项目组需要设计一个ID生成器，每次生成一个与之前不重复的，长度为4的字符串，该字符串是由字符0—9、a—z、A—Z组成。现给定一个用于返回累计生成过的ID总数的方法getTotal()，试编程实现ID生成方法generate()。

import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    
    public class Generator {
    	private static long count;
    	
    	private static final String s = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    	private static final int length = s.length();
    	private static Random random;
    	private static List<String> codeList;
    	
    	static {
    		random = new Random();
    		codeList = new ArrayList<>();
    	}
    	
    	public static String generate() {
    		boolean has = false;
    		StringBuffer buffer = new StringBuffer();
    		
    		while(!has) {
    			buffer.setLength(0);
    			for(int i = 0; i < 4; i++) {
    				int index = random.nextInt(length);
    				buffer.append(s.charAt(index));
    			}
    			if(!codeList.contains(buffer.toString())) {
    				has = true;
    				synchronized (Generator.class) {
    					count++;
    				}
    				codeList.add(buffer.toString());
    			}
    		}
    		
    		return buffer.toString();
    	}
    	
    	// 该方法用于返回累计生成过的ID总数（每次生成会自动更新生成过的ID总数）
    	public static long getTotal() {
    		return count;
    	}
    	
    	public static void main(String[] args) {
    		for(int i = 0; i < 100; i++) {
    			System.out.println(generate());
    		}
    		System.out.println(getTotal());
    	}
    }

运行结果：

![70 1][]

[70]: /images/20220518/41d7cb9ec8ae43d3a30a7704dbfdeae4.png
[70 1]: /images/20220518/9c30b65c11144999942dc9072174b8e4.png