英文:
consecutive 1 in the array after using at most k 0's
问题
这是LeetCode任务的修改版本。
给定一个二进制数组 nums 和整数 k，如果你可以翻转最多 k 个 0，返回数组中连续 1 的最大数量。
现在我想知道获得最大连续 1 的可能方式。
示例：
输入 1010101
K = 1
可能的组合有：
1110101
1011101
1010111
因此，对于此输入，有 3 种可能的方式，其中最大连续 1 的数量为 3。
约束条件：
输入数组的长度为 1 到 10^5
k 的大小在 0 到数组长度之间
获得最长连续 1 的解决方案是：
public int longestOnes(int[] A, int K) {
int i = 0, j;
for (j = 0; j < A.length; ++j) {
if (A[j] == 0) K--;
if (K < 0 && A[i++] == 0) K++;
}
return j - i;
}
如何获取可能方式的数量。
英文:
This is a modified version of the leetcode task.
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Now I want to know the possible ways to get the maximum number of consecutive 1's
Example:
Input 1010101
K = 1
Possible combinations are :
1110101
1011101
1010111
So there are 3 possible ways where maximum consecutive 1's (111) occurs for this input
Constraints:
length of input array is 1 to 10^5
size of k is 0 to array length
Solution to get the longest consecutive ones is:
public int longestOnes(int[] A, int K) {
int i = 0, j;
for (j = 0; j < A.length; ++j) {
if (A[j] == 0) K--;
if (K < 0 && A[i++] == 0) K++;
}
return j - i;
}
How to get the number of possible ways.
答案1
得分: 3
使用两个指针。每当指针之间有不超过 k 个零时，将前向指针向前移动；否则，将后向指针向前移动。
每当指针之间有不超过 k 个零时，您有一个潜在的解。注意它的长度（指针之间的距离）。如果它是一个新的最大值，那么将实现这个最大值的计数设置为 1 并继续。如果它是当前的最大值，则将实现这个最大值的解的计数加 1。如果两者都不是，则只需继续遍历数组。
示例：我将使用 || 表示两个指针，考虑它们之间的任何内容。
输入 1010101
K = 1
||1010101, 长度 = 0, 最大值 = 0, 计数 = 1
|1|010101, 长度 = 1, 最大值 = 1, 计数 = 1
|10|10101, 长度 = 2, 最大值 = 2, 计数 = 1
|101|0101, 长度 = 3, 最大值 = 3, 计数 = 1
|1010|101, 无效, 最大值 = 3, 计数 = 1
1|010|101, 无效, 最大值 = 3, 计数 = 1
10|10|101, 长度 = 2, 最大值 = 3, 计数 = 1
10|101|01, 长度 = 3, 最大值 = 3, 计数 = 2
10|1010|1, 无效, 最大值 = 3, 计数 = 2
101|010|1, 无效, 最大值 = 3, 计数 = 2
1010|10|1, 长度 = 2, 最大值 = 3, 计数 = 2
1010|101|, 长度 = 3, 最大值 = 3, 计数 = 3
线性时间，常数空间。
英文:
Use two pointers. Advance the forward pointer whenever there are <= k zeroes between the pointers; advance the rear pointer otherwise.
Any time there are <= k zeroes between the pointers, you have a potential solution. Note its length (distance between pointers). If it is a new maximum then set the count that achieves this maximum to 1 and proceed. If it is the current maximum then increment the count of solutions which achieve this maximum by 1. If neither then just proceed through the array.
Example: I'll use || to represent the two pointers, considering anything between them
Input 1010101
K = 1
||1010101, len = 0, max = 0, count = 1
|1|010101, len = 1, max = 1, count = 1
|10|10101, len = 2, max = 2, count = 1
|101|0101, len = 3, max = 3, count = 1
|1010|101, invalid, max = 3, count = 1
1|010|101, invalid, max = 3, count = 1
10|10|101, len = 2, max = 3, count = 1
10|101|01, len = 3, max = 3, count = 2
10|1010|1, invalid, max = 3, count = 2
101|010|1, invalid, max = 3, count = 2
1010|10|1, len = 2, max = 3, count = 2
1010|101|, len = 3, max = 3, count = 3
linear time, constant space.
答案2
得分: 0
以下是翻译好的代码部分：
// 将字符串按照 0 进行分割
string[] b = Console.ReadLine().Split("0");
string[] t = b;
int r = 0;
for (int i = 0; i < t.Length - 1; i++){
// 计算相邻两个 1 块的长度之和
int v = (t[i].Length + t[i+1].Length);
// 更新最大值
r = v > r ? v : r;
}
Console.WriteLine(r + 1);
英文:
The idea is to split the string by 0, then add 2 by 2 the blocks of 1s and get the max value. In c# ...
string[] b = Console.ReadLine().Split("0");
string[] t = b;
int r = 0;
for (int i = 0; i < t.Length-1; i++){
int v = (t[i].Length + t[i+1].Length);
r = v > r ? v : r;
}
Console.WriteLine(r+1);
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论