密码截取__牛客网

Java

牛客916838684号

习惯了自己的逻辑，别人的就很难理解下去了

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        char[] ch = str.toCharArray();

        int count =0;

        for (int i = 0; i < ch.length / 2; i++) {
            for (int j = ch.length; j >= ch.length / 2 ; j--) {
                String sub = str.substring(i, j);

                String front = sub.substring(0,sub.length()/2);
                String back = sub.substring((sub.length()+1)/2, sub.length());

                char[] chback = back.toCharArray();
                Arrays.sort(chback);

                if(front.equals(String.valueOf(chback))){
                    // System.out.println("相同");
                    count = Math.max(count, sub.length());
                }

            }
        }
        System.out.println(count);
    }
}

发表于 2025-09-29 17:02:24 回复(0)

Java

我不喝牛奶

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String a = in.nextLine();
        int n = a.length() ;
        int maxLength = 0;
        // 优化的中心扩展法

        //直接切割查找，暴力查找所有子串，复杂度高，效率低，会超时
        /*
        for1 : for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i + j == n - 1) break;
                maxLength = Math.max(dfs(a, i, n - j, maxLength), maxLength);
                if (maxLength == n  ) break for1;//已经是最长的了
            }
        }*/
        System.out.println(longestPalindrome(a));

    }
    //直接分割查找，复杂度大，效率低，会超时
    public  static int  dfs(String str, int start, int end,
                            int maxLength) {
        String s = str.substring(start, end);
        int n = s.length();
        int m = n / 2;
        if (n == 1) return 0;
        if (n % 2 == 0) {
            String s1 = s.substring(0, m );
            String s2 = new StringBuilder(s.substring(m, n )).reverse().toString();
            if (s1.equals(s2)) {
                maxLength = Math.max(n, maxLength);
            }
        } else {
            String s1 = s.substring(0, m);
            String s2 = new StringBuilder(s.substring(m + 1, n )).reverse().toString();
            if (s1.equals(s2)) {
                maxLength = Math.max(n, maxLength);
            }
        }
        return maxLength;
    }

    //优化的中心扩展法,
    public static int longestPalindrome( String s) {
        int n = s.length();
        if (n < 2 ) {
            return n;
        }
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            //奇数长度回文（以i位中心）
            int len1 = expandAroundCenter(s, i, i);
            //偶数长度回文（以i和i+1为中心）
            int len2 = expandAroundCenter(s, i, i + 1);
            maxLength = Math.max(maxLength, Math.max(len1, len2));
        }
        return  maxLength;
    }
    //优化的中心扩展法
    public static int expandAroundCenter(String s, int left, int right) {
        //判断左右是否相等
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt( right)) {
            //从中心向两边扩展
            left--;//向左扩展
            right++;//向右扩展
        }
        // 循环结束时，left和right已经超出回文边界
        // 实际回文长度为 right - left - 1
        return right - left - 1;
    }
}

发表于 2025-06-25 14:48:02 回复(0)

Java

新的旅程a

来一个动态规划版的，时间和空间复杂度都是O(n)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.next();
        int max = 0;
        int[] dp = new int[input.length()]; //当前回文字符串长度
        dp[0] = 1;
        for(int i=1;i<input.length();i++){
            if(i-1-dp[i-1]>=0 &&input.charAt(i)==input.charAt(i-1-dp[i-1])){//在上一个回文字符串的基础上，分别往左右扩大1位
                dp[i] = dp[i-1] + 2; //如：AB->ABA,ABB->ABBA,ABCB->ABCBA
            } else if(input.charAt(i)==input.charAt(i-1)){//当前字符和上一个字符相等时
                //分为是否连续相等。如：ABC->ABCC,ABB->ABBB
                dp[i] = i>=2&&input.charAt(i-1)==input.charAt(i-2)?dp[i-1]+1:2;
            } else if(i>3&&input.charAt(i)==input.charAt(i-2)){//当前字符和i-2个字符相等
                //是否为ABABA->ABABAB这种循环形式的。循环形式的和前一个dp相等，否则为3
                dp[i] = input.charAt(i-1)==input.charAt(i-3)?dp[i-1]:3;
            } else{
                dp[i] = 1;
            }
            max = Math.max(dp[i],max);
        }
        System.out.println(max);
    }
}

