日韩国产精品99成人不卡在线无毒|狠狠躁夜夜爽一级二级精品|亚洲日日噜噜孕妇中文字幕|日韩久草中文三级片

新聞動態(tài)

leetcode必備算法:聊聊滑動窗口

常見問題 發(fā)布者:ou3377 2021-12-10 09:03 訪問量:297

前言

我們刷leetcode的時候,經常會遇到滑動窗口類型題目?;瑒哟翱趩栴}非常經典,也很有技巧性,一般大廠也喜歡問。今天跟大家一起來學習滑動窗口的套路,文章如果有不正確的地方,歡迎大家指出哈,感謝感謝~

  • 什么是滑動窗口?
  • 一道算法題走進滑動窗口
  • 滑動窗口可以用來解決哪些問題?
  • 滑動窗口框架套路
  • leetcode案例分析

什么是滑動窗口

滑動窗口這個詞,相信大家耳熟能詳啦。因為說到TCP的時候,經常談起滑動窗口協(xié)議(Sliding Window Protocol),它是TCP協(xié)議的一種應用,用于網絡數(shù)據傳輸時的流量控制,以避免擁塞的發(fā)生。

TCP頭部有個字段叫win,也即那個16位的窗口大小,它告訴對方本端的TCP接收緩沖區(qū)還能容納多少字節(jié)的數(shù)據,這樣對方就可以控制發(fā)送數(shù)據的速度,從而達到流量控制的目的。

TCP的滑動窗口在某一個時刻就是固定窗口大小的滑動窗口,隨著網絡流量等因素改變窗口大小也會隨著改變。算法中的滑動窗口有點類似,就是維護一個窗口(隊列/數(shù)組),不斷滑動,然后更新答案。滑動窗口,指的是這樣一類問題的求解方法,在數(shù)組上通過雙指針同向移動而解決的一類問題。

一個例子走進滑動窗口算法

我們來看一道算法題吧:給定一個整數(shù)數(shù)組,計算長度為k的連續(xù)子數(shù)組的最大總和。

輸入:arr [] = {100,200,300,400}  k = 2

輸出:700

解釋:300 + 400 = 700

看到這個題目,我們馬上想到暴力法去解決了,兩個for搞定:

   public int maxSum(int[] arry, int k) {
        int size = arry.length;
        int maxSum = 0;

        for (int i = 0; i < size - k + 1; i++) {
            int currentSum = 0;
            for (int j = 0; j < k; j++) {
                currentSum = currentSum + arry[i + j];
            }

            maxSum = Math.max(currentSum, maxSum);
        }

        return maxSum;
    }

暴力法用了兩個嵌套的for循環(huán),時間復雜度不理想,為O(k*n)而滑動窗口算法可以解決嵌套循環(huán)問題,有效降低時間復雜度。

因為滑動窗口就是維護一個窗口,不斷滑動,然后更新答案。 我們用滑動窗口算法來走一波:

當k=2時,

  • 我們可以維護一個長度為2的窗口,初始化第一個窗口值的總和,并保存起來
  • 然后窗口不斷向右滑動,滑動過程中,與保存的最大值比較,并更新答案。
  • 窗口直到滑到最右邊才結束。

當k=3時,類似的

  • 我們可以維護一個長度為3的窗口,初始化第一個窗口值的總和,并保存起來
  • 然后窗口不斷向右滑動,滑動過程中,與保存的最大值比較,并更新答案。
  • 窗口直到滑到最右邊才結束。

于是,我們就可以寫代碼啦:

   public int maxSum1(int[] arry, int k) {
        int size = arry.length;

        if (size < k) {
            return -1;
        }

        //初始化第一個窗口值的總和
        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum = maxSum + arry[i];
        }

        int sum = maxSum;
        for (int i = k; i < size; i++) {
            sum = sum + arry[i] - arry[i - k];
            maxSum = Math.max(maxSum,sum);
        }

        return maxSum;
    }

使用了滑動窗口,時間復雜度,只需要O(n)就可以解決啦。

滑動窗口可以解決哪些問題

哪些leetcode的題目,我們可以用滑動窗口去解決呢?

一般情況,子串問題,如什么最小覆蓋子串、長度最小的子數(shù)組等等,都可以考慮使用滑動窗口算法。比較經典的滑動窗口題目有這些:

  • 無重復字符的最長子串
  • 最小覆蓋子串
  • 串聯(lián)所有單詞的子串
  • 至多包含兩個不同字符的最長子串
  • 長度最小的子數(shù)組
  • 滑動窗口最大值
  • 字符串的排列
  • 最小窗口子序列

都是leetcode的原題,大家可以去leetcode官網找找手感哈。

滑動窗口框架套路

滑動窗口的大致邏輯框架,偽代碼如下:

int left =0,right = 0;
while (right < s.size()){
  //增大窗口
  window.add(s[right]);
  right++;
  
  while (window needs shrink){
    //縮小窗口
    window.remove (s[left]);
    left ++;
  }
}

基本流程就是醬紫:

  • 首先呢,就是獲取原字符串的長度。
  • 接著維護一個窗口(數(shù)組、哈希、隊列)
  • 窗口一步一步向右擴展
  • 窗口在向右擴展滑動過程,需要判斷左邊是否需要縮減
  • 最后比較更新答案

我們用這個框架,嘗試去解一道leetcode的真題吧。

題目:給定一個字符串 s ,請你找出其中不含有重復字符的最長子串的長度。

實例1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc",所以其長度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b",所以其長度為 1。

因為需要判斷是否存在重復字符,所以,我們用一個哈希集合(HashSet)來作為窗口

int lengthOfLongestSubstring(String s){
     //獲取原字符串的長度
     int len = s.length();
     //維護一個哈希集合的窗口
     Set<Character> windows = new HashSet<>();
     int left=0,right =0;
     int res =0;

     while(right<len){
       char c = s.charAt(right);
       //窗口右移
       right++;

       //判斷是否左邊窗口需要縮減,如果已經包含,那就需要縮減
       while(windows.contains(c)){
          windows.remove(s.charAt(left));
           left++;
       }
       windows.add(c);
       //比較更新答案
       res = Math.max(res,windows.size());
      }
     return res;
}

leetcode案例分析

我們再來看一道leetcode真題,加深一下印象哈。

題目:給你一個字符串S、一個字符串T。返回S中涵蓋T所有字符的最小子串。如果S中不存在涵蓋T所有字符的子串,則返回空字符串 "" 。

實例1:

輸入:s = "ADOBECODEBANC", t = "ABC"
輸出:"BANC"

實例2:

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

我們還是套用這個框架流程:

- 首先呢,就是獲取原字符串的長度。
- 接著維護一個窗口(數(shù)組、哈希、隊列)
- 窗口一步一步向右擴展
- 窗口在向右擴展滑動過程,需要判斷左邊是否需要縮減
- 最后比較更新答案

獲取原字符串的長度。

這個比較簡單,因為原題還是需要有左右指針去遍歷字符串S的。

int len = S.length();

接著維護一個窗口(數(shù)組、哈希、隊列)、右移、左邊縮減

我們可以先定義一個最小的窗口,長度為0。定義窗口時,我們得想下:窗口什么時候右移,什么時候左邊縮減,怎么比較更新答案。

最小的窗口什么時候可以右移呢?因為題目要求涵蓋T的所有子串,所以,窗口一開始就可以右移,直到包含T的所有字母

圖片

顯然,窗口字符串ADOBEC,是S中涵蓋T所有字符的第一個子串。但是呢,我們要找的是最小子串,ADOBEC還不一定是最小的。因為:

  • 1.當前窗口可能包含一個滿足題目條件的,更小的子窗口字符串。(可以左邊縮減)
  • 2.窗口還沒滑到的地方,可能包含一個滿足條件的,更小的字符串。(可以窗口繼續(xù)右移)

找到第一個滿足條件的窗口字符串ADOBEC后,為了尋找更小的子窗口字符串。我們可以:

  • 1.左邊縮減,如果縮小的窗口仍然滿足包含T所有字母,那當前窗口就可能是最小子串。存儲下來(就類似于滑動窗口框架的更新答案哈),然后繼續(xù)從左縮減窗口。
  • 2.如果縮小窗口不能滿足包含T的所有字母,這時候就可以停止窗口的左邊縮減,轉而向右擴大窗口啦。

圖片窗口先左邊縮減,再右移動,保存滿足條件的窗口

不斷重復以上的步驟,把找到滿足條件的窗口保存下來,比較得出最小的子串。示例滿足條件的最小子串是BANC

圖片

這道題的難點,其實是如何判斷S的子串包含T,我們一起來看下代碼吧:

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || s.length() < t.length()) {
            return "";
        }

        int sLen = s.length();
        Map<Character, Integer> lookup = new HashMap<>();
         
        for (int i = 0; i < sLen; i++) {
            lookup.put(s.charAt(i), 0);
        }

        for (int i = 0; i < t.length(); i++) {
            Character c = t.charAt(i);
            if (lookup.containsKey(c)) {
                lookup.put(c, lookup.get(c) + 1);
            } else {
                return "";
            }
        }

        int left = 0;
        int right = 0;
        int minLen = Integer.MAX_VALUE;
        int tCount = t.length();
        String result = "";
        while (right < sLen) {
            char c = s.charAt(right);
            if (lookup.get(c) > 0) tCount--;
            lookup.put(c, lookup.get(c) - 1);
            //窗口右移
            right++;
            
            //已經包含T的所有字母
            while (tCount == 0) {
                //比較更新答案
                if (minLen > right - left) {
                    minLen = right - left;
                    result = s.substring(left, right);
                }
                char c2 = s.charAt(left);
                if (lookup.get(c2) == 0) tCount++;
                lookup.put(c2, lookup.get(c2) + 1);
                //窗口從左邊縮減
                left++;
            }
        }
        return result;
    }
}

leetcode提交結果如下:

圖片

文章源自“撿田螺的小男孩


關鍵字: leetcode 滑動窗口

文章連接: http://www.hsjyfc.com.cn/cjwt/796.html

版權聲明:文章由 晨展科技 整理收集,來源于互聯(lián)網或者用戶投稿,如有侵權,請聯(lián)系我們,我們會立即刪除。如轉載請保留