資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的連續 1 最長長度 III
假設我們有一個由 0 和 1 組成的陣列 A，我們最多可將 k 個值從 0 更新為 1。我們必須找到僅包含 1 的最長（連續）子陣列的長度。因此，如果 A = [1,1,1,0,0,0,1,1,1,1,0] 且 k = 2，則輸出將為 6，那麼如果我們翻轉 2 個 0，該陣列可以類似於 [1,1,1,0,0,1,1,1,1,1,1]，最長的 1 序列的長度是 6。
為了解決此問題，我們將按照以下步驟執行操作 −
- 設定 ans := 0，j := 0 且 n := 陣列的大小
- 對 i 在範圍 0 到 n – 1 之間
- 如果 A[i] 是 0，則將 k 減少 1
- while j <= i 且 k < 0
- 如果 A[j] = 0，則將 k 增加 1
- 將 j 增加 1
- ans := i – j + 1 的最大值，ans
- 返回 ans
讓我們檢視以下實現以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestOnes(vector<int>& A, int k) {
int ans = 0;
int j = 0;
int n = A.size();
for(int i = 0; i < n; i++){
if(A[i] == 0) k--;
while(j <= i && k <0){
if(A[j] == 0){
k++;
}
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {1,1,1,0,0,0,1,1,1,1,0};
Solution ob;
cout <<(ob.longestOnes(v, 3));
}輸入
[1,1,1,0,0,0,1,1,1,1,0] 3
輸出
10
更新於: 2020 年 4 月 30 日
479 次瀏覽
廣告