发表于 2024-11-04 05:10:28 回复(0)

Java

Ding_Lifeng

Java 动态规划

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            // 动规--确定回文串的最大长度
            String code = in.nextLine();
            int len = code.length();
            if(len == 1)
                System.out.println(1);

            // dp[i][j] - 目标字符串i到j是否为回文串， i>j为false i=j为true
            // 状态转移方程
            // dp[i][j] = dp[i+1][j-1] || charAt(i) == charAt(j) (j-i>1)
            // dp[i][j] = charAt(i) == charAt(j) (j-i=1)
            // 答案-dp[i][j] = true , max(j-i+1)
            boolean[][] dp = new boolean[len][len];
            int maxLen = 1;
            for(int i=0; i<len; i++)  // j=i边界条件
                dp[i][i] = true;

            for(int l=2; l<=len; l++){  // 循环条件为子串长度，子串长度由短至长
                for(int i=0; (i+l-1)<len; i++){
                    int j = i+l-1;
                    if(code.charAt(i)==code.charAt(j)){
                        if(l==2)
                            dp[i][j] = true;
                        else
                            dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] == true)
                        maxLen = Math.max(maxLen,l);
                }
            }
            System.out.println(maxLen);
        }
    }
}

发表于 2024-08-30 14:29:01 回复(0)

Java

牛客317900105号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int len = 0;
            for (int i = 0; i < str.length(); i++) {
                for (int j = str.length() - 1; j > i; j--) {
                    len = Math.max(findStr(str, i, j),len);
                }
            }
            System.out.println(len);
        }
    }

    //此方法用来寻找从小索引到大索引的子串的长度
    public static int findStr(String str, int i, int j) {
        int a = i;
        int b = j;
        boolean is = true;
        while (i < j){
            if (str.charAt(i) == str.charAt(j)){
                i++;
                j--;
            }else {
                is = false;
                break;
            }
        }
        if (is)
            return b - a + 1;
        else
            return 0;
    }
}

发表于 2024-07-05 16:33:53 回复(0)

Java

热血的三文鱼躺平了

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String s = in.nextLine();

        char[] c = s.toCharArray();

        System.out.print(checkStr(c));

    }

    public static int checkStr(char[] c){
        int m = 0;
        for(int i = 0; i<c.length; i++)
        {
            for(int j = c.length-1; j>i; j--)
            {
                int n = cS(c,i,j);
                m = m<n?n:m;
            }
        }
        return m;
    }

    public static int cS(char[] c, int i, int j)
    {
        if(i<=j){
            if(c[i]==c[j])
                if(i!=j)
                    return 2+cS(c,i+1,j-1);
                else
                    return 1;
            else
                return -2500;
        }
        return 0;
    }
}

发表于 2024-05-04 21:52:35 回复(0)

Java

