当前位置：首页 > article >正文

Java-02

article 2025/1/10 3:56:56

笔试算法：

41.

回文串

我们称一个字符串为回文串，当且仅当这个串从左往右和从右往左读是一样的。例如，aabbaa、a、abcba 是回文串，而 ab、ba、abc 不是回文串。注意单个字符也算是回文串。

现在，给你一个长度为n的字符串 S，接下来需要将这个串重新排列，组成一个新的字符串 T。

首先，T 一开始为空，之后进行如下操作：从左往右开始，剪切 S 中开头 k 个字符构成的子串。如果该子串是一个回文串，就将其拼接在 T 的前面；否则，将其拼接在 T 的末尾。其中 k 是一个给定的参数。

你需要输出最后 T 是多少。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行两个正整数 n,k (1<= n,k <= 105)，其中 k 是 n 的因子。
第二行输入字符串 S。该字符串仅由小写英文字母组成。

输出描述：

输出一行一个字符串，表示 T。

示例1

输入例子：

12 3
ababaacbaccc

输出例子：

cccababaacba

先进行条件判断，之后是简单的逻辑

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        sc.nextLine();
        String s=sc.nextLine();
        if(k==1){
            String result=new StringBuilder(s).reverse().toString();
            System.out.println(result);
        }
        else if(n<=k){
            System.out.println(s);
        }
        else{
            String result="";
            if(n%k==0){
                for(int i=0;i<n/k;i++){
                    String smallString=s.substring(i*k,i*k+k);
                    String smallReverse=new StringBuilder(smallString).reverse().toString();
                    if(smallReverse.equals(smallString)){
                        result=smallString+result;
                    }else{
                        result=result+smallString;
                    }
                }
            }else{
                for(int i=0;i<n/k;i++){
                    String smallString=s.substring(i*k,i*k+k);
                    String smallReverse=new StringBuilder(smallString).reverse().toString();
                    if(smallReverse.equals(smallString)){
                        result=smallString+result;
                    }else{
                        result=result+smallString;
                    }
                }
                String duo=s.substring(n/k*k,n);
                String duoReverse=new StringBuilder(duo).reverse().toString();
                if(duo.equals(duoReverse)){
                    result=duo+result;
                }else{
                    result=result+duo;
                }
            }
            System.out.println(result);
        }
    }
}