携程4月1日笔试编程题部分代码
题目忘了拍了。。。大家找一找网上应该有的
第一题暴力O(N^2)超时，只过了40%，蹲一波大佬们的AC代码。
第二题二维dp过了88%，显示，WA不知道哪里有问题，代码如下：
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
int m = Integer.parseInt(sc.nextLine());
int p = Integer.parseInt(sc.nextLine());
Set<Integer> birth = new HashSet<>();
for(int i = 0;i < p;i++){
birth.add(Integer.parseInt(sc.nextLine()));
}
int x = Integer.parseInt(sc.nextLine());
int[][] dp = new int[x + 1][m + 1];
dp[0][0] = n;
for(int i = 1;i <= x;i++){
if(dp[i][m] > 0){
dp[i][m] -= dp[i - m - 1][0];
}
for(int j = 1;j <= m;j++){
dp[i][j] += dp[i - 1][j - 1];
if(birth.contains(j)) {
dp[i][0] += dp[i][j];
}
}
}
int res = 0;
for(int i = 0;i <= m;i++){
res += dp[x][i];
}
System.out.println(res);
}
} 第三题编辑距离问题，牛客有原题，本来以为会很复杂，结果直接遍历字典就AC了。。。 public class Main {
public static void main(String[] args){
String[] d = {"surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"};
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str = sc.nextLine();
boolean flag = true;
for(String s : d){
if(change(str,s) <= 2){
System.out.println(s);
flag = false;
break;
}
}
if(flag){
System.out.println("null");
}
}
}
private static int change(String s1,String s2){
int[][] dp = new int[s1.length()][s2.length()];
for(int i = 0;i < s1.length();i++){
dp[i][0] = i;
}
for(int i = 0;i < s2.length();i++){
dp[0][i] = i;
}
for(int i = 1;i < s1.length();i++){
for(int j = 1;j < s2.length();j++){
dp[i][j] = Math.min(dp[i - 1][j] + 1,
Math.min(dp[i][j - 1] + 1,
dp[i - 1][j - 1] + (s1.charAt(i) == s2.charAt(j) ? 0 : 1)));
}
}
return dp[s1.length() - 1][s2.length() - 1];
}
} 感觉我就这水平了，希望有个面试吧