老师我太想进步溜

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int res = 0;
        for (int i = 0; i < str.length(); i++) {
            int len1 = calLen(str, i, i);
            int len2 = calLen(str, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }

        System.out.println(res);
    }

    private static int calLen(String str, int l, int r) {
        while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

编辑于 2024-03-09 16:21:04 回复(0)

Java

SnailTree

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String inputStr = in.nextLine();
        int max = inputStr.length();
        boolean flag = true;
        while (flag) {
            if (checkStr(inputStr)) {
                flag = false;
                break;
            }
            for (int i = 0; i + max < inputStr.length(); i++) {
                if (checkStr(inputStr.substring(i, i + max))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                max--;
            }

        }
        System.out.println(max);

    }
    private static boolean checkStr(String str) {
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != str.charAt(str.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

发表于 2024-01-03 16:38:52 回复(0)

Java

今生能进大厂吗

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            int count = 0;
            int max = 0;
            for (int i = 1; i < s.length() - 1; i++) {
                char c = s.charAt(i);
                //ABA
                while (true) {
                    //对于字符c 它的前一个字符等于后一个字符属于ABA型
                    //i-1-count >=0 && i+1+count< s.length()左右边界控制
                    if (i - 1 - count >= 0 && i + 1 + count < s.length() &&
                            s.charAt(i - 1 - count) == s.charAt(i + 1 + count)) {
                        count++;
                    } else {
                        if (count > 0) {
                            max = max > count * 2 + 1 ? max : count * 2 + 1;
                            count = 0;
                        }
                        break;
                    }
                }
                //ABBA  对于字符c 它等于后一个字符属于ABBA型
                if (c == s.charAt(i + 1)) {
                    while (true) {
                        //i-1-count >=0 && i+2+count< s.length()左右边界控制
                        if (i - 1 - count >= 0 && i + 2 + count < s.length() &&
                                s.charAt(i - 1 - count) == s.charAt(i + 2 + count)) {
                            count++;
                        } else {
                            if (count > 0) {
                                max = max > count * 2 + 2 ? max : count * 2 + 2;
                                count = 0;
                            }
                            break;
                        }
                    }
                }
            }
            System.out.println(max);

        }
    }
}

编辑于 2023-12-29 10:30:00 回复(0)

Java

虎图图

思路

1.设置一个方法判断字符串是否为满足题目要求的回文字符串

2.遍历输入的字符串，利用双指针、substring()方法截取不同的子字符串代入方法看是否满足条件

3.设置一个集合，存储遍历过程中的长度，输出最长长度

要点

使用双指针遍历时，外层遍历for(int i = 0;i < s.length();i ++)，需要注意内层遍历for(int j = s.length() - 1;j >= i;j --)，参数j要满足条件j > i;一是防止substring()方法出错；二是节省时间，因为i= 1，j = 5 和i = 5，j = 1区间的字符串是同一个

public class HJ032 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int count = 0;      //满足条件的子字符串的长度
        List<Integer> l = new ArrayList<>();   //存储遍历过程中的长度
        if(s.length() == 1){        //边界值处理
            System.out.println(1);
            return;
        }
        if(s.length() == 2){
            if(s.charAt(0) == s.charAt(1)){
                System.out.println(2);
                return;
            }else{
                System.out.println(1);
                return;
            }
        }
        for(int i = 0;i < s.length();i ++){      //双指针遍历字符串
            for(int j = s.length() - 1;j >= i;j --){      //参数j要满足条件j > i;一是防止substring()方法出错；
                                                         // 二是节省时间，因为i= 1，j = 5和i = 5，j = 1区间的子字符串是同一个
                if (s.charAt(i) == s.charAt(j) && isPalindromic(s.substring(i,j + 1))) {
                    count = j - i + 1;      //存储本次遍历过程中满足条件的子字符串的长度
                    l.add(count);     //将长度添加到集合l中
                }
            }
        }
        Collections.sort(l);
        System.out.println(l.get(l.size() - 1));
    }

    /**
     * 判断字符串s是否为回文字符串
     * @param s
     * @return
     */
    public static boolean isPalindromic(String s){
        if(s == null){
            return false;
        }
        for(int i = 0,j = s.length() - 1;j > i;i ++, j --){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }

}

发表于 2023-09-21 00:27:33 回复(0)

Java

