美團(tuán)–最長(zhǎng)全1串

文章目錄

• 美團(tuán)--最長(zhǎng)全1串
• • 一、問(wèn)題描述
  • 二、分析
  • 三、代碼

一、問(wèn)題描述

給你一個(gè)01字符串，定義答案=該串中最長(zhǎng)的連續(xù)1的長(zhǎng)度，現(xiàn)在你有至多K次機(jī)會(huì)，每次機(jī)會(huì)可以將串中的某個(gè)0改成1，現(xiàn)在問(wèn)最大的可能答案

• 輸入描述:

輸入第一行兩個(gè)整數(shù)N,K，表示字符串長(zhǎng)度和機(jī)會(huì)次數(shù)第二行輸入N個(gè)整數(shù)，表示該字符串的元素( 1 <= N <= 300000 , 0 <= K <= N )

• 輸出描述:

輸出一行表示答案輸入例子1: 10 2 1 0 0 1 0 1 0 1 0 1輸出例子1: 5

二、分析

這道題和很多題類似：

• 力扣424. 替換后的最長(zhǎng)重復(fù)字符：替換后的最長(zhǎng)重復(fù)字符
• 字節(jié)-字符串翻轉(zhuǎn)：字符串翻轉(zhuǎn)

這幾道題基本上是一樣的，這道題也是：力扣1004. 最大連續(xù)1的個(gè)數(shù) III：最大連續(xù)1的個(gè)數(shù)

• 首先考慮本問(wèn)題的最直觀樸素的想法：枚舉出每一個(gè)子串，逐個(gè)驗(yàn)證其有效性并且更新最大值。
• 這種做法的時(shí)間復(fù)雜度是O(n^3)，在這一數(shù)據(jù)規(guī)模下是一定會(huì)超時(shí)的，超時(shí)的原因是做了非常多重復(fù)的驗(yàn)證計(jì)算，且枚舉了非常多沒(méi)有意義的串
• 那么基于我們?cè)谶@類連續(xù)子數(shù)組性質(zhì)問(wèn)題的經(jīng)驗(yàn)，使用雙指針(滑動(dòng)窗口)會(huì)是一個(gè)非常好的想法
• 雙指針解法
• 雙指針解法的重點(diǎn)在于維護(hù)兩個(gè)指針：
• 設(shè)置兩個(gè)指針(表現(xiàn)為數(shù)組下標(biāo)值)，左指針指向當(dāng)前子串左邊界，右指針指向當(dāng)前子串右邊界，我們通過(guò)某種方法使得左右指針之間的當(dāng)前子串符合要求：即 '0' 的數(shù)目小于等于 K
• 又：我們很容易知道，最長(zhǎng)串一定出現(xiàn)在串內(nèi) '0' 的數(shù)目飽和(如果'0'比較多)或者最大(如果 K 比較大)的情況下，因此我們需要盡可能地把右指針右移
• 那么固定左指針時(shí)，什么情況下可以使右指針右移呢？轉(zhuǎn)化次數(shù)K有剩余 或右指針的下一位是'1'
• 如此移動(dòng)右指針，即可找到每一個(gè)左指針?biāo)鶎?duì)應(yīng)的最長(zhǎng)有效串，而且右指針指向的元素的下一位一定是’0’
• 那么我們可以把每一個(gè)數(shù)組元素作為左指針，以上述方式枚舉出最長(zhǎng)有效串，然后返回結(jié)果
• 但是還是不夠快
• 不夠快的原因還是做了重復(fù)計(jì)算，在左指針變化時(shí)，右指針從左指針處開始右移，沒(méi)有有效利用上一次操作的結(jié)果，造成了大量沒(méi)有必要的操作；那么如何避免重復(fù)計(jì)算呢？
• 我們的關(guān)鍵在于剛剛提到的“0數(shù)飽和”。即：可能成為最長(zhǎng)串的串，它內(nèi)部'0'的數(shù)量一定是飽和或者最大的
• 那么我們可以通過(guò)某種操作來(lái)使得在左指針右移之后，我們立即就能獲得新左指針對(duì)應(yīng)的'0'數(shù)飽和串/'0'數(shù)最大串
• 首先我們考察左指針右移一位時(shí)的情況：
• 首先我們需要清楚一個(gè)事實(shí)：當(dāng)右指針到達(dá)串尾部時(shí)，左指針沒(méi)有任何必要繼續(xù)右移，因?yàn)樽笾羔樣乙频脑捵哟拈L(zhǎng)度一定會(huì)減小，并且飽和性質(zhì)無(wú)法保證
• 也就是說(shuō)，左指針右移的條件是：右指針沒(méi)有觸碰串的右邊界
• 那么我們會(huì)得到一個(gè)推論：當(dāng)左指針需要右移時(shí)，串中的'0'一定是飽和的而不是最大的（“飽和”指子串中0的數(shù)目與K相等，不可以再轉(zhuǎn)化0為1；“最大”指整個(gè)串中所有的0均已被轉(zhuǎn)化為1）既飽和又最大的情況也不需要右移
• 得到這個(gè)推論，我們就可以來(lái)考慮左指針右移時(shí)的情況：
• 當(dāng)前左指針指向的元素是'0'時(shí)：當(dāng)左指針右移時(shí)子串內(nèi)的'0'數(shù)減一，為了維護(hù)其飽和性質(zhì)，我們剛剛提到“右指針指向的元素的下一位一定是'0'”，所以右指針一定可以右移至少一位(如果右移之后的下一位是'1'則可以繼續(xù)右移)
• 當(dāng)前左指針指向的元素是'1'時(shí)：當(dāng)左指針右移時(shí)子串內(nèi)的'0'數(shù)不變，由于我們維護(hù)了每一個(gè)子串的飽和性質(zhì)，右指針不可以右移
• 每一次左指針移動(dòng)及之后右指針移動(dòng)的一系列操作結(jié)束之后，更新最大值。通過(guò)以上的操作，遍歷直到右指針觸碰數(shù)組右邊界，即可得到全局的最大符合條件串的長(zhǎng)度
• 開銷分析
• 平均漸進(jìn)時(shí)間復(fù)雜度O(n)
• 漸近額外空間O(1)

三、代碼

class Solution { public:int longestOnes(vector<int>& A, int K) {//在這個(gè)實(shí)現(xiàn)中，right指的是當(dāng)前子串末尾的下一位int left(0), right(0);int max(0);while (left <= right && right < A.size()) {//如果right沒(méi)有走到結(jié)尾，并且right位置為1（可以直接++）或者//right位置為0（如果k不等于0）那么可以進(jìn)行一次0-》1轉(zhuǎn)變，//繼續(xù)++）while (right < A.size() && (A[right] || K != 0)) {//如果是0，那么k的值需要--if (!A[right]) K--;right++;}//更新結(jié)果max = std::max(right - left, max);//如果left位置為1，只需要left++if (A[left]) left++;//反之代表left位置為0，那么我們需要同時(shí)++else {left++, right++;}}return max;} };

總結(jié)

以上是生活随笔為你收集整理的美团--最长全1串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。