计算字符串的编辑距离_星际密码
【摘要】 计算字符串的编辑距离计算字符串的编辑距离import java.util.*;public class Main{ public static int distancefun(String str1,String str2){ int row = str1.length(); int col = str2.length(); int[][] ...
计算字符串的编辑距离
import java.util.*;
public class Main{
public static int distancefun(String str1,String str2){
int row = str1.length();
int col = str2.length();
int[][] dp = new int[row+1][col+1];
//初始状态:f(i,0) = i; f(0,j) = j;
//状态转移: f(i,j) = str[i]==str2[j]? f(i-1,j-1): min(f(i-1,j),f(i,j-1),f(i-1,j-1))+1
//状态定义: f(i,j) str1 前 i 个子串和 str2 前j 个子串的最小编辑距离
//返回结果:f(row,col);
for(int i = 0;i<= row;i++){
dp[i][0] = i;
}
for(int i = 0;i<=col;i++){
dp[0][i] = i;
}
for(int i = 1;i<=row;i++){
for(int j = 1;j<=col;j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
int min = Math.min(dp[i-1][j],dp[i][j-1]);
dp[i][j] = Math.min(dp[i-1][j-1],min) + 1;
}
}
}
return dp[row][col];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int result = distancefun(str1,str2);
System.out.println(result);
}
}
星际密码
//找规律!
当n = 1时
|1 1| 左上角值 = 1
|1 0|
当n = 2时
|1 1|*|1 1|=|2 1| 左上角值 = 2
|1 0| |1 0| |1 1|
当n = 3时
|2 1|*|1 1|=|3 2| 左上角值 = 3
|1 1| |1 0| |2 1|
当n = 4时
|3 2|*|1 1|=|5 3| 左上角值 = 5
|2 1| |1 0| |3 2|
当n = 5时
|5 3|*|1 1|=|8 5| 左上角值 = 8
|3 2| |1 0| |5 3|
当n = 6时
左上角值 = 13 ?
//可以知道 这是一组斐波那契数列!
import java.util.*;
public class Main{
public static void main(String[] args){
int[] arr = new int[10001];//我们只需要把 前10000 个斐波那契值保存即可!而这里大于4位就保留后四位,Int类型存储足够
arr[1] = 1;
arr[2] = 2;
for(int i = 3;i < 10001;i++){
arr[i] = arr[i - 1] + arr[i - 2];
arr[i] = arr[i] % 10000;//超过10000 对结果求余!
}
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
StringBuffer sb = new StringBuffer();
int n = sc.nextInt();
for(int i = 0;i < n;i++){
int x = sc.nextInt();
sb.append(String.format("%04d",arr[x]));//格式打印保存到sb中!
}
System.out.println(sb);//打印sb!
}
}
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)