计算字符串的编辑距离_星际密码

举报
bug郭 发表于 2022/08/27 00:04:29 2022/08/27
【摘要】 计算字符串的编辑距离计算字符串的编辑距离import java.util.*;public class Main{ public static int distancefun(String str1,String str2){ int row = str1.length(); int col = str2.length(); int[][] ...

计算字符串的编辑距离

计算字符串的编辑距离

image-20220504164447459

image-20220505220927901

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);
    }
}

星际密码

星际密码

image-20220513160622818

//找规律!
当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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。