给定一个长度为 N(最多 10^5)的字符串,它仅由 0 和 1 组成。我们必须从原始字符串中删除长度正好为 K 的两个子字符串,以最大化连续 1 的数量。
例如假设字符串是 1100110001 并且 K=1。
所以我们可以删除两个长度为 1 的子字符串。这里最好的选择是删除第 3 位和第 4 位的 0,并得到输出 4(因为新字符串将是 11110001)
如果我尝试暴力破解,肯定会超时。我不知道滑动窗口是否有效。谁能给我任何关于如何进行的提示?显然,我并不要求完整的答案,只是一些提示对我有用。提前致谢:)
最佳答案
这有一个非常简单的动态规划解决方案。
对于每个索引i,计算:
- 如果未删除任何内容,则紧接其前的 1 序列的长度;
- 可以紧接在它之前的最长的 1 序列,如果在它之前恰好删除了一个子串;和
- 如果恰好在它之前删除了两个子串,则可以紧接在它之前的最长的 1 序列。
对于每个索引,这三个值很容易在常数时间内根据早期索引的值计算出来,因此您可以在 O(N) 时间内一次性完成此操作。
例如,令BEST(i,r) 为删除r 个子字符串后位置i 之前的最佳长度。如果 i >= K,那么您可以删除以 i 结尾的子字符串并使 BEST(i,r) = BEST(i-K,r-1) 对于 r > 0。如果 string[i-1] = '1' 那么你可以从之前的位置扩展序列并且有 BEST(i,r) = BEST(i-1,r)+1 强>。为每个 i,r 选择最佳可能性。
您在第 (3) 步中找到的最大值就是答案。
关于string - 字符串中连续 1 的最大数目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56988805/