刚做的一个公司的在线编程题,简单来说,就是比对两个数组,查看是否能够匹配成同一个单词。
代码是不够精简,不过哪里出问题了,导致分数那么低...
题目
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; }
结果
![]() | 1 starvedcat 2016-09-17 12:42:50 +08:00 楼主你是 correctness 只有 12%啊 |
2 shliujing OP @starvedcat run 的时候, 4 个用例都通过了,我才 submit 的。。。略坑。而且写算法时时间有点急,来不及优化了 |
![]() | 3 guokeke 2016-09-17 12:54:20 +08:00 via Android 算法有疏忽,那不是分。 |
4 shliujing OP 找到问题了。  多了这行,导致如果两个字母匹配成功后就跳出;实际情况应该继续往下匹配,因为后面有可能还有不匹配的! 哎,还是怪自己平时算法写的不多。 |
![]() | 5 GentleSadness 2016-09-17 17:41:05 +08:00 via Android kmp 算法,如果想写正则表达式, dfa |
![]() | 6 wodesuck 2016-09-17 18:44:06 +08:00 @GentleSadness 跟 kmp 没关系,并不是匹配子串,只是个简单模拟题 |
![]() | 7 GentleSadness 2016-09-17 22:53:23 +08:00 @wodesuck ? kmp 算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。他把前缀和后缀对比,减少了匹配时间 |
![]() | 8 wodesuck 2016-09-19 22:40:45 +08:00 @GentleSadness 我知道 kmp 是什么……只是这题不是 kmp |