最高连续性
程序员文章站
2024-03-19 22:19:22
...
问题描述:给定数组A,A是元素为0或者1的数组,我们可以更改K个数组中的0,求数组中最大连续子数组的长度。
例子:
算法思路:从0开始依次遍历数组,当某个元素为0的时候将其转换为1,由于我们最终只要求解这个最大连续子数组的长度,因此这里 可以用K-1来表示元素从0转换为1。如果为1,则K不变化。接着要用另外一个变量来记录整体最长子数组的起始位置,即当数组在遍历数组元素到底是0还是1的时候,这个子数组的其实位置也在发生变化,这个子数组整体的在发生变化。
如上面的例子。K=2,当j=3的时候,A[j]=0,这时K--,K=1,当j=4的时候,A[j]=0,K=0,而当j=5,A[j]=10,K--,K=-1,这时相当于把这个位置的0换成了1,表面是违背了题目,但如果将这个最长子数组的起始位置向后移一位,即开始的位置是0,现在将其位置变为1,然后这个最长子数组的长度就是j-i+1,这个就是这个最长子数组的长度了。而当初始的位置为1的时候,表明舍去了一个将0变为1的机会,因此当K<0并且这个起始位置的元素为0的时候,这个K就要加1。这个起始位置只要是当K<0了就要加1。最后j每变化一个就和上一次的最大值进行比较,最终返回这个最大值就OK了。
代码示例:
public int longestOnes(int[] A, int K) {
int res=0;
int i=0;
for(int j=0;j<A.length;j++)
{
if(A[j]==0)
K--;
if(K<0&&A[i++]==0)
K++;
res=Math.max(res,j-i+1);
}
return res;
}
}
代码来源思想源自以为大佬,开始还真没想出来,看了半天源码才想出来。。。。。。在博客上面积累。。。。。。。
推荐阅读
-
最高连续性
-
linux 下取进程占用 cpu/内存 最高的前10个进程 博客分类: LINUX
-
Java总结05 Java集合体系.最高集合接口Collection和其迭代器/一般集合接口List和其迭代器/增强版For循环的应用
-
956 最高的广告牌
-
mou年电影国内票房最高的演员是谁
-
揭秘新岸线全球最高频ARM处理器 应用服务器中国移动三星WindowsAndroid
-
mysql一个表存多少数据才是性能最高的 博客分类: WebHibernate其他Ibatis3 mysqldbibatishibernate
-
mysql一个表存多少数据才是性能最高的 博客分类: WebHibernate其他Ibatis3 mysqldbibatishibernate
-
为什么《百家讲坛》上的中学教师收视率最高? 博客分类: 无益 生活ASP.net旅游BlogASP
-
为什么《百家讲坛》上的中学教师收视率最高? 博客分类: 无益 生活ASP.net旅游BlogASP