精华内容
下载资源
问答
  • 最后打印那部分我没做,如果有需要的同学...//回文字符串暴里破解法,求回文字符串长度 public class huiwen1 { public static void main(String[] args) { //写下字符串并拆分成数组 Scanner sc = new Scanner(Sys

    最后打印那部分我没做,如果有需要的同学,可以看我的最后输出长度上边的打印注解。

    因为已经求出最大长度,那打印很简单,只需要记录下两个值就可以打印。

    (以下为代码)

    import java.util.Scanner;
    //回文字符串暴里破解法,求回文字符串长度
    public class huiwen1 {
        public static void main(String[] args) {
            //写下字符串并拆分成数组
            Scanner sc = new Scanner(System.in);
            char[] array= sc.nextLine().toCharArray();
            //记录最大回文字符串长度
            int max = 0;
            //从第一个字符开始判断
            for (int i = 0; i < array.length-1; i++) {
                //从后往前找,找到与第i个字符相同的
                for (int j = array.length-1; j > i; j--) {
                    //找到相同
                    if (array[i] == array[j]){
                        //找寻中心点位置
                        int zhong = (i+j)/2;
                        int add = 0,num1=0;
                        //如果为是长度为3,那么中心点就是2,如果长度是4,那么中心点是2,3,要判断下
                        if ((i+j)%2==1){
                            add = 1;
                        }
                        int jilu = zhong+add;
                        //由中心向外判断,如果依次都是回文,那就没事,如果不是,就退出,就说明i到j这一段不是回文
                        for (int k = zhong+add; k < j; k++) {
                            if (add==0 && (k+1)==j){
                                num1=k;
                                break;
                            }
                            if (array[k]!=array[jilu-1])
                                break;
                            else{
                                num1=k;
                                jilu--;
                            }
                        }
                        //此处判断为,一旦是回文,那就求出长度,方便后续判断
                        if (num1+1==j){
                            max = max > j-i+1?max : j-i+1;
                        }
                    }
                    //此处为在知道是回文基础上,减少i循环次数,节约时间,从第j开始出发找下个回文
                    if (max!=0){
                        i=j;
                        break;
                    }
                }
            }
            //如果全部不是回文,那就要打印1
            if (max == 0)
                max=1;
            //想打印最长回文字符串,可以在找出回文字符串的里面
            // 把i和j的所在的字符位置,记录下,再最后for循环i到j打印
            System.out.println(max);
        }
    }
    
    展开全文
  • Java 获取最大回文字符串

    千次阅读 2014-05-27 21:49:42
    获取最大回文字符串也是笔记中常考到的一个题目

    获取最大回文字符串也是笔记中常考到的一个题目,花果山用Java语言实现了时间复杂度为O(n^3)和O(n^2)的算法,而这篇博客则用C++实现了三种寻找最大回文的算法,前两种时间复杂度相似,其中第三种复杂度为O(n)的看的不是很明白。我们这里重点借鉴了其第二种插入标志字符的方式来实现寻找最大回文,这种方法用空间复杂度来减少了些许时间复杂度。该思想的核心是在待查找最大回文的字符串中每隔一个字符插入一个在字符串中不存在的一个字符,从而将查找奇数长度的回文和偶数长度的回文合并到一起。

    	/**
    	 * 获取最大回文,时间复杂度为O(n^2)
    	 * @param s	待查找的字符串
    	 * @return
    	 */
    	public String getMaxPalindrome(String s){
    		byte flag;
    		//在前32位控制字符中找到一个字符串s中不存在的标志符
    		for(flag=1;flag<32;flag++){
    			if(s.indexOf(flag)==-1){
    				break;
    			}
    		}
    		if(flag==32)
    			return null;
    		StringBuffer sb=new StringBuffer();
    		//插入标志符
    		for(int i=0;i<s.length();i++){
    			sb.append(s.charAt(i));
    			sb.append((char)flag);
    		}
    		int maxLen=0;
    		int start=0;
    		int end=0;
    		for(int i=0;i<sb.length();i++){
    			int tmpLen;
    			int offset;
    			//如果sb中第i位字符是标志符
    			if(sb.charAt(i)==flag){
    				tmpLen=0;
    				offset=1;
    			}
    			//如果是普通字符
    			else {
    				offset=2;
    				tmpLen=1;
    			}
    			for(;offset<i&&sb.length()-i-1>offset;offset=offset+2){
    				if(sb.charAt(i-offset)==sb.charAt(i+offset)){
    					tmpLen=tmpLen+2;
    					if(tmpLen>maxLen){
    						maxLen=tmpLen;
    						start=i-offset-1;
    						end=i+offset+1;
    					}
    				}
    				else continue;
    			}
    		}
    		//首先将byte强制转换为char,在转换成String进行替换
    		return sb.substring(start, end).replaceAll(""+(char)flag, "");
    	}



    注意上述代码中通过记录最大回文在sb中的位置,最后再转换成字符串,而不是在一开始通过设置一个maxStr这样的变量,在找到新的最大回文时更新这个变量。这样做是为了减少计算量,new一个String变量或者对String变量重新复制都比直接记录字符串位置耗时。

    展开全文
  • leetcode第五题 最大回文字符串长度(java代码)题目描述 题目描述 给定一个字符串S,找到S中最长的回文子串。你可以假设S的最大长度为1000, 示例1 输入:“babad” 输出:“bab” 注意:“aba也是一个有效的答案” ...

    leetcode第五题 最大回文字符串长度(java代码)

    题目描述

    给定一个字符串S,找到S中最长的回文子串。你可以假设S的最大长度为1000,

    示例1
    输入:“babad”
    输出:“bab”
    注意:“aba也是一个有效的答案”

    示例2
    输入:“cbbd”
    输出:“bb”

    java 代码

    public  void Five(){
                Scanner s=new Scanner(System.in);
                String name = s.nextLine();
                String split="";
                String [][] lines= new String[name.length()][name.length()];
                String [][] equip= new String[name.length()][name.length()];
                String value="";//记录最大回环字符串
                int max=-1;
                for (int i=0;i<name.length();i++){
                    split="";
                    for (int j=i;j<name.length();j++){
                        split=split+name.charAt(j);
                        lines[i][j]=split;
                    }
                    System.out.println();
                }
                for (int i=0;i<name.length();i++){
                    for (int j=i;j<name.length();j++){
                        if (Five_res(lines[i][j]).equals(lines[i][j])&&max<lines[i][j].length()){
                            max=lines[i][j].length();
                            value=lines[i][j];
                        }
                    }
                }
                System.out.println("最大回环字符串长度为"+max+",回环字符串为:"+value);
        }
    
        public  String Five_res(String s){
            String restring="";
            for (int i=s.length()-1;i>=0;i--){
                restring=restring+s.charAt(i);
            }
    
            return  restring;
        }
    

    运行结果

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • * 找出一个数组中的最大回文字符串 * 思路:1,遍历每个字符,从第一个到最后一个。for() * 2.以当前字符为基准点,向左向右延伸,看左右是否相等[注意基数回文与偶数回文判断方法不一样]。f...
    /**
     * Created by Administrator on 2017/4/23.
     * 找出一个数组中的最大回文字符串
     * 思路:1,遍历每个字符,从第一个到最后一个。for()
     * 2.以当前字符为基准点,向左向右延伸,看左右是否相等[注意基数回文与偶数回文判断方法不一样]。for(j)
     * 3.遇到不相等的时候,把回文长度赋值给current,比较current与max,用break跳出循环
     * 4.返回值
     */
    public class Synonym {
        public String circuit(String str){
            int current=0;
            int max=0;
            String biggest=" ";
            for(int i=0;i<str.length();i++){
                for(int j=0;j+i<str.length()&&i-j>=0;j++)
                {if(str.charAt(i-j)!=str.charAt(i+j)) {
                    current=2*j-1;
                    if(current>max){
                        max=current;
                        biggest=str.substring(i+1-j,i+j);
                    }
                    break;
                }
                }
                for(int j=0;j+i+1<str.length()&&i-j>=0;j++){
                   if(str.charAt(i-j)!=str.charAt(i+1+j)){
                       current=2*j;
                       if(current>max){
                           max=current;
                           biggest=str.substring(i+1-j,i+1+j);
                       }
                       break;
                   }
                }
            }
            return max+"   "+biggest;
        }
    
        public static void main(String[] args) {
            Synonym sy=new Synonym();
            System.out.println( sy.circuit("aabbbcccdddccbb"));
        }
    }

    转载于:https://my.oschina.net/u/3321842/blog/885412

    展开全文
  • 验证回文字符串II做题博客链接题目链接描述示例初始代码模板代码 做题博客链接 https://blog.csdn.net/qq_43349112/article/details/108542248 题目链接 https://leetcode-cn.com/problems/valid-palindrome-ii/ ...
  • Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化ABBA->12ABBA,ABA-&...
  • 题目描述: ...比如,abxdba,删去x,可以得到abdba,是一个回文字符串,你的任务就是求出给定的字符串删去若干字符后可以得到的最长回文字符串的长度。字符串长度不超过1000,字符范围从'a'到'z'。...
  • 680. 验证回文字符串 Ⅱ 题目描述 给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: “aba” 输出: True 示例 2: 输入: “abca” 输出: True 解释: 你可以删除c字符。 注意: 字符...
  • Java实现 LeetCode 680 验证回文字符串 Ⅱ(暴力)

    万次阅读 多人点赞 2020-04-04 17:12:44
    680. 验证回文字符串 Ⅱ 给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: “aba” 输出: True 示例 2: 输入: “abca” 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含...
  • 回文字符串需要分情况考虑,分奇偶两种情况,为奇数是i==i,然后向两边扩展,当为偶数时,先判断 i ==i+1 字符是否一样,一样则向两边扩展,否则他就不可能是回文串。 最后回文长度就是right - left -1,这个可以举...
  • 问题描述 草稿解决过程 ...import java.util.Scanner; /** * Created by Admin on 2017/3/26. */ public class test02 { public static int HuiWenNum(String str){ String rev=n...
  • 字符串中最长的回文字符串长度

    千次阅读 2016-07-13 08:10:14
    1、回文字符串  回文字符串是指aba类型的字符串,即字符串关于中间字符对称。判断字符串中是否含有回文、得到最长回文字符串的长度、得到不同回文字符串的个数等等,是经常考察的编程题目。 2、之前采用的一种...
  • 回文字符串是指将该字符串前后颠倒之后和该字符串一样的字符串。例如:a,aaaa,aba,abba… 最长回文子串 要求最长回文子串,就需要遍历每一个子串,时间复杂度是O(N²);判断字串是不是回文,时间复杂度是
  • 回文字符串

    千次阅读 2013-09-03 14:52:20
    回文字符串 这是一道在线编程的题目,题目详情:  回文字符串是指从左到右和从右到左相同的字符串,现给定一个仅由小写字母组成的字符串,你可以把它的字母重新排列,以形成不同的回文字符串。  输入:非空仅由...
  • 求解最长回文字符串朴素算法最朴素的算法是暴力解法就不谈了,时间复杂度是O(n3)。比最朴素解法稍微好一些的解法是O(n2)的一种解法,思路是从对称轴开始考虑,根据回文字符串长度的奇偶分为两种情况,如果最长的回文...
  • 回文字符串问题

    2016-07-22 19:09:29
    一动态规划法 二中心检测法 三添加辅助标志 四字符串变成回文字符串需要添加的字符数
  • 判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。 想法 首先假设我已经...
  •  该代码的功能可以实现对任意的一段字符串进行判断是否有回文,回文有哪些,和其中的最大回文。 二、代码部分 1、全局变量 1 static String hws = ""; 2 static int num = 0; 3 static String[] hw; 2、...
  • 680. 验证回文字符串 Ⅱ 难度简单336收藏分享切换为英文接收动态反馈 给定一个非空字符串s,最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: ...
  • 字符串删除字符的回文字符串

    千次阅读 2017-12-11 22:18:16
    求原字符串和其反串的最大公共子序列(不是子串,因为可以不连续)的长度(使用动态规划很容易求得),然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。字符串逆转:def rev
  • 判断是否能成为回文字符串。 示例 1: 输入: “aba” 输出: True 示例 2: 输入: “abca” 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。 代码 /* * @lc app=...
  • 判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。 注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。 题目要求当字符串不是...
  • import java.util.ArrayList; import java.util.Scanner;public class dbDemo { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String s = scan.nextLine();
  • 判断是否能成为回文字符串。 class Solution { public boolean validPalindrome(String s) { char[] ch = s.toCharArray(); //双指针 int left = 0, right = ch.length - 1; while (left < right) { //如果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,878
精华内容 2,351
关键字:

最大回文字符串java

java 订阅