中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

leetcode如何實現最小覆蓋子串

發布時間:2021-12-16 09:32:29 來源:億速云 閱讀:136 作者:小新 欄目:大數據

這篇文章主要為大家展示了“leetcode如何實現最小覆蓋子串”,內容簡而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領大家一起研究并學習一下“leetcode如何實現最小覆蓋子串”這篇文章吧。

給定一個字符串 S 和一個字符串 T,請在 S 中找出包含 T 所有字母的最小子串。

示例:

輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"

說明:

  • 如果 S 中不存這樣的子串,則返回空字符串 ""

  • 如果 S 中存在這樣的子串,我們保證它是唯一的答案。

解題思路:

1,用hashmap存儲s和t中字符出現的次數

2,移動右指針,對于s中的每個字符,如果出現在t中,且s中出現的次數不大于t中出現的次數,說明我們找到了一個匹配字符,記錄下來fund

3,如果found和t的長度相同,說明找到了解

A,包含t中所有字符

B,包含了部分重復字符(沒有記錄到fund中),說明,有些字符在s中出現的頻率大于t中出現的頻率

4,如果左指針對應字符在s中頻率大于t中的頻率,則應該舍棄這個字符,即移動左指針,調整對應次數

5,如果次數和t中相等,說明我們找到了一個局部最優解,記錄下來

6,右移左指針,并且減少fund,尋找下一個局部最優解。

func minWindow(s string, t string) string {    src:=make(map[byte]int)    dst:=make(map[byte]int)    for i:=0;i<len(t);i++{        dst[t[i]]++    }    start:=0    found:=0    min:=len(s)    begin:=-1    for end:=0;end<len(s);end++{      src[s[end]]++        if src[s[end]]<=dst[s[end]]{            found++        }        if found==len(t){            for start<end && src[s[start]]>dst[s[start]]{                src[s[start]]--                start++            }            if end-start<min{                min=end-start                begin=start            }            src[s[start]]--            start++            found--        }    }    if begin==-1{        return ""    }    return string(s[begin:begin+min+1])}

以上是“leetcode如何實現最小覆蓋子串”這篇文章的所有內容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內容對大家有所幫助,如果還想學習更多知識,歡迎關注億速云行業資訊頻道!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

平远县| 宁波市| 张家川| 元氏县| 汶川县| 二连浩特市| 万安县| 榕江县| 冷水江市| 邵阳市| 庆云县| 天台县| 土默特右旗| 济阳县| 孝义市| 舟曲县| 北流市| 阜城县| 崇信县| 安吉县| 噶尔县| 克东县| 德江县| 元朗区| 鄂尔多斯市| 资阳市| 永登县| 丹阳市| 鲁山县| 温泉县| 保定市| 禹城市| 新津县| 清徐县| 广水市| 孟州市| 天峨县| 铜梁县| 栾城县| 桑日县| 德惠市|