<mark>第一道题目：</mark>
把两个不相同的字符串变得相同
1修改一个字符,如把a替换为b
2增加一个字符,如把ab变为aeb
3删除一个字符,如把aeb变为ab
比如,对于abcdefg和abcdef两个字符串来说,我们认为可以通过增加和减少个g的方式来达到目的。把每一步操作所需要的次数定义为两个字符串的距离,而这个相似度等于距离+1的倒数。也就是说,“abcdefg"和abcdef的距离为1,相似度为1/2=0.5。然后让写一个算法计算出它们的相似度
输入:
“abcdef”
“abcdefg”
输出:
1/2
public class Main1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = in.nextLine();
String str2 = in.nextLine();
System.out.println(calculateStringDistance(str1,str2));
}
public static String calculateStringDistance(String word1,String word2){
int m = word1.length();
int n = word2.length();
// for(int i =0;i< m;i++){
// if(word1.charAt(i)-'0'>=65 &&word1.charAt(i)-'0'<=90){
// return null;
// }
// }
// for(int i =0;i< n;i++){
// if(word2.charAt(i)-'0'>=65 &&word2.charAt(i)-'0'<=90){
// return null;
// }
// }
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <=m ; i++) {
dp[i][0] = i;
}
for(int j =0;j<=n;j++){
dp[0][j] = j;
}
for (int i = 1; i <=m; i++) {
for(int j =1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else {
dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
}
}
}
String s = String.valueOf(dp[m][n]+1);
if(s =="0"){
return null;
}
return "1"+"/"+s;
}
}
<mark>第二道题目：</mark>
用一维数组存储学号和成绩,并且按照成绩排序
输入描述:
输入第一行包括一个整数N(1=N<=100),代表学生的个数。接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩。
输出描述:
按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来。
如果学生的成绩相同,则按照学号的大小进行从小到大排序。
示例1
3
1 90
2 87
3 92
输出
2 87
1 90
3 92
public class Main2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Student[] str = new Student[n];
for (int i = 0; i < n; i++) {
int p = in.nextInt();
int q = in.nextInt();
Student s = new Student(p,q);
str[i] = s;
}
for (int i = 1; i < n; i++) {
for (int j = i; j >0 ; j--) {
if(str[j].cj < str[j-1].cj){
Student temp = str[j];
str[j] = str[j-1];
str[j-1] = temp;
}else if(str[j].cj==str[j-1].cj){
if(str[j].no <str[j-1].no){
Student temp = str[j];
str[j] =str[j-1];
str[j-1] = temp;
}
}
}
}
for (int i = 0; i < n; i++) {
System.out.println(str[i].no+" "+str[i].cj);
}
}
static class Student{
int no;
int cj;
public Student(int no,int cj){
this.no = no;
this.cj = cj;
}
}
}
原文地址https://mp.weixin.qq.com/s/7szm1KbpnTbUe8Mgk9d5KA
原创面试复习图（点击菜单获取）
京公网安备 11010502036488号