陈六狗

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int arr[] = new int[str.length() * 2 - 3];
        int index = 0;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j <= i && i + j + 1 < str.length(); j++) {
                if (i - j == 0 || i + j + 1 == str.length() - 1) {
                    if (str.charAt(i - j) == str.charAt(i + j + 1)) {
                        arr[index] = (j + 1) * 2;
                        index++;
                        break;
                    } else {
                        arr[index] = j * 2;
                        index++;
                        break;
                    }
                } else {
                    if (str.charAt(i - j) == str.charAt(i + j + 1)) {

                    } else {
                        arr[index] = j * 2;
                        index++;
                        break;
                    }
                }
            }
        }
        for (int i = 1; i < str.length(); i++) {
            for (int j = 0; i - j - 1 >= 0 && i + j + 1 < str.length(); j++) {
                if (i - j - 1 == 0 || i + j + 1 == str.length() - 1) {
                    if (str.charAt(i - j - 1) == str.charAt(i + j + 1)) {
                        arr[index] = (j + 1) * 2 + 1;
                        index++;
                        break;
                    } else {
                        arr[index] = j * 2 + 1;
                        index++;
                        break;
                    }
                } else {
                    if (str.charAt(i - j - 1) == str.charAt(i + j + 1)) {

                    } else {
                        arr[index] = j * 2 + 1;
                        index++;
                        break;
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.println(max);
    }
}

发表于 2023-09-18 16:05:00 回复(0)

Java

牛客546909688号

求大神问为什么案例结果是7啊，我怎么看都觉得案例不对啊

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        //将字符串反转
        StringBuffer reverseStr = new StringBuffer("");
        for(int i=str.length()-1;i>=0;i--){
            reverseStr.append(str.charAt(i));
        }

        //比较两个字符串的相同的字符串
        int count = 0;
        int startIndex = 0;
        int endIndex = 0;
        boolean isNewStart = false;
        for(int i=0;i<str.length();i++){
            //如果显示相等，分两种情况，1）开关若是关闭，说明是第一个相等的，开始计算开始位置，开关打开  2）开关打开，说明计数已经开始，endIndex设为当前index
            if(str.charAt(i) == reverseStr.charAt(i)){
                if(isNewStart){//开关打开
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                }else{
                    startIndex = i;
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                    isNewStart = true;
                }
            }else{
                //如果显示不等，也分两种情况，1）开关关闭，未开始计数，跳转下一个字符  2）开关打开，计数开始，endIndex设为当前index，计算长度count,若大于原count，赋值给原count,开关关闭
                if(isNewStart){//开关打开
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                    isNewStart = false;
                }else{
                    continue;
                }
            }
        }
        System.out.println(count);
    }
}

案例：

tmikrmvnkzwffmuycgffiqnrepltnfvnggtmwkzmpjpcfuhmdcdlrupmqbimvppbnqinwcuidfckveonfgcknihwztkvrikfunegxfboluzjhxkoxdvdxoczqdkyjziqmjnnrbvcolyxijemlujjofuojdwfhcgzmmnsznhbv

发表于 2023-09-09 23:36:50 回复(0)

Java

爱交友的柠檬精在抱佛脚

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
      public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String str = in.nextLine();
        int max = 1;

        for (int i = 0; i < str.length() / 2; i++) {
            for (int j = i+1; j <=str.length(); j++) {

                String s1 = str.substring(i, j);
                if (find(s1)) {
                    if (max < s1.length()) {
                        max = s1.length();
                    }
                }
            }

        }
        System.out.println(max);

    }

    public static boolean find(String str) {
        if(str.length()%2==0){
                 StringBuffer sb = new StringBuffer();
        String str1 = str.substring(0, str.length() / 2);
        String str2 = sb.append(str.substring(str.length() / 2 )).reverse().toString();
        if (str1.equals(str2)) {
            return true;
        }

        }else{
            StringBuffer sb = new StringBuffer();
            String str1 = str.substring(0,str.length()/2);
            String str2 = sb.append(str.substring(str.length() / 2 +1)).reverse().toString();
           if (str1.equals(str2)) {
            return true;
        }
        }

       
        return false;
    }
}

发表于 2023-08-15 22:03:57 回复(0)

Java

牛客781396821号

