在仅包含 1 和 0 的 String
中查找最大的 1 和 0 交替子序列。还要找到最大子序列的起始索引。
示例:
对于1101011,最长的交替子序列长度为5,从索引1到5。
我尝试通过比较连续的元素来做到这一点,如果它们不相等,则将当前长度与最大大小进行比较:
int findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex = 0;
int endindex = 0;
int j = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] != arr[i+1] && maxsize < i - j + 1) {
maxsize = i - j + 1;
startindex = j;
} else {
j = i;
}
}
endindex = startindex+maxsize-1;
if (maxsize == -1)
System.out.println("No such subarray");
else
System.out.println(startindex+" to "+endindex);
return maxsize;
}
测试方法:
int [] ia = {1, 1, 0, 1, 0, 1, 1};
findSubArray (ia, 7);
返回:5 并打印 0 到 4
问题是虽然它打印了正确的长度,即 5,但索引不正确。正确的输出应该是 1 到 5。
为了纠正这个问题,如果我执行 j = i + 1
,那么整个匹配将进行一次折腾,我得到的索引为 0 到 0。
上面的代码有什么错误?此外,任何替代方法的伪代码都会有所帮助。
最佳答案
您将 j = i;
更改为 j = i + 1;
是正确的,但这还不够。
您缺少的是当前交替序列从 j
开始并在 i+1
结束,而不是 i
。
另外,你的条件逻辑有问题。您的 else 子句应该仅在当前交替序列结束时到达(即 arr[i] == arr[i+1]
),但当当前序列不长于最大值时也会到达顺序。
因此条件应该分为两个条件:
if (arr[i] != arr[i+1]) {
if (maxsize < i + 1 - j + 1) {
maxsize = i + 1 - j + 1;
startindex = j;
}
} else {
j = i + 1;
}
关于java - 字符串中 1 和 0 的最大交替子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48801099/