一个算法问题，请波波老师帮忙分析下

来源：6-5 BFS和图的最短路径 Perfect Squares

慕工程2559728

2018-09-07

给定一个01字符串，定义答案=该串中最长的连续1的长度，有最多K次机会，可以将字符串中的某个0改为1，问最大可能答案是什么？
输入
字符串长度=10 机会次数k= 2
字符串：1 0 0 1 0 1 0 1 0 1

答案为5

因为可以修改为
1 0 0 1 0 1 1 1 1 1
最长连续1的个数为5

写回答

2回答

liuyubobobo

2018-09-07

已采纳

滑动窗口，找一个最长的窗口包含k个零：）

慕工程2559728

贴错位置了。。

2018-09-07

共3条回复

慕工程2559728

提问者

2018-09-07

public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n = 0;  int k = 0;
		
		String[] s = cin.nextLine().split(" ");
		
		n = Integer.valueOf(s[0]);
		k = Integer.valueOf(s[1]);
		
		String[] str = cin.nextLine().split(" ");
		System.out.println(find(n,k,str));
		
		}

	private static int  find(int n, int k, String[] str) {
		if(k>=n)
			return n;
		int max = 0;
		int l=0;  int r=-1;

		while(r < n-1){
		
			r++;
			if(str[r].equals("0")){
			    --k;
			}
			while(k<0){
			if(str[l].equals("0")){
				k++;
				l++;
			}
			else
				l++;
			}
			
			max = max > r-l+1 ? max :r-l+1;
		}
		return max;
	}

liuyubobobo

自己测试一下试试看：）

2018-09-07

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

查看课程

相似问题

逆波兰问题

回答 1

请问波波老师，一个大型系统算法复杂度问题