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

Question

给定一个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

Answer 1

liuyubobobo 2018-09-07 14:54:10

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

• 提问者 慕工程2559728 #1

  非常感谢！

• 提问者 慕工程2559728 #2

  这是我根据您的思路写的代码，这么写对吗？
  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;
  	}

• 提问者 慕工程2559728 #3

  贴错位置了。。

Answer 2

提问者 慕工程2559728 2018-09-07 16:08: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 #1

  自己测试一下试试看：）