柚子快報邀請碼778899分享：算法(滑動窗口四)

http://yzkb.51969.com/

1.串聯(lián)所有單詞的子串

? ?

給定一個字符串?s?和一個字符串數組?words。?words?中所有字符串?長度相同。

?s?中的?串聯(lián)子串?是指一個包含??words?中所有字符串以任意順序排列連接起來的子串。

例如，如果?words = ["ab","cd","ef"]， 那么?"abcdef"，?"abefcd"，"cdabef"，?"cdefab"，"efabcd"， 和?"efcdab"?都是串聯(lián)子串。?"acdbef"?不是串聯(lián)子串，因為他不是任何?words?排列的連接。

返回所有串聯(lián)子串在?s?中的開始索引。你可以以?任意順序?返回答案。

示例 1：

輸入：s = "barfoothefoobarman", words = ["foo","bar"]

輸出：[0,9]

解釋：因為 words.length == 2 同時 words[i].length == 3，連接的子字符串的長度必須為 6。

子串 "barfoo" 開始位置是 0。它是 words 中以 ["bar","foo"] 順序排列的連接。

子串 "foobar" 開始位置是 9。它是 words 中以 ["foo","bar"] 順序排列的連接。

輸出順序無關緊要。返回 [9,0] 也是可以的。

示例 2：

輸入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

輸出：[]

解釋：因為 words.length == 4 并且 words[i].length == 4，所以串聯(lián)子串的長度必須為 16。

s 中沒有子串長度為 16 并且等于 words 的任何順序排列的連接。

所以我們返回一個空數組。

示例 3：

輸入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

輸出：[6,9,12]

解釋：因為 words.length == 3 并且 words[i].length == 3，所以串聯(lián)子串的長度必須為 9。

子串 "foobarthe" 開始位置是 6。它是 words 中以 ["foo","bar","the"] 順序排列的連接。

子串 "barthefoo" 開始位置是 9。它是 words 中以 ["bar","the","foo"] 順序排列的連接。

子串 "thefoobar" 開始位置是 12。它是 words 中以 ["the","foo","bar"] 順序排列的連接。

算法原理

我們隨便來看一個例子?輸入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

我們把bar?看成一個a,foo看成一個b,the看成一個c

?這個題的s就可以看成一串 abbacvad

這樣這個題就變成一個找出字符串你的異位字符,變成跟我們做的上個題是一樣的

這道題我們要熟練的運用容器以及哈希表和List表

這道題我們right-left的長度不能大于words數組的長度,即單詞的長度

由于我們不確定從哪里開始是我們想要找的單詞的首字母,我們需要遍歷單個單詞的每個字母如下圖所示

我們要對一個單詞遍歷這個單詞的每個字母,所以我們要套兩層for循環(huán)

