- public class Main {
- public int longestOnes(int[] A, int K) {
- // count 是记录最长的长度
- int count = 0;
- // 如果 K>=A.length 说明 A 所有 0 的位置都可以变成 1
- if (K>= A.length)
- return A.length;
- // 另外
- else
- {//zoreSum 记录 i 遍历 1 到另外一个 1 之后的 0 的数量 //flag 记录第一个滑动窗口的左边位置 , 右边位置为 i
- int zoreSum = 0;
- int flag = 0;
- for (int i = 0; i <A.length; i++) {
- if (A[K] != 1)
- {
- zoreSum++;
- }
- // 如果超过 K 个 0 如 K=3 zoreSum=4 "111"100001->00010"111"1
- //zoreSum =3 的话 还可以连在一起 "111"10001 ->01"111"1
- while (zoreSum> K) {
- if (A[flag] == 0)
- {
- zoreSum--;
- }
- flag++;
- }
- //zoreSum 减到 K 则回复正常
- count = Math.max(count, i - flag + 1);
- }
- }
- return count;
- }
动态规划解法
用两个 for
- public int longestOnes(int[] A, int K) {
- int max = 0;
- int[] cur = new int[K+1];
- for(int i = 0; i <A.length; ++i) {
- for(int j = K; j>= 0; --j) {
- if(A[i] == 1) {
- cur[j]++;
- }
- else {
- if(j == 0) {
- cur[j] = 0;
- }
- else {
- cur[j] = cur[j-1] + 1;
- }
- }
- max = Math.max(max, cur[j]);
- }
- }
- return max;
- }
来源: http://www.bubuko.com/infodetail-3117363.html