zhang583740618
rjbusiness
采纳率0%
2013-04-15 09:19 阅读 225
已采纳

算法求教,ACM 题目指导

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


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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

7条回答 默认 最新

  • 已采纳
    Dead_Knight Dead_Knight 2013-04-15 10:25

    [code="java"]
    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;
    }
    [/code]
    循环的地方改成:
    for(int i = 0; i <= compareIndex; i++)
    就可以满足了

    点赞 评论 复制链接分享
  • zyn010101 zyn010101 2013-04-15 10:02

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

    点赞 评论 复制链接分享
  • jinnianshilongnian jinnianshilongnian 2013-04-15 10:08

    我的理解是递归做
    abcda
    1、首先判断第一个和最后一个是否一样
    2、如果不一样 分两种情况 --> 最前 最后 插入字符 然后再递归(带上当前的插入的数量) 找下去 找到最后即可 这样就找到每种情况

    3、优化 可以把找完的存到一个位置 然后其他递归每次找时和之前找到的进行匹配 如果大于就提前终止 不再找了

    点赞 评论 复制链接分享
  • Dead_Knight Dead_Knight 2013-04-15 10:11

    [code="java"]
    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;
    }
    [/code]
    粗略的写了个,你测试下,与你的目标算法可有出入。我测试几个,基本上是正确的。

    点赞 评论 复制链接分享
  • Dead_Knight Dead_Knight 2013-04-15 10:21

    [code="java"]
    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;
    }
    [/code]
    测试了一下,觉得有些小问题,就是判断个数是否为奇数,如果奇数,count--。这个思路不对,应该去掉,并且用新的办法重新计算,等中午有空,再改造下

    点赞 评论 复制链接分享
  • hejiaqi789 hejiaqi789 2013-04-15 10:35

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

    点赞 评论 复制链接分享
  • Dead_Knight Dead_Knight 2013-04-15 11:00

    [code="java"]
    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;
    }
    [/code]

    点赞 评论 复制链接分享

相关推荐