algorithm - 如何找到子序列？

Question

我得到一个随机长度的随机数字序列，由 0、1、2 组成:

201102220221

我还得到了一个数字:1 或 2。我只能遍历序列一次，我需要确定我给出的数字的所有子序列，运行它通过另一个函数计算值并将该值添加到总和(初始化为 0)。

任何 0 都可以用 1 或 2 替换。因此，可以通过用数字替换旁边的 0 来“扩展”子序列。如果一个子序列不能扩展到最小长度超过 4，我需要丢弃它。

例如，假设我得到了序列:

11011002102

和数字 1。我在开头识别长度为 2 的子序列(参见第一个元素)。它可以扩展为长度为 7 的子序列，方法是用 1 替换第一个 0、第三个和第四个零。因此，我通过一个函数运行它的当前长度并将其添加到总和中。

sum += function(2);

然后我确定下一个 1 的子序列(参见第四个元素)。它目前的大小为 2，并且可以通过替换它周围的零来扩展到最大大小 7。所以我将它的长度传递给一个函数并将其添加到总和中。

sum += function (2);

我终于确定了 1 的最后一个子序列(参见第六元素)。它目前的长度为 1，并且可以通过将其旁边的零替换为小于 4 的 1 来扩展到最大大小 2，因此我将其丢弃。

谁能帮我写一个函数，通过仅循环遍历序列一次来执行上述操作。 请不要给我真正的代码，只是想法、建议或伪代码。

我没有任何工作可以分享，我完全迷路了。我也不懂算法，所以请不要开始谈论动态规划或线性规划之类的东西，而是解释解决问题的可能方法。

Answer 1

鉴于只能循环一次序列的要求，您知道代码的基本结构。

给定用于丢弃子序列(扩展长度为 4 或更多)和用于处理子序列(未扩展序列长度)的参数，您知道需要跟踪哪些数据。找出如何根据您的环境和语言约定最好地存储这些数据。

在循环的每次迭代中，考虑输入序列的当前字符及其对存储数据的影响。

我试图在此处澄清问题，而不仅仅是向您提供解决方案。欢迎提出更多问题。

编辑:

考虑如何逐步分解问题。以下是 for 循环的迭代:

1----------

好的，我们正在寻找 1，我们已经找到了一个。

-1---------

太棒了，又是一个 1，现在我们的子序列长度已经增加到 2

--0--------

是的，因为这不是 1，所以这个子序列的长度现在已知为 2 - 它不再增加，但因为这是 0，如果它可以扩展到至少 4，它可能仍然符合条件。扩展的子序列长度现在是 3。

---1-------

扩展的子序列长度现在是 4!这意味着我们可以在将最后一个序列长度传递给 function 之后将其添加到总和中。这也是另一个子序列的开始 - 因此子序列长度现在重​​置为 1，但扩展的子序列长度在 4 时仍然有效。这意味着这个子序列已经足够长，不会被拒绝，但我们在这个阶段还没有计算完它的长度。

----1------

子序列长度 = 2，扩展子序列长度 = 5

-----0-----

这标志着第二个子序列的结束，像以前一样处理它。等等

------0----
-------2--- <- expanded subsequence length gets reset here
--------1-- <- start of another subsequence
---------0- <- expanded length is 2
----------2 <- expanded length is not long enough for this to qualify, discard it

所以，相当简单。我们需要跟踪两个因素:子序列长度 和扩展子序列长度。

一旦你开始工作，想想这个输入序列“1010101”会发生什么。