字符串回文数算法有没有通用公式
刚才在这边看到一提,如图:
能够写出一些代码,但是还缺少最后一步,请赐教:
/**
* 计算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;
}
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);
}
}
abccba
acbbca
baccab
bcaacb
cabbac
cbaabc
回文字符串个数为：6
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;
}
}
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;
}
}
[解决办法]
这里附加说明一下，对于成对的字母，如果超出一对，要除以其排列数(即阶乘)
比如，传入"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种
