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;
}
} 第二题我怎么也跑不出来...
）。