最長重復(fù)子數(shù)組 findLength

默認(rèn)格式：

class Solution {
    public int findLength(int[] A, int[] B) {
    }
}

解題思路：

1，暴力算法

遍歷數(shù)組1中的每一個元素

用這個元素和數(shù)組2的每一個元素對比，如果相同

循環(huán)讀取兩個數(shù)組的下一個元素，直到不相同為止

這個算法太復(fù)雜，就不做實現(xiàn)了。

2，使用哈希表+鏈表

遍歷一遍數(shù)組1，將其每個元素出現(xiàn)的位置存入到一個List中，然后存入hashmap中。

遍歷數(shù)組2，每個元素在哈希表中是否存在，如果存在，遍歷這個List中的所有位置，對這些位置進行測試，找出最大長度

寫的時候已經(jīng)發(fā)現(xiàn)了，用哈希表來存并沒有減少核心部分的時間，時間復(fù)雜度依然很高。

    public int findLength(int[] A, int[] B) {
        int max=0;
        //構(gòu)建一個HashMap來存地址
        HashMap<Integer, List<Integer>> map=new HashMap<>();
        for (int i=0;i<A.length;i++){
            if (map.get(A[i])==null){
                List<Integer> list=new LinkedList<>();
                list.add(i);
                map.put(A[i],list);
            }else {
                map.get(A[i]).add(i);
            }
        }
        for (int i=0;i<B.length;i++){
            //如果元素在數(shù)組A中存在
            if (map.get(B[i])!=null){
                //遍歷原數(shù)組中對應(yīng)的每一個位置
                for(int index:map.get(B[i])){
                    int a=index,b=i;
                    for (;a<A.length&&b<B.length&&A[a]==B[b];a++,b++){
                    }
                    max=Integer.max(max,b-i);
                }
            }
        }
        return max;
    }

優(yōu)化1：（失?。?/h3>

這個HashMap可以使用數(shù)組來代替，因為他里面的值不會超過100，我們可以對其進行控制，用數(shù)組下標(biāo)來代替HashMap的鍵的功能。

    public int findLength(int[] A, int[] B) {
        int max=0;
        //使用數(shù)組來存
//        HashMap<Integer, List<Integer>> map=new HashMap<>();
        List<Integer>[] lists=new ArrayList[100];
        for (int i=0;i<A.length;i++){
            if (lists[A[i]]==null){
                List<Integer> list=new ArrayList<>();
                list.add(i);
                lists[A[i]]=list;
            }else {
                lists[A[i]].add(i);
            }
        }
        for (int i=0;i<B.length;i++){
            //如果元素在數(shù)組A中存在
            if (lists[B[i]]!=null){
                //遍歷原數(shù)組中對應(yīng)的每一個位置
                for(int index:lists[B[i]]){
                    int a=index,b=i;
                    for (;a<A.length&&b<B.length&&A[a]==B[b];a++,b++){
                    }
                    max=Integer.max(max,b-i);
                }
            }
        }
        return max;
    }

優(yōu)化2：

還是數(shù)據(jù)結(jié)構(gòu)上的優(yōu)化，我們可以使用Set來代替List，這樣可以節(jié)省一些時間

優(yōu)化到這我覺得應(yīng)該是我做題的方向錯了，應(yīng)該有一個巧妙的方法能夠解決這個問題但是我目前沒有想到，看看官方的解答吧。

官方的解題方法有多種，我這里就選擇最巧妙的那一個方式：動態(tài)規(guī)劃。

動態(tài)規(guī)劃的題目之前做過很多，但是對這個概念的理解還不夠深刻，還需要多多練習(xí)。

動態(tài)規(guī)劃的核心思想就是，一邊計算一邊記錄，并且得到的結(jié)果會累計，最后我們累計的結(jié)果就是我們需要的值。

在這道題中，我們?nèi)〕鰯?shù)組A中的一個元素，和B中每個元素比較一遍，如果相等，這能證明什么，這就證明，如果A中這個元素的前一個和B中當(dāng)前元素的前一個相等，此時這個連續(xù)的長度就+1。

用這個結(jié)論，我們可以遍歷兩個數(shù)組，構(gòu)建一個a*b的二維數(shù)組，假設(shè)A種當(dāng)前元素地址是a1，B中當(dāng)前元素的地址是b1，那么當(dāng)前的長度可以加上(a1-1,b1-1)這個位置的元素的值。

雖然實現(xiàn)了，但不是最優(yōu)的辦法，官方給出的最優(yōu)算法有一些復(fù)雜，沒能看懂

public int findLength(int[] A, int[] B) {
    int[][] map=new int[A.length][B.length];
    int max=0;
    for (int i=0;i<A.length;i++){
        for (int j=0;j<B.length;j++){
            if (A[i]==B[j]){
                if (i-1<0||j-1<0)
                    map[i][j]=1;
                else
                    map[i][j]=map[i-1][j-1]+1;
                max=Integer.max(max,map[i][j] );
            }
        }
    }
    return max;
}

到此這篇關(guān)于最長重復(fù)子數(shù)組 findLength示例詳解的文章就介紹到這了,更多相關(guān)最長重復(fù)子數(shù)組 findLength內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論