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

codility 编程题只得 12 分?

  •  
  •   shliujing ·
    shliujing · 2016-09-17 12:41:01 +08:00 · 4490 次点击
    这是一个创建于 2993 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚做的一个公司的在线编程题,简单来说,就是比对两个数组,查看是否能够匹配成同一个单词

    代码是不够精简,不过哪里出问题了,导致分数那么低...

    题目

    Java 代码

    public boolean solution(String S, String T) {
            // write your code in Java SE 8
            int SLength = 0;
            int TLength = 0;
    
            String[] SParts = S.split("[^\\d]+");
            String[] TParts = T.split("[^\\d]+");
    
            for(int i = 0; i < SParts.length; i++) {
                if(!SParts[i].equals("")){
                    SLength += Integer.parseInt(SParts[i]);
                }
            }
    
            for(int i = 0; i < TParts.length; i++) {
                if(!TParts[i].equals("")){
                    TLength += Integer.parseInt(TParts[i]);
                }
            }
    
            for(int i = 0; i < S.length(); i++) {
                if(!Character.isDigit(S.charAt(i))){
                    SLength += 1;
                }
            }
    
            for(int i = 0; i < T.length(); i++) {
                if(!Character.isDigit(T.charAt(i))){
                    TLength += 1;
                }
            }
    
            if(TLength != SLength) {
                return false;
            }
    
            char[] sArray = S.toCharArray();
            char[] tArray = T.toCharArray();
            char[] sArrayFiltered = new char[SLength];
            char[] tArrayFiltered = new char[TLength];
    
            int sIndex = 0;
            int tIndex = 0;
    
            for(int i = 0; i < sArray.length; i++) {
                if(Character.isDigit(sArray[i])) {
                    sIndex += Character.getNumericValue(sArray[i]);
                } else {
                    sArrayFiltered[sIndex] = sArray[i];
                    sIndex++;
                }
            }
    
            for(int i = 0; i < tArray.length; i++) {
                if(Character.isDigit(tArray[i])) {
                    tIndex += Character.getNumericValue(tArray[i]);
                } else {
                    tArrayFiltered[tIndex] = tArray[i];
                    tIndex++;
                }
            }
    
            for (int i = 0; i < SLength; i++) {
                if (sArrayFiltered[i]=='\0' || tArrayFiltered[i]=='\0') continue;
                if (sArrayFiltered[i] != tArrayFiltered[i]) return false;
                return true;
            }
    
            return true;
        }
    

    结果

    8 条回复    2016-09-19 22:40:45 +08:00
    starvedcat
        1
    starvedcat  
       2016-09-17 12:42:50 +08:00
    楼主你是 correctness 只有 12%啊
    shliujing
        2
    shliujing  
    OP
       2016-09-17 12:48:52 +08:00
    @starvedcat run 的时候, 4 个用例都通过了,我才 submit 的。。。略坑。而且写算法时时间有点急,来不及优化了
    guokeke
        3
    guokeke  
       2016-09-17 12:54:20 +08:00 via Android
    算法有疏忽,那不是分。
    shliujing
        4
    shliujing  
    OP
       2016-09-17 12:54:50 +08:00
    找到问题了。
    ![]( http://i4.piimg.com/567571/3b208ecd7bc527b1.png)

    多了这行,导致如果两个字母匹配成功后就跳出;实际情况应该继续往下匹配,因为后面有可能还有不匹配的!

    哎,还是怪自己平时算法写的不多。
    GentleSadness
        5
    GentleSadness  
       2016-09-17 17:41:05 +08:00 via Android
    kmp 算法,如果想写正则表达式, dfa
    wodesuck
        6
    wodesuck  
       2016-09-17 18:44:06 +08:00
    @GentleSadness 跟 kmp 没关系,并不是匹配子串,只是个简单模拟题
    GentleSadness
        7
    GentleSadness  
       2016-09-17 22:53:23 +08:00
    @wodesuck ? kmp 算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。他把前缀和后缀对比,减少了匹配时间
    wodesuck
        8
    wodesuck  
       2016-09-19 22:40:45 +08:00
    @GentleSadness 我知道 kmp 是什么……只是这题不是 kmp
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3753 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 00:51 · PVG 08:51 · LAX 16:51 · JFK 19:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.