携程笔试三道编程题

第一题（AC）电话接听最少人员

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.nextLine();

		int[] arr = new int[n];
		int[] dep = new int[n];
		for (int i = 0; i < n; i++) {
			String line = scanner.nextLine();
			String[] sa = line.split(",");
			arr[i] = Integer.parseInt(sa[0]);
			dep[i] = Integer.parseInt(sa[1]);
		}

		int result = find(arr, dep, n);

		System.out.println(result);
		scanner.close();
	}
	
	static int find(int arr[], int dep[], int n) {
		Arrays.sort(arr);
		Arrays.sort(dep);

		int result = 0;
		int need = 1;

		int i = 1;
		int j = 0;

		while (i < arr.length && j < dep.length) {
			if(arr[i] < dep[j]) {
				need += 1;
				i++;
				if(need > result) {
					result = need;
				}
			} else {
				need -= 1;
				j++;
			}
		}

		return result;
	}

}

第二题（AC88%）海豚数量

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.nextLine();

		int m = scanner.nextInt(); // life time
		scanner.nextLine();
		
		int p = scanner.nextInt();
		scanner.nextLine();
		
		int[] birth = new int[p];
		for(int i=0; i<p;i++) {
			birth[i] = scanner.nextInt();
			scanner.nextLine();
		}
		
		int x = scanner.nextInt();
		
		int[] ages = new int[m+1];
		ages[0] = 1;
		
		for(int k=0; k<x; k++) {
			for(int i=m; i>0; i--) {
				ages[i] = ages[i-1];
			}
			ages[0] = 0;
			for(int bir : birth) {
				ages[0] = ages[0] + ages[bir];
			}
		}
		
		int res = 0;
		for(int i=0; i<=m; i++) {
			res += ages[i];
		}
		res = res * n;

		System.out.println(res);
		scanner.close();
	}
	
}

第三题（AC）字符串校正

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		String[] corrects = {"surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"};
		
		while(scanner.hasNextLine()) {
			String word = scanner.nextLine();
			if(word == null || word.length() == 0) {
				break;
			}
			
			boolean hasWord = false;
			for(String correct : corrects) {
				if(correctFunc(word, correct)) {
					System.out.println(correct);
					hasWord = true;
					break;
				}
			}
			
			if(!hasWord) {
				System.out.println("null");
			}
		}
		
		scanner.close();
	}

	private static boolean correctFunc(String word, String correct) {
		int line = word.length();
		int col = correct.length();
		
		int[][] dp = new int[line][col];
		dp[0][0] = word.charAt(0) == correct.charAt(0) ? 0 : 1;
		String word0 = String.valueOf(word.charAt(0));
		for(int i=1; i<col; i++) {
			if(word.charAt(0) == correct.charAt(i)) {
				if(correct.substring(0, i).contains(word0)) {
					dp[0][i] = dp[0][i-1] + 1;
				} else {
					dp[0][i] = dp[0][i-1];
				}
			} else {
				dp[0][i] = dp[0][i-1] + 1;
			}
		}
		String correct0 = String.valueOf(correct.charAt(0));
		for(int i=1; i<line; i++) {
			if(correct.charAt(0) == word.charAt(i)) {
				if(word.substring(0, i).contains(correct0)) {
					dp[i][0] = dp[i-1][0] + 1;
				} else {
					dp[i][0] = dp[i-1][0];
				}
			} else {
				dp[i][0] = dp[i-1][0] + 1;
			}
		}
		
		for(int i=1; i<line; i++) {
			for(int j=1; j<col; j++) {
				int tmp = Integer.MAX_VALUE;
				if(word.charAt(i) == correct.charAt(j)) {
					tmp = dp[i-1][j-1];
				} else {
					tmp = dp[i-1][j-1] + 1;
				}
				dp[i][j] = Math.min(tmp, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
			}
		}
		
		if(dp[line-1][col-1] <= 2) {
			return true;
		}
		
		return false;
	}

}

#携程##笔试题目#