算法求教，ACM 题目指导

Question

题目：要求对任意一个字符串，通过加入若干字符使其对称如abcda至少要插入两个字符，两个一下无法使其对称abdcdba，adbcdba请求出需要插入的最少字符数希望大家能给我出出主意，给点解决这个题目的思路！感激

Answer 1

public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i <= compareIndex; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
return count;
}

循环的地方改成：
for(int i = 0; i <= compareIndex; i++) 
就可以满足了

Answer 2

这个问题灰常简单：我们不知道该字符串的对称序号位于字符串的第几个字符，也就没有办法从中间字符一次对比来增加字符，换个思路，我们可以从开头和末尾来对比，倒数第一正数第一相同，依次对比倒数第二个和正数第二个；倒数第一正数第一不同则在开头或者末尾增加字符，然后再对比倒数第二个正数第二个......

Answer 3

public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i < length; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
if(count % 2 == 1) {
count--;
}
return count;

粗略的写了个，你测试下，与你的目标算法可有出入。我测试几个，基本上是正确的。

Answer 4

public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i < length; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
return count;
}

测试了一下，觉得有些小问题，就是判断个数是否为奇数，如果奇数，count--。这个思路不对，应该去掉，并且用新的办法重新计算，等中午有空，再改造下

Answer 5

提示：
定义一个计数的number=0。
然后一定是进行首尾比较。
做两个下标变量i,j.首是：i=0,尾是：j=n.
如果相等;i++,j--,判断条件是j>i
如果不等.i++,number++,j不变.
最终number应该就是最少字符数了吧.

Answer 6

public static int symmetry(String source) {
StringBuffer target = new StringBuffer(source);
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i <= compareIndex; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
target.insert(compareIndex + 1, c);
}
}
System.out.println(target.toString());
return count;
}