首页 > 代码库 > 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     }
Approximate matching

 

------------------------------------------------我是分割线----------------------

 

Coursera OA,面经整理