刚才在这边看到一提,如图:
能够写出一些代码,但是还缺少最后一步,请赐教:/**
* 计算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;
}
能够写出一些代码,但是还缺少最后一步,请赐教:/**
* 计算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); }}consoleabccba
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个回文字符串。
但是比如这样: aa,bbbb,cccc,dd,e
貌似不能直接算阶乘吧?
但是比如这样: aa,bbbb,cccc,dd,e
貌似不能直接算阶乘吧?对于这种情况，算出重复数量的字符，然后做一次除法运算即可
例如"aaaaaabbbbccd" -> aaabbc = A(6,6) / A(3,3)/A(2,2)=6!/3!/2!=60稍后会附上代码
但是比如这样: aa,bbbb,cccc,dd,e
貌似不能直接算阶乘吧?对于这种情况，算出重复数量的字符，然后做一次除法运算即可
例如"aaaaaabbbbccd" -> aaabbc = A(6,6) / A(3,3)/A(2,2)=6!/3!/2!=60稍后会附上代码
附上代码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;
}
}
public static int palindrome(String s) {
if(s == null || s.length()>100 || s.length() < 1){
return 0;
}
int[] counts = new int[26];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - 'a']++;
}
if (!can(counts)) {
return 0;
}
int sum=0;
double divider=1;
for (int i = 0; i < counts.length; i++) {
divider *= permutation(counts[i]/2);
} double result = permutation(s.length()/2)/divider;
return (int) (result % 1000000007);
} private static double permutation(int n) {
if (n < 0)
return 0;
if(n==0)
return 1;
double result = 1;
while(n > 0){
result *= n;
n--;
}
return result;
} private static boolean can(int[] counts) {
int oddCount= 0;
for (int count : counts) {
if (count % 2 != 0) {
oddCount++;
}
}
return oddCount<= 1;
}
其实回文的真谛在于左起第N位和右起第N位相同，而此题又仅需计算数量而非列举打个比方，我给你abcdefg七个字母，1秒钟你就能回答：“无法构成回文”，为什么你没有对它排列组合就能得到结论？然后我们尝试一下换个角度想问题，我把这n个字母组成的字符串以第1位、第n位、第2位、第n-1位、第3位、第n-2位……排列，会发现，所谓回文，只是找“成对”的字母的数量而已。伪代码如下：
if(字母量为奇数){
找到一个不成对的字母，剔除。
//此时字母量变成偶数了
}
if(检查所有字母全部都成对){
return 计算字母对的配列组合有多少种//并非进行排列组合遍历，而是公式计算
}else{
return 0;
}这样就算给出一万个字母，你也可以1秒钟之内计算出回文有多少个。相反，如果采取遍历，估计给你一百个字母你就要死机了
return 计算字母对的配列组合有多少种//并非进行排列组合遍历，而是公式计算请问这个这个字母对的排列组合是多少？没有太明白你的意思，请详解此处，多谢！
比如给我的字母是"aabbccde",我直接return 0,为什么呢？因为d和e都不成对，回文怎么放？
而对于"aabbc"，则回文必然把c放在第3位，于是我剔除它，变成"aabb"处理那么，现在，假如我得到的是"aabbcc"，怎么处理呢？
我有一对a、一对b、一对c，那么，我只需要将abc排列组合即可。计算公式为3!=3*2*1=6
也就是说abc、acb、bac、bca、cab、cba对应的回文就是
abc|cba、acb|bca、bac|cab、bca|acb、cab|bac、cba|abc
其中的竖线是为了便于理解而加上的，实际中没有。而因为题目并不需要将回文列举出来，故直接公式计算即可
为什么呢？因为我们计算排列的时候，是把2对a看作不同的a1 和 a2计算的，但是a1和a2其实可以互换
详解：比如我们心中a1 a2 b和a2 a1 b是当作两个来计算的，而实际上他们都是aab，所以应该除那么"aaaabbbb"应该有多少？结果是4!/2!/2!=(4*3*2*1)/2/2=6种
像墙面几位朋友那样说的话,
感觉之前我的工作白做了.....
是不是可以这样计算:
return doubleNumber!/( doubleNumber == 0 ? 1 : doubleNumber )!