柚子快報(bào)邀請(qǐng)碼778899分享：算法(滑動(dòng)窗口四)

http://yzkb.51969.com/

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

? ?

給定一個(gè)字符串?s?和一個(gè)字符串?dāng)?shù)組?words。?words?中所有字符串?長(zhǎng)度相同。

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

例如，如果?words = ["ab","cd","ef"]， 那么?"abcdef"，?"abefcd"，"cdabef"，?"cdefab"，"efabcd"， 和?"efcdab"?都是串聯(lián)子串。?"acdbef"?不是串聯(lián)子串，因?yàn)樗皇侨魏?words?排列的連接。

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

示例 1：

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

輸出：[0,9]

解釋：因?yàn)?words.length == 2 同時(shí) words[i].length == 3，連接的子字符串的長(zhǎng)度必須為 6。

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

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

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

示例 2：

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

輸出：[]

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

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

所以我們返回一個(gè)空數(shù)組。

示例 3：

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

輸出：[6,9,12]

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

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

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

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

算法原理

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

我們把bar?看成一個(gè)a,foo看成一個(gè)b,the看成一個(gè)c

?這個(gè)題的s就可以看成一串 abbacvad

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

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

這道題我們r(jià)ight-left的長(zhǎng)度不能大于words數(shù)組的長(zhǎng)度,即單詞的長(zhǎng)度

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

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

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

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

2.我們的起始位置是right=i,終止位置時(shí)?right+len?每次向后移動(dòng)都是移動(dòng)len的長(zhǎng)度

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

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

然后left+len判斷下一個(gè)單詞

4.當(dāng)count==m?說明此時(shí)正是我們要找的子串,我們輸出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.最小覆蓋子串

??

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

注意：

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

示例 1：

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

輸出："BANC"

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

示例 2：

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

輸出："a"

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

示例 3:

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

輸出: ""

解釋: t 中兩個(gè)字符 'a' 均應(yīng)包含在 s 的子串中，

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

? ?程序解法：

? ? ? 1.暴力解法：通過暴力枚舉，枚舉出所有結(jié)果，然后比對(duì)所有結(jié)果那個(gè)子串最短

? ? ? 2.滑動(dòng)窗口+哈希表

? 算法原理?

這個(gè)題我們依舊用滑動(dòng)窗口來做，并且用數(shù)組來模擬哈希表

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

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

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

int[] hash2=new int[128];

hash1用來存放abc，hash2用來存放長(zhǎng)的字符串

我們來統(tǒng)計(jì)hash1中的個(gè)數(shù)，這里使用統(tǒng)計(jì)個(gè)數(shù)的方式不可取，因?yàn)殚L(zhǎng)的字符串中有可能有多個(gè)一樣的字符，我們就取第一次出現(xiàn)的字符為新的字符,就是取種類的個(gè)數(shù)

for(char ch:t){

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

hash1[ch]++;

}

2.采用滑動(dòng)窗口的方式

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

? ? 我們首先進(jìn)入窗口，進(jìn)窗口之后判斷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++;

然后當(dāng)kind和count相等時(shí)?我們更新結(jié)果，取出當(dāng)前right-left+1的值，和開始的值

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

while(kinds==count){

if(right-left+1

minlen=right-left+1;

begin=left;

}

3.更新完結(jié)果后我們出窗口

??

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);

}

}

柚子快報(bào)邀請(qǐng)碼778899分享：算法(滑動(dòng)窗口四)

http://yzkb.51969.com/

推薦閱讀