不卡超碰,亚洲婷婷综合网,性情网站,豆花视频在线一区二区在线视频 ,91精品成人网,日本最新三级理论无码电影,天天操天天射天天好逼网,一级片乱伦

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做最長公共前綴?，我們先來看題面：

https://leetcode-cn.com/problems/longest-common-prefix/

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

題意

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串?""。

樣例

示例?1:

輸入: ["flower","flow","flight"]
輸出: "fl"
示例?2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

題解

解法一

這種解法是暴力循環(huán)法，從題目可知：最長公共前綴的最長長度一定是字符串?dāng)?shù)組中長度最短哪個(gè)字符串。

首先找出長度最短的字符串str，加入str="abcf"。
依次對(duì)'abcf'、'abc'、'ab'、'a'進(jìn)行篩選，判斷哪個(gè)是所有其他字符串的前綴。

public?String longestCommontPrefix6(String[] strs)?{
????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????????if(!strs[i].startsWith(tmp)) {
????????????return?false;
????????}
????}
????return?true;
}

解法二

這種方法稱之為水平掃描法，用一張圖來表示其具體過程如下：

首先假設(shè)最長前綴result=str[0], 遍歷字符串?dāng)?shù)組，依次與result做比較，找出其最長前綴，然后更新result，再進(jìn)行下一次比較。

public?String?longestCommonPrefix3(String[] strs) {
????if(strs.length == 0) {
????????return?"";
????}
????String?result = strs[0];
????for(int i=0; i????????while(strs[i].indexOf(result) != 0) {
????????????result = result.substring(0, result.length()-1);
????????????if(result.length() == 0) {
????????????????return?"";
????????????}
????????}
????}
????return?result;
}

解法三

利用二分法的思想

找出最短的字符串記為m;
對(duì)字符串m進(jìn)行二分,分割點(diǎn)記為mid，用tmp表示m[low...high]。
如果tmp為所有字符串的前綴，則mid右移，否則左移，直到low>high。
代碼如下：

public?String longestCommontPrefix6(String[] strs)?{
????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????????if(!strs[i].startsWith(tmp)) {
????????????return?false;
????????}
????}
????return?true;
}