字符串回文数算法有没有通用公式
刚才在这边看到一提,如图:
能够写出一些代码,但是还缺少最后一步,请赐教:
/**
* 计算s指定的字符串能够组成的回文字符串的个数
*
* @param s
* 全小写字母,且长度小于100的源字符串
* @return count 能够组成的回文字符串个数
*/
public static int palindrome(String s) throws Exception {
int count = 0;
// 字符串不能为空
if (s == null) {
throw new Exception("字符串不能为空");
}
// 将s装换为字符数组
char[] sToArray = s.toCharArray();
// 将sToArray数组排序
Arrays.sort(sToArray);
// 将排序后的字符数组转换为字符串
String strConvert = sToArray.toString();
int onlyNumber = 0;// 单个出现的字符个数
int baseNumber = 0;// 不成对出现的相同字符的个数
int doubleNumber = 0;// 成对出现的相同字符的个数
int nowPosition = 0;// 当前下标位置
int oldPosition = nowPosition;// 上次读取的位置
// 遍历不重复出现的字符并记录相同字符个数和单个字符个数
while (nowPosition != strConvert.length()) {
// 找到与上次位置指定字符重复的最后下标
nowPosition = strConvert.lastIndexOf(oldPosition);
// 如果上次读取的位置不等于当前读取的位置,相同字符个数加1
// 当前操作位置累加1,上次操作的位置等于累加后的操作位置
if (oldPosition != nowPosition) {
// 相同字符的长度,用于判断是否在回文字符串的中间位置
if ((nowPosition - oldPosition) % 2 == 0) {
// 等于0,说明该长度是基数,则只能出现在中间位置
baseNumber++;
} else {
// 不等于0,说明是偶数长度,可以出现在以length/2 或 length/2+1的位置
doubleNumber++;
}
// 当前操作位置等于上次操作位置,当前字符为单个字符,只能出现在中间位置
} else {
onlyNumber++;
}
// 单个出现的字符超过两个时,该字符串不能构成回文字符串,方法结束
if (onlyNumber == 2) {
return count;
}
// 当前位置下移
nowPosition++;
// 记录偏移后的位置
oldPosition = nowPosition;
}
//计算回文数
/*这里不知道怎么实现*/
return count;
}
------解决方案--------------------
用stringbuffer的reverse是方法，先倒序，再和之前的进行equalas比较，是true就是回文。
[解决办法]
LS好法子。
还有个法子就是写个判断方法专门判断是否回文：下标i=0，j=str.length()-1然后按位比较字符是否相等。出现不相等立即return false。当i>=j时退出循环，return true。
这样就不用额外的StringBuilder了。
[解决办法]
最笨的办法就 全排列+回文判断，lssss的判断方法没问题
[解决办法]
package com.zf.test08;
import java.util.concurrent.atomic.AtomicInteger;
public class Test01 {
public static int palindrome(String s) throws Exception {
AtomicInteger palindromeSize = new AtomicInteger(0) ;
permutation(s.toCharArray() , 0 , palindromeSize);
return palindromeSize.intValue() ;
}
/**
* 全排列
* @param palindromeSize 回文字符串数量（
* 为了便于递归之后获取，所以用AtomicInteger类型。而不用int，因为int是值传递）
*/
public static void permutation(char[] array , int index , AtomicInteger palindromeSize){
if(index > array.length - 1){
if(isPalindrome(array)){
palindromeSize.incrementAndGet() ;
System.out.println(new String(array));
}
}
for (int i = index ; i < array.length; i++) {
if(contains(array , index , i))
continue ;
swap(array, index, i);
permutation(array , index + 1 , palindromeSize) ;
swap(array, index, i);
}
}
/**
* 检查字符数组组成的字符串是否为回文
*/
public static boolean isPalindrome(char[] array){
for (int i = 0; i < (array.length / 2) ; i++) {
if(!(array[i] == array[array.length - i - 1])){
return false ;
}
}
return true ;
}
public static boolean contains(char array[] , int index , int i){
for (int j = index; j < i ; j++) {
if(array[j] == array[i])
return true;
}
return false;
}
public static void swap(char[] array , int i , int j){
char tmp = array[i] ;
array[i] = array[j];
array[j] = tmp ;
}
public static void main(String[] args) throws Exception {
int result = palindrome("aabbcc") ;
System.out.println("\n\n回文字符串个数为：" + result);
}
}
console
abccba
acbbca
baccab
bcaacb
cabbac
cbaabc
回文字符串个数为：6
[解决办法]
说说我的思路：
注意本题没有要求输出字符串，只需要输出字符串个数。
1.判断字符串是否可形成回文字符串
回文字符串只有abccba和abcba两种形式。
即aabbcc，字符成对出现 -->情况1
或者aabbc,字符成对出现，仅包含一个任意的其他字符 -->情况2
2.无论是情况1和情况2，回文字符串个数为成对字符数量的全排列组合数。
情况1：3！=6
情况2：2！=2
注意：当仅有1个字符的时候，成对字符数量为0，0！=1，有1个回文字符串。
[解决办法]
附上代码
public class Test01 {
public static void main(String[] args) {
// 测试
final String[] arr = new String[] { "a", "aabbcc", "abbccba",
"aaaaaabbbbccd", "aaaaaaaabbbbccd","aaaabbccdddddee", "abccdb" };
for (String string : arr) {
long start = System.nanoTime();
int count = palindrome(string);
long end = System.nanoTime();
System.out.printf("字符串%s,长度%d,回文字符串个数%d,耗时%f秒\n", string,string.length(), count,(end -start)/1e9);
}
}
/**
* 计算s指定的字符串能够组成的回文字符串的个数
*
* @param s
* 全小写字母,且长度小于100的源字符串
* @return count 能够组成的回文字符串个数,没有回文字符串返回-1
*/
public static int palindrome(String s) {
if (s == null
[解决办法]
s.equals("")) {
return -1;
}
char[] charArr = s.toCharArray();
// 由于全部是小写字母，所以可以用int数组做
int[] countArr = new int[26];
for (char c : charArr) {
++countArr[c - 'a'];
}
int singleCharCount = 0;// 不成对字符数量
int divider = 1; // 需要除去的数字
for (int i : countArr) {
if ((i & 1) == 1) {
++singleCharCount;
}
// 检查是否有2个不成对字符
if (singleCharCount > 1) {
return -1;
}
// 不论奇偶数i / 2都相同
divider *= getFactorial(i / 2);
}
// 计算回文字符串个数
int total = getFactorial(s.length() / 2);// 总数
return total / divider;
}
/** 计算阶乘 */
static int getFactorial(int n) {
if (n == 0)
return 1;
int sum = 1;
for (int i = 1; i <= n; ++i) {
sum *= i;
}
return sum;
}
}
[解决办法]
之前看了标题一直没点进来，原来题目比标题有意思一些……
思路：
因为都是小写字母，所以首先想到的是用两个数组 （boolean[26]， int[26]） 进行计数，最终 int[26] 内的结果是成对出现的字母的数量折半，此时假如 boolean[26] 内有大于1个的 true，则回文数为 0
假如回文数不为0，那么按照 int[26] 中的字母数量进行全排列，去重之后就是回文数，实际操作可以用 Set<String> (如果这一步还能优化，那更好，暂时想不出算法）
[解决办法]
Calculator 类的源码在这里： http://blog.csdn.net/raistlic/article/details/7844812
一个字符串，只要其奇数个的字母不多余一种，那么其回文数都可以这样算出来：
比如 "aabbccccd"，其中偶数个的字母折半后是 "abcc"，全排列个数为 4!，其中 cc 重复，cc的全排列个数为 2!,
则回文数为 4! / 2! = 12
另如 "aaaabbbbbbc", 其中偶数个的字母折半后是 "aabbb"， 5! / (2! * 3!) = 10
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class PalindromeCount {
public static void main(String[] args) {
String sample = "aabbccdeeee";
System.out.println(getPalindromeCount(sample));
}
private static BigInteger getPalindromeCount(String str) {
assert str != null;
boolean[] flags = new boolean[26];
int[] counts = new int[26];
for(int i=0, len=str.length(); i<len; i++) {
int c = str.charAt(i) - 'a';
if( flags[c] )
counts[c]++;
flags[c] = !flags[c];
}
int all = 0;
List<Integer> redundants = new ArrayList<Integer>();
for(int i=0, odd=0; i<26; i++) {
if( flags[i] ) {
odd++;
if( odd > 1 )
return BigInteger.ZERO;
}
all += counts[i];
if( counts[i] > 1 )
redundants.add(counts[i]);
}
BigInteger result = Calculator.factorial(all);
for(Integer r : redundants)
result = result.divide(Calculator.factorial(r));
return result;
}
}
[解决办法]
11楼神人,神马排列组合都是在浪费时间
其实回文的真谛在于左起第N位和右起第N位相同，而此题又仅需计算数量而非列举
打个比方，我给你abcdefg七个字母，1秒钟你就能回答：“无法构成回文”，为什么你没有对它排列组合就能得到结论？
然后我们尝试一下换个角度想问题，我把这n个字母组成的字符串以第1位、第n位、第2位、第n-1位、第3位、第n-2位……排列，会发现，所谓回文，只是找“成对”的字母的数量而已。
伪代码如下：
if(字母量为奇数){
找到一个不成对的字母，剔除。
//此时字母量变成偶数了
}
if(检查所有字母全部都成对){
return 计算字母对的配列组合有多少种//并非进行排列组合遍历，而是公式计算
}else{
return 0;
}
这样就算给出一万个字母，你也可以1秒钟之内计算出回文有多少个。相反，如果采取遍历，估计给你一百个字母你就要死机了
[解决办法]
这里附加说明一下，对于成对的字母，如果超出一对，要除以其排列数(即阶乘)
比如，传入"aaaaabb"，剔除一个a，变成2对a、1对b，那么结果就是3!/2!=3
为什么呢？因为我们计算排列的时候，是把2对a看作不同的a1 和 a2计算的，但是a1和a2其实可以互换
详解：比如我们心中a1 a2 b和a2 a1 b是当作两个来计算的，而实际上他们都是aab，所以应该除
那么"aaaabbbb"应该有多少？结果是4!/2!/2!=(4*3*2*1)/2/2=6种