string - 字符串中连续 1 的最大数目

标签 string algorithm optimization brute-force sliding-window

给定一个长度为 N(最多 10^5)的字符串,它仅由 0 和 1 组成。我们必须从原始字符串中删除长度正好为 K 的两个子字符串,以最大化连续 1 的数量。

例如假设字符串是 1100110001 并且 K=1。

所以我们可以删除两个长度为 1 的子字符串。这里最好的选择是删除第 3 位和第 4 位的 0,并得到输出 4(因为新字符串将是 11110001)

如果我尝试暴力破解,肯定会超时。我不知道滑动窗口是否有效。谁能给我任何关于如何进行的提示?显然,我并不要求完整的答案,只是一些提示对我有用。提前致谢:)

最佳答案

这有一个非常简单的动态规划解决方案。

对于每个索引i,计算:

  1. 如果未删除任何内容,则紧接其前的 1 序列的长度;
  2. 可以紧接在它之前的最长的 1 序列,如果在它之前恰好删除了一个子串;和
  3. 如果恰好在它之前删除了两个子串,则可以紧接在它之前的最长的 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/

相关文章:

html - 不以 .css 结尾的 CSS 文件

c - c中逻辑运算符之间的空间

java - 在 TextView 中显示 JSONStringer 结果

PHP - 在字符串中打印命名空间常量?

java - 在android中输入第一个字符后立即输入字符

algorithm - 在 O(1) 中实现并合并两个堆栈

java - 如何在java中拆分字符串并包含定界符

algorithm - 网格打包算法

c++ - 回溯N皇后算法

javascript - 来自base64编码的纯Javascript粒子排斥器png