c++ - 使用特殊参数拆分字符串

Question

我有以下字符串:

1,1,1,0,1,1,2,1,1,1,1,2,1,1,1,0,1,1,0,1,1,1,

---

0-->rupture
2-->continuity

---

• 当我在两个 0 之间有 1 时，这意味着我有一个文档[0,1,1,1,0] = D
• 当我在 2 和 0 之间有 1 时，这意味着我有一个片段 [2,1,..., 1,0] = f 和 i 将所有片段添加到片段列表 F 并且它表示子片段的结尾
• 当我在 2 和 2 之间有 1 时，这意味着我也有一个片段 [2,1,... ,1,2] = f

---

作为我最终必须拥有的解决方案:

• 3 个文档 D1、D2、D3，它们位于索引 [0,3] 之间，[15,18], [18,21]
• [3,15] 之间的片段 F 包含 3 个子片段，f1 在 [3,6] 之间，f2 在 [ 6,11] 和 f3 在 [11,15] 之间。

Note: We consider that the string starts with a 0 and ends with a 0 This is why we have a document between [0,3] and another document between [18,21]

---

我正在尝试制定这个问题，但我想不出一个可靠的主意。请告诉我是否清楚。我可以使用什么作为算法来帮助解决这个问题，我可以使用像树这样的特定数据结构吗...

谢谢，哈尼族。

Answer 1

如果你的字符串是:

1,1,1,0,1,1,2,1,1,1,1,2,1,1,1,0,1,1,0,1,1,1

初始化lastPos = 0, lastType = 0 {lastType = 0 for 0 and 2 for 2}

遍历数组。您在位置 3 找到下一个 0。由于 lastType 等于 0，您知道您在 2 个零 之间找到了一个 1 序列。随心所欲。

Make lastType = 0, lastPos = 3.

继续到最后。

Order of time complexity: O(n)
Order of space complexity: O(1)