给定一个字符串,求这个字符串的最大回文数.doc
《给定一个字符串,求这个字符串的最大回文数.doc》由会员分享,可在线阅读,更多相关《给定一个字符串,求这个字符串的最大回文数.doc(6页珍藏版)》请在三一文库上搜索。
1、题目:回文判断是一类典型的问题,尤其是与字符串结合后呈现出多姿多彩,在实际应用中比较广泛,下面介绍几个回文的问题。首先我们要介绍一个什么叫回文数:回文,就是指一个字符串顺着读和反着读都是一样的字符串,例如madam,你我你,我爱我 等等一些列的字符串1、首先来判断一下一个字符串是否是回文字符串:java view plaincopyprint?1 public int palindromeNumber(String s, int low, int high) 2 if (low = high) 3 return 1; 4 else if (low high) 5 if (s.charAt(lo
2、w) = s.charAt(high) & (high - low) = 1) /防止出现abba等情况 6 return 1; 7 if (s.charAt(low) = s.charAt(high) & (high - low) != 1) /这是类似aba的情况 8 return palindromeNumber(s, low + 1, high - 1); 9 else 10 return 0; 11 else 12 return 0; 13 上面的这个方法,如果输入的字符串是回文字符串的话,则输出1,如果不是的话,输出0,2、已经明白了如何判断一个字符串是否是回文数,接下来我们就要求
3、出一个给定字符串中最大的回文数是多少,就是把这个回文数的长度打出来java view plaincopyprint?14 package programmer; 15 16 import java.util.Scanner; 17 18 /* 19 * 回文判断是一类典型的问题,尤其是与字符串结合后呈现出多姿多彩,在实际中使用也 20 * 比较广泛,而且也是面试题中的常客,所以本文就结合几个典型的例子来体味下回文之趣。 21 * 回文,英文palindrome,指一个顺着读和反过来读都一样的字符串,比如 madam、 22 * 我爱我,这样的短句在智力性、趣味性和艺术性上都颇有特色,中国历史上
4、还有很多 23 * 有趣的回文诗呢 24 */ 25 public class PalindromeNumber 26 27 public int palindromeNumber(String s, int low, int high) 28 if (low = high) 29 return 1; 30 else if (low high) 31 if (s.charAt(low) = s.charAt(high) & (high - low) = 1) 32 return 1; 33 if (s.charAt(low) = s.charAt(high) & (high - low) !=
5、 1) 34 return palindromeNumber(s, low + 1, high - 1); 35 else 36 return 0; 37 else 38 return 0; 39 40 41 /* 42 * 这里求一个字符串中的最长回文字符串的长度,我们使用了枚举的方法,但是这 种方法的时间复杂度还是很大的,浪费了很多不必要的时间和判断,比如当判断 43 * 子串 不是回文时, 就不必要再判断包含本子串的父串了 44 */ 45 public int maxPalindrome1(String s) 46 int len = 0, max = 0; 47 for (int i
6、 = 0; i = i; j-) 49 if (palindromeNumber(s, i, j) = 1) 50 len = j - i + 1; 51 52 if (max len) 53 max = len; 54 55 56 return max; 57 58 59 public static void main(String args) 60 Scanner sc = new Scanner(System.in); 61 String s = sc.nextLine(); 62 System.out.println(new PalindromeNumber().palindromeN
7、umber(s, 0, 63 s.length() - 1); 64 System.out.println(new PalindromeNumber().maxPalindrome1(s); 65 66 上面的思想也十分简单,就是逐个遍历,显然这是十分耗费时间的,时间复杂度为O(n*n*n),因为还要判断这个是否是回文数,所以比较浪费时间。接下来我们提供一种比较有建设性的方法。3、我们知道回文数是正着读和反着读是一样的,就是说对于一个给定的字符串,如果我们将这个字符串逆置的话,我们就会发现两个字符串有一个最长的连续相同的子序列,则这个连续的最长的共同子序列就是我们要求的回文数,例如:abcab
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 给定 一个 字符串 这个 最大 回文
链接地址:https://www.31doc.com/p-2715780.html