思路一：暴力解法：对于每个字符，从后向前寻找它的回文字符串，记录最长的

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            int num = 0, length = a.length();
            // 确定字符
            for (int i = 0 ; i < length ; i++) {
                char c = a.charAt(i);
                // 开始遍历
                for (int j = length - 1 ; j >= i ; j--) {
                    char ch = a.charAt(j);
                    // 相同：寻找回文字符串；不同：继续寻找
                    if (c == ch) {
                        int i1 = i + 1, j1 = j - 1;
                        for (; i1 <= j1 ; i1++, j1--) {
                            if (a.charAt(i1) != a.charAt(j1)) {
                                break;
                            }
                        }
                        if (i1 >= j1) {
                            num = num > j - i ? num : j - i + 1;
                        }
                    }
                }
            }
            System.out.println(num);
        }
    }
}

思路二：从中心寻找：对于每个字符，向两侧寻找它的回文字符串，记录最长的；如果它和它后面的字符相同，则从中心两个字符开始寻找

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            int num = 0, length = a.length();
            // 确定字符
            for (int i = 0 ; i < length ; i++) {
                char c = a.charAt(i);
                // 从中心单个字符为基准开始寻找回文字符串长度
                int j = i - 1;
                int k = i + 1;
                for (; j >= 0 && k < length ; j--, k++) {
                    if (a.charAt(j) != a.charAt(k)) {
                        break;
                    }
                }
                // 计算时，这两个字符不同，需要回退一步
                j++;
                k--;
                num = num > (k - j + 1) ? num : k - j + 1;
                // 如果它和它后面的字符相同，从中心两个字符为基准开始寻找回文字符串长度
                if ((i < length - 1) && (c == a.charAt(i + 1))) {
                    for (j = i - 1 , k = i + 2; j >=0 && k < length ; j--, k++) {
                        if (a.charAt(j) != a.charAt(k)) {
                            break;
                        }
                    }
                    j++;
                    k--;
                    num = num > (k - j + 1) ? num : k - j + 1;
                }
            }
            System.out.println(num);
        }
    }
}

发表于 2023-05-25 11:43:38 回复(0)

Java

joyvvvv

public class Test01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            //dp[i][j]表示下标i-j是否是回文，不是值为0，是值为子串长度
            //这里可以使用Boolean[][]dp，如果是回文更新max长度。
            int[][] dp = new int[str.length()][str.length()];
            //i==j，表示只有一位，初始化时都是回文，长度为1；
            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = 1;
            }
            int max = 0;
            //i从下往上遍历，j从左至右遍历
            for (int i = dp.length - 1; i >= 0 ; i--) {
                //j>i,所以从i+1开始遍历
                for (int j = i + 1; j < dp[0].length ; j++) {
                    if (str.charAt(i) == str.charAt(j)) {
                        //特殊情况两位相等 值为2
                        if (j - i == 1) {
                            dp[i][j] = 2;
                        } else {
                            //如果[i+1][j-1]是回文，[i][j]+2
                            dp[i][j] =dp[i+1][j-1]==0?0:dp[i+1][j-1]+2;
                        }
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            System.out.println(max);
        }
    }
}

发表于 2023-05-16 20:59:36 回复(0)

Java

牛客604637229号

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNext()) { // 注意 while 处理多个 case

String a = in.next();

TreeMap<Integer,String> treeMap = new TreeMap<Integer,String>();

for(int i=0;i<a.length();i++){

for(int j=a.length();j>i;j--){

StringBuffer bf = new StringBuffer();

String substr = a.substring(i,j);

boolean flag = true;

int substrlen = substr.length();

//根据dp[i]=dp[len-1-i]表达式进行规划

for(int k=0;k<(int)(substrlen/2);k++){

if(substr.charAt(k)!=substr.charAt(substrlen-1-k)){

flag = false;

break;//当前的中断，只是本循环的中断

}

if(flag){

treeMap.put(substrlen,substr);

}

System.out.println(treeMap.lastEntry().getKey());

}

发表于 2023-04-20 00:44:19 回复(0)

密码截取

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

思路

要点

问题信息

热门推荐

通过挑战的用户

相关试题