V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ddmad1030
V2EX  ›  程序员

Leetcode 刷题遇到的问题!求助!

  •  
  •   ddmad1030 · 2016-03-17 16:55:11 +08:00 · 2669 次点击
    这是一个创建于 3155 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在做最长回文子字符串的问题(第 5 题)的时候, 我用的是 Manacher 算法,按理说应该可以过( O ( n )),但是居然超时了,答案倒是对的, 看了半天也不知道哪里出了问题,求助啊 T^T 。

    下面是代码:

    public class Solution {
        public String longestPalindrome(String s) {
            if (s.length() <= 1) {
                return s;
            }
            
            String newString = addHelperChar(s);
            int[] p = new int[newString.length()];
            int maxId = 0;
            int maxRange = 0;
            
            for (int i = 1; i < newString.length(); i ++) {
                p[i] = maxRange > i ? (p[2 * maxId - i] < maxRange - i ? p[2 * maxId - i] : maxRange - i) : 1;
                while (i - p[i] > 0
                    && i + p[i] < newString.length()
                    && newString.charAt(i + p[i]) == newString.charAt(i - p[i])) {
                        p[i]++;
                }
                if (maxRange < p[i]) {
                    maxId = i;
                    maxRange = p[i];
                }
            }
            
            String result = "";
            for (int i = maxId - maxRange + 1; i < maxId + maxRange; i ++) {
                char temp = newString.charAt(i);
                if (temp != '#') {
                    result += temp;
                }
            }
            
            return result;
        }
        
        public String addHelperChar(String s) {
            String result = "$";
            
            for (int i = 0; i < s.length(); i ++) {
                result += "#";
                result += s.charAt(i);
            }
            
            result += "#%";
            
            return result;
        }
    }
    
    9 条回复    2016-03-18 11:25:33 +08:00
    ddmad1030
        1
    ddmad1030  
    OP
       2016-03-17 17:36:56 +08:00
    刚刚在 lintcode 那边 submit 了同样的 code , 然后就 ac 了。。。
    sleeperqp
        2
    sleeperqp  
       2016-03-17 17:53:09 +08:00   ❤️ 1
    public String addHelperChar(String s) {
    String result = "$";

    for (int i = 0; i < s.length(); i ++) {
    result += "#";
    result += s.charAt(i);
    }

    result += "#%";

    return result;
    }
    感觉是这里的问题 string 的+=的效率问题
    bdbai
        3
    bdbai  
       2016-03-17 18:14:54 +08:00 via iPhone
    @sleeperqp 试下用 StringBuilder
    ddmad1030
        4
    ddmad1030  
    OP
       2016-03-17 18:15:54 +08:00
    @sleeperqp 感谢!听了你的意见,把 2 处用 string 直接加的地方全都换成 char[] 然后就通过了!
    ddmad1030
        5
    ddmad1030  
    OP
       2016-03-17 18:19:37 +08:00
    @bdbai 感谢! 我改成用 char[] 运算就通过了,不过 stringbuilder 没有试,估计应该也可以的。
    还是大意了,平时一直都是+= 这样也没出现什么问题,以后得注意了
    bdbai
        6
    bdbai  
       2016-03-17 20:09:49 +08:00 via iPhone   ❤️ 1
    @ddmad1030 StringBuilder 就是专门用来处理字符串拼接的,用起来也很方便,推荐试一下。
    roychan
        7
    roychan  
       2016-03-17 20:19:45 +08:00
    好像 += 确实可能有效率问题
    monkeylyf
        8
    monkeylyf  
       2016-03-18 10:39:40 +08:00
    跑个题 面试的时候你能记住 Manacher 吗 我觉得我的记忆里越来越差了
    ddmad1030
        9
    ddmad1030  
    OP
       2016-03-18 11:25:33 +08:00
    @monkeylyf 面试不复习的话应该也是记不住的 因为平时写 code 根本用不到。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3353 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 10:57 · PVG 18:57 · LAX 02:57 · JFK 05:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.