算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家聊的问题叫做最长公共前缀 ,我们先来看题面: https:///problems/longest-common-prefix/
题意"" 。样例示例 1: 题解解法一
if(strs.length == 0) { return ""; } int min = Integer.MAX_VALUE; for(String str : strs) { min = Math.min(min, str.length()); } int low = 1; int high = min; while(low <= high) { int middle = (low + high)/2; if(this.isCommontPrefix(strs, middle)) { low = middle + 1; } else { high = middle - 1; } } return strs[0].substring(0, (low + high)/2); } public boolean isCommontPrefix(String[] strs, int length) { String tmp = strs[0].substring(0, length); for (int i=0; i<strs.length; i++) { if(!strs[i].startsWith(tmp)) { return false; } } return true; }
解法二if(strs.length == 0) { return ""; } String result = strs[0]; for(int i=0; i<strs.length; i++) { while(strs[i].indexOf(result) != 0) { result = result.substring(0, result.length()-1); if(result.length() == 0) { return ""; } } } return result; }
解法三
if(strs.length == 0) { return ""; } int min = Integer.MAX_VALUE; for(String str : strs) { min = Math.min(min, str.length()); } int low = 1; int high = min; while(low <= high) { int middle = (low + high)/2; if(this.isCommontPrefix(strs, middle)) { low = middle + 1; } else { high = middle - 1; } } return strs[0].substring(0, (low + high)/2); } public boolean isCommontPrefix(String[] strs, int length) { String tmp = strs[0].substring(0, length); for (int i=0; i<strs.length; i++) { if(!strs[i].startsWith(tmp)) { return false; } } return true; } 今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。 上期推文: |
|