查找两个字符串a,b中的最长公共子串_洗牌

查找两个字符串a,b中的最长公共子串

查找两个字符串a,b中的最长公共子串

import java.util.*;
public class Main{
    public static String dphelp(String str1,String str2){
        String result = new String();
        int maxLen = 0;//保存最大长度值!
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        //初始化: 初始化dp的时候已经全部初始化为0了可以不做处理!
       /* for(int i = 0;i< len1;i++){
            dp[i][0] = 0;
        }
        for(int i = 0;i< len2;i++){
            dp[0][i] = 0;
        } */
        //转移方程!
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j<=len2;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j]>maxLen){
                        //更新最大值和结果!
                        maxLen = dp[i][j];
                        //substring(i,j) // [i,i)
                        result = str1.substring(i-maxLen,i);
                    }
                }
            }
        }
        return result;
    }
   public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int len1 = str1.length();
        int len2 = str2.length();
        if(len1>len2){//保证 str1是较短串!
            String tmp = str1;
            str1 = str2;
            str2 = tmp;
        }
        System.out.println(dphelp(str1,str2));
       }
}

相同题目,简化了 只需要返回最大长度即可!!!

公共子串计算

洗牌

洗牌

import java.util.*;
public class Main{
    public static void helpfun(int[] array,int n,int x){
        // int ret = new int[2*n]; error!
        while(x-->0){
            int[] ret = new int[n*2];//保存洗牌结果!
            for(int i = 0;i<n;i++){
                ret[2*i] = array[i];  //左手 i --> 2*i
                ret[2*i+1] = array[i+n]; //右手 i+n --> 2*i+1
            }
            array = ret;//更新洗牌!
            //这里将 ret 的引用给了 array 如果 ret 不重新声明
            //会使这个array和ret在一块数组空间交换,结果错误!
        }
       for(int i = 0;i<2*n-1;i++){
         System.out.print(array[i]+" ");
       }
       System.out.println(array[2*n-1]);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0){
            int n = sc.nextInt();
            int x = sc.nextInt();//洗牌次数!
            int[] array = new int[n*2];
            for(int i = 0;i<2*n;i++){
                array[i] = sc.nextInt();
            }
             helpfun(array,n,x);
        }

    }
}