第一層for循環(huán)就是? ?for(int i=0;i

1.定義left=i,right=i?還需要定義一個count用來記錄單詞的數量定義兩個哈希表,一個哈希表hash1用來記錄words數組里面單詞的個數,一個哈希表hash2用來記錄s表內的單詞,用len表示words單詞的長度

2.我們的起始位置是right=i,終止位置時?right+len?每次向后移動都是移動len的長度

3.我們首先需要進窗口,用in來接受進入窗口的單詞,然后我們判斷進來窗口的單是否在?hash1中存在?存在就count++?

3,當我們一直向后判斷,當right-left的值>words里面字符的m(m表示單詞的個數)*len了?說明此時我們應該出窗口了?在出窗口前我們需要判斷出窗口的單詞是否存在于hash1表中,存在我們就count--

然后left+len判斷下一個單詞

4.當count==m?說明此時正是我們要找的子串,我們輸出left的值

代碼如下

class Solution {

public List findSubstring(String s, String[] words) {

Listret=new ArrayList();

Maphash1=new HashMap();

for(String str:words)hash1.put(str,hash1.getOrDefault(str,0)+1);

int len=words[0].length(),m=words.length;

for(int i=0;i

Maphash2=new HashMap();

for(int left=i,right=i,count=0;right+len<=s.length();right+=len){

String in=s.substring(right,right+len);

hash2.put(in,hash2.getOrDefault(in,0)+1);

if(hash2.get(in)<=hash1.getOrDefault(in,0))count++;

if(right-left+1>len*m){

String out=s.substring(left,left+len);

if(hash2.get(out)<=hash1.getOrDefault(out,0))count--;

hash2.put(out,hash2.get(out)-1);

left+=len;

}

if(count==m){

ret.add(left);

}

}

}

return ret;

}

}

2.最小覆蓋子串

??

給你一個字符串?s?、一個字符串?t?。返回?s?中涵蓋?t?所有字符的最小子串。如果?s?中不存在涵蓋?t?所有字符的子串，則返回空字符串?""?。

注意：

對于?t?中重復字符，我們尋找的子字符串中該字符數量必須不少于?t?中該字符數量。如果?s?中存在這樣的子串，我們保證它是唯一的答案。

示例 1：

輸入：s = "ADOBECODEBANC", t = "ABC"

輸出："BANC"

解釋：最小覆蓋子串 "BANC" 包含來自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

輸入：s = "a", t = "a"

輸出："a"

解釋：整個字符串 s 是最小覆蓋子串。

示例 3:

輸入: s = "a", t = "aa"

輸出: ""

解釋: t 中兩個字符 'a' 均應包含在 s 的子串中，

因此沒有符合條件的子字符串，返回空字符串。

? ?程序解法：

? ? ? 1.暴力解法：通過暴力枚舉，枚舉出所有結果，然后比對所有結果那個子串最短

? ? ? 2.滑動窗口+哈希表

? 算法原理?

這個題我們依舊用滑動窗口來做，并且用數組來模擬哈希表

如圖我們有以下的一個字符串，我們要找的是abc的最小子串，

1.我們給字符串和abc串各創(chuàng)建一個數組

? ??int[]hash1=new int[128];

int[] hash2=new int[128];

hash1用來存放abc，hash2用來存放長的字符串

我們來統(tǒng)計hash1中的個數，這里使用統(tǒng)計個數的方式不可取，因為長的字符串中有可能有多個一樣的字符，我們就取第一次出現(xiàn)的字符為新的字符,就是取種類的個數

for(char ch:t){

if(hash1[ch]==0)kinds++;

hash1[ch]++;

}

2.采用滑動窗口的方式

? ? ? ? 定義left=0，right=0，count=0；

? ? 我們首先進入窗口，進窗口之后判斷hash2[right]==hash1[right]?相等就++?

? ?

int minlen=Integer.MAX_VALUE,begin=-1;

for(int left=0,right=0,count=0;right

char in=s[right];

hash2[in]++;

if(hash1[in]==hash2[in])count++;

然后當kind和count相等時?我們更新結果，取出當前right-left+1的值，和開始的值

int minlen=Integer.MAX_VALUE,begin=-1;

while(kinds==count){

if(right-left+1

minlen=right-left+1;

begin=left;

}

3.更新完結果后我們出窗口

??

char out=s[left];

left++;

if(hash1[out]==hash2[out]) count--;

hash2[out]--;

最后代碼如下

class minWindow {

public String minWindow1 (String ss, String tt) {

char s[]=ss.toCharArray();

char t[]=tt.toCharArray();

int[]hash1=new int[128];

int[] hash2=new int[128];

int kinds=0;

for(char ch:t){

if(hash1[ch]==0)kinds++;

hash1[ch]++;

}

int minlen=Integer.MAX_VALUE,begin=-1;

for(int left=0,right=0,count=0;right

char in=s[right];

hash2[in]++;

if(hash1[in]==hash2[in])count++;

while(kinds==count){

if(right-left+1

minlen=right-left+1;

begin=left;

}

char out=s[left];

left++;

if(hash1[out]==hash2[out]) count--;

hash2[out]--;

}

}

if(begin==-1)return new String();

else return ss.substring(begin,begin+minlen);

}

public static void main(String[] args) {

minWindow minWindow=new minWindow();

String s="ADOBECODEBANC";

String t="AABC";

String result= minWindow.minWindow1(s,t);

System.out.println(result);

}

}

柚子快報邀請碼778899分享：算法(滑動窗口四)

http://yzkb.51969.com/

推薦閱讀