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