数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告