codility 编程题只得 12 分?

2016-09-17 12:41:01 +08:00
 shliujing

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

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

题目

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

结果

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

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

哎,还是怪自己平时算法写的不多。
GentleSadness
2016-09-17 17:41:05 +08:00
kmp 算法,如果想写正则表达式, dfa
wodesuck
2016-09-17 18:44:06 +08:00
@GentleSadness 跟 kmp 没关系,并不是匹配子串,只是个简单模拟题
GentleSadness
2016-09-17 22:53:23 +08:00
@wodesuck ? kmp 算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。他把前缀和后缀对比,减少了匹配时间
wodesuck
2016-09-19 22:40:45 +08:00
@GentleSadness 我知道 kmp 是什么……只是这题不是 kmp

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/306734

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX