第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請及時(shí)綁定郵箱和手機(jī)立即綁定

滑動(dòng)窗口算法在算法面試題中的應(yīng)用

標(biāo)簽:
算法 面試

试想有这样一道题, 怎么解决?
题目描述:
给定两个字符串s和t, 找到s中包含所有t中字母的最短字符串组合。

举例:
输入: S = “ADOBECODEBANC”, T = "ABC"
输出: “BANC”

这个时候就要用到滑动窗口算法,滑动窗口算法广泛应用于网络协议等,其实滑动窗口算法是一种思路,可以解决很多问题。

下面详细讲解下这个算法的步骤:

  1. 设定两个指针,left和right,表示一个滑动的窗口之最左端和最右端。
    初始,这两个指针指向S的第一个字符
  2. left不动,right来向右移动,直到找到一个字符串能匹配T串,便是当前能match的字符串。
  3. 这个时候,我们一个一个的右移动left,同时每右移动一次left,我们再通过右移动right来找match的字符串,如果能找到,且比当前串短,update。如果找不到,继续右移动left。

下面举例说明一下:

  1. left=0, right=0;ADOBECODEBANC

  2. 移动right, 找到第一个match的字符串: 图片描述

  3. 右移动left一步,一直移动right,找到match字符串,但是更长,不更新, 图片描述

  4. 继续右移动left一位,
    图片描述

  5. 最后找到了最短字符串BANC

同样的思路可以解决如下问题:
A. 给定一个字符串s和一个非空字符串p,在s中找到p字谜的所有开始索引。
s: “cbaebabacd” p: “abc” 输出[0,6]

B. 给定一个字符串,查找不重复字符的最长子字符串的长度。

left=0,right=0;
图片描述

欢迎留言交流!

點(diǎn)擊查看更多內(nèi)容
1人點(diǎn)贊

若覺得本文不錯(cuò),就分享一下吧!

評(píng)論

作者其他優(yōu)質(zhì)文章

正在加載中
感謝您的支持,我會(huì)繼續(xù)努力的~
掃碼打賞,你說多少就多少
贊賞金額會(huì)直接到老師賬戶
支付方式
打開微信掃一掃,即可進(jìn)行掃碼打賞哦
今天注冊有機(jī)會(huì)得

100積分直接送

付費(fèi)專欄免費(fèi)學(xué)

大額優(yōu)惠券免費(fèi)領(lǐng)

立即參與 放棄機(jī)會(huì)
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)

舉報(bào)

0/150
提交
取消