算法求教，ACM 题目指导

问答首页 → 编程语言技术

0 0

算法求教，ACM 题目指导10

题目：要求对任意一个字符串，通过加入若干字符使其对称
如abcda至少要插入两个字符，两个一下无法使其对称abdcdba，adbcdba
请求出需要插入的最少字符数

希望大家能给我出出主意，给点解决这个题目的思路！感激

Java ACM

2013年4月15日 09:19

1140566087
2
0 0 6

7个答案按时间排序按投票排序

0 0

采纳的答案

	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++)
就可以满足了

2013年4月15日 10:25

Dead_knight
1227
2 3 49

1条评论

0 0

	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;
	}

2013年4月15日 11:00

Dead_knight
1227
2 3 49

添加评论

0 0

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

2013年4月15日 10:35

hejiaqi789
123
1 1 12

添加评论

0 0

	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--。这个思路不对，应该去掉，并且用新的办法重新计算，等中午有空，再改造下

2013年4月15日 10:21

Dead_knight
1227
2 3 49

添加评论

0 0

	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;
	}

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

2013年4月15日 10:11

Dead_knight
1227
2 3 49