首页 > 4.1携程技术类笔试
头像
迪迪卫甜筒🏂
编辑于 2020-04-02 08:27
+ 关注

4.1携程技术类笔试

第一题LeetCode253 AC 用两个数组分别记录开始和结束时间,然后遍历开始时间数组。
import java.util.Arrays;
import java.util.Scanner;

public class test1 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			int[][] intervals = new int[n][2];
			for(int i = 0; i < n; i++) {
				String s = sc.next();
                String[] cur = s.split(",");
				intervals[i][0] = Integer.parseInt(cur[0]);
				intervals[i][1] = Integer.parseInt(cur[1]);
			}
			int res = function(intervals);
			System.out.println(res);
		}
	}
	
	public static int function(int[][] intervals) {
		int n = intervals.length;
		int[] start = new int[n];
		int[] end = new int[n];
		for(int i = 0; i < n; i++) {
			start[i] = intervals[i][0];
			end[i] = intervals[i][1];
		}
		Arrays.sort(end);
		int j = 0; //指向结束时间的index
		int res = 0;
		for(int i = 0; i < n; i++) {
			if(start[i] < end[j]) {
				res++;
			}else {
				j++;
			}
		}
		return res;
	}
}
第三题 LeetCode72 AC DP问题 
import java.util.*;

public class test2 {
	
	public static List<String> dict = new ArrayList<>();
	
	static {
		dict.add("surprise");
		dict.add("happy");
		dict.add("ctrip");
		dict.add("wellcome");
		dict.add("student");
		dict.add("system");
		dict.add("program");
		dict.add("editor");
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			String s = sc.next();
			String res = function(s);
			System.out.println(res);
		}
	}
	
	public static String function(String s) {
		int n = s.length();
		for(String word : dict) {
			int m = word.length();
			int[][] dp = new int[n + 1][m + 1];
			for(int i = 0; i < n + 1; i++) {
				dp[i][0] = i;
			}
			for(int i = 0; i < m + 1; i++) {
				dp[0][i] = i;
			}
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(s.charAt(i) == word.charAt(j)) {
						dp[i + 1][j + 1] = dp[i][j];
					}else {
						dp[i + 1][j + 1] = Math.min(dp[i][j + 1] + 1, Math.min(dp[i + 1][j] + 1, dp[i][j] + 1));
					}
				}
			}
			if(dp[n][m] <= 2) {
				return word;
			}
		}
		return null;
	}
}
第二题我怎么也跑不出来...


全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