有哪些做网站好的公司,如何解决旅游网站建设问题,南昌地宝网最新招聘信息网,wordpress手机mip数据结构–最长公共前缀
方法一#xff1a;
分析
首先找到最小长度的字符串#xff0c;然后把其与每一个与每一个字符串查找索引#xff0c;判断其是不是第一个(索引为0)#xff0c;若其是#xff0c;则计数的加一#xff0c;当计数等于字符数组长度#xff0c;即每个…数据结构–最长公共前缀
方法一
分析
首先找到最小长度的字符串然后把其与每一个与每一个字符串查找索引判断其是不是第一个(索引为0)若其是则计数的加一当计数等于字符数组长度即每个字符串都有则返回该字符串否则最短字符串减1位再执行以上操作
代码
class Solution {public String longestCommonPrefix(String[] strs) {String str;String minStr strs[0];int cnnt 0;for(int i1;istrs.length;i){if(strs[i].length()minStr.length()){minStr strs[i];}}for(int i0;iminStr.length();i){str minStr.substring(0, minStr.length()-i);cnnt 0;for(int j0;jstrs.length;j){cnnt strs[j].indexOf(str)0?cnnt:cnnt;}if(cnntstrs.length){return str;}}return ;方法二:横向查找
分析:
通过调用方法依次比较公共字符串和字符数组里面的每一个元素返回公共部分作为公共字符串 方法是返回两个字符串的公共部分
代码:
class Solution {public String longestCommonPrefix(String[] strs) {if(strs null || strs.length 0){return ;}// 依次遍历字符串数组更新最长公共前缀int length strs.length;String prefix strs[0];for(int i 1; i length; i){prefix calPrefix(prefix, strs[i]);if(prefix.length() 0){return prefix;}//没有字符串就直接返回}return prefix;}public String calPrefix(String str1, String str2){int length Math.min(str1.length(), str2.length());int index 0;for(int i 0; i length; i){if(str1.charAt(i) ! str2.charAt(i)){break;}index;}return str1.substring(0, index);}
}方法三纵向查找
分析
先找到第一个字符串然后依次取出它的每一个字符分别与其它字符串对应位置的字符进行比较 循环结束条件 1.当字符与某个字符串的对应字符不相等时 2.当字符已经到达某个字符串的长度此时返回因为里面的循环结束之后 i 要加1所以是和字符串的length比较 当然 这里for(int j 0; j strs.length; j)的j可以从1开始
代码
class Solution {public String longestCommonPrefix(String[] strs) {if(strs null || strs.length 0){return ;}// 纵向扫描遍历第一个字符串的字符并与其余字符串相应位置的字符比较for(int i 0; i strs[0].length(); i){char c strs[0].charAt(i);for(int j 0; j strs.length; j){if(i strs[j].length() || strs[j].charAt(i) ! c){return strs[0].substring(0, i);}}}return strs[0];}
}方法四分治
分析
代码
class Solution {public String longestCommonPrefix(String[] strs) {if(strs null || strs.length 0){return ;}// 分治return calPrefix(strs, 0, strs.length - 1);}public String calPrefix(String[] strs, int start, int end){if(start end){return strs[start];}int mid start (end - start) / 2;String left calPrefix(strs, start, mid);String right calPrefix(strs, mid1, end);return doCal(left, right);}public String doCal(String str1, String str2){int length Math.min(str1.length(), str2.length());int index 0;for(int i 0; i length; i){if(str1.charAt(i) ! str2.charAt(i)){break;}index;}return str1.substring(0, index);}
}方法五二分查找
分析
代码
// 最短字符串的字符数 minLengthint minLength Integer.MAX_VALUE;for(int i 0; i strs.length; i){minLength Math.min(minLength, strs[i].length());}// 在 0 - minLength 区间内进行二分查找int start 0, end minLength;while(start end){int mid (end - start 1) / 2 start;if(isPrefix(strs, mid)){start mid;}else{end mid - 1;}}return strs[0].substring(0, start);}public boolean isPrefix(String[] strs, int length){String str0 strs[0].substring(0, length);for(int i 0; i strs.length; i){String str strs[i];for(int j 0; j length; j){if(str0.charAt(j) ! str.charAt(j)){return false;}}}return true;}
}
