首页 > 代码库 > Coursera OA,面经整理
Coursera OA,面经整理
1.Approximate matching
//to do 有没有比暴力方法更简洁的办法?
枚举pre的开始位置,相等的话,while循环找到local max
枚举post的结尾位置(从后往前),while循环找local max
注意循环的控制条件和index
1 private static String approximateMatch(String pre, String middle, String post) { 2 int preSize = pre.length(); 3 int middleSize = middle.length(); 4 int postSize = post.length(); 5 int preVal; //indicate the max length in pre 6 int postVal;//indicate the max length in post 7 int preIndex = 0; //the start index of maxPre string 8 int postIndex = 0;// the end index of max post string 9 10 //initialization11 int GobalMax = 0;12 int LocalMax = 0;13 int start = 0;14 15 //get preVal 16 for (;start < preSize ; start++) {17 LocalMax = 0;18 while ( start + LocalMax < preSize && LocalMax < middleSize && middle.charAt(LocalMax) == pre.charAt(start + LocalMax)) { 19 LocalMax++;20 }21 if (LocalMax > GobalMax) {22 GobalMax = LocalMax;23 preIndex = start;24 }25 26 if (GobalMax > preSize - start) {27 break;28 }29 }30 preVal = GobalMax; 31 32 //initialization for right part33 int end = postSize - 1;34 GobalMax = 0;35 int midEnd = middleSize - 1;36 //get postVal37 for (; end >= 0; end--) {38 LocalMax = 0;39 40 while (end - LocalMax >= 0 && LocalMax < middleSize 41 && middle.charAt(midEnd - LocalMax) == post.charAt(end - LocalMax)) {42 LocalMax++;43 }44 if (LocalMax > GobalMax) {45 GobalMax = LocalMax;46 postIndex = end + 1;47 }48 49 if (GobalMax > end) {50 break;51 }52 }53 postVal = GobalMax;54 55 //return result string56 if (preVal + postVal >= middleSize) {57 return middle;58 } else {59 return pre.substring(preIndex, preVal + preIndex) + post.substring(postIndex - postVal, postIndex);60 }61 }
------------------------------------------------我是分割线----------------------
Coursera OA,面经整理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。