字节青训-找出最长的神奇数列

问题描述

小F是一个好学的中学生，今天他学习了数列的概念。他在纸上写下了一个由 0 和 1 组成的正整数序列，长度为 n。这个序列中的 1 和 0 交替出现，且至少由 3 个连续的 0 和 1 组成的部分数列称为「神奇数列」。例如，10101 是一个神奇数列，而 1011 不是。现在，小F想知道在这个序列中，最长的「神奇数列」是哪一个。你能帮他找到吗？

如果有多个神奇数列，那么输出最先出现的一个。

测试样例

样例1：

输入：inp = "0101011101"
输出：'010101'

样例2：

输入：inp = "1110101010000"
输出：'10101010'

样例3：

输入：inp = "1010101010101010"
输出：'1010101010101010'

 

 解题思路：

问题理解

我们需要在一个由 0 和 1 组成的字符串中找到最长的「神奇数列」。神奇数列的定义是：

• 由 0 和 1 交替出现。
• 至少由 3 个连续的 0 和 1 组成。

数据结构选择

我们可以直接使用字符串来处理这个问题，因为输入和输出都是字符串。

算法步骤

1. 初始化变量：

   • maxlist 用于存储最长的神奇数列。
   • maxLength 用于记录最长神奇数列的长度。
   • start 用于记录当前神奇数列的起始位置。
   • currentLength 用于记录当前神奇数列的长度。

2. 遍历字符串：

   • 从第二个字符开始遍历字符串。
   • 如果当前字符与前一个字符不同，说明仍然是交替的，增加 currentLength。
   • 如果当前字符与前一个字符相同，说明交替中断，检查当前神奇数列的长度是否大于等于3，如果是，则更新 maxlist 和 maxLength。然后重置 start 和 currentLength。

3. 处理最后一段神奇数列：

   • 在遍历结束后，检查最后一段神奇数列的长度是否大于等于3，如果是，则更新 maxlist 和 maxLength。

4. 返回结果：

   • 返回 maxlist，即最长的神奇数列。

最终代码：

def solution(inp):
    maxlist = ""  # 用于存储最长的神奇数列
    maxLength = 0  # 最长神奇数列的长度
    n = len(inp)  # 输入字符串的长度

    # 当前神奇数列的起始位置和长度
    start = 0
    currentLength = 1

    for i in range(1, n):
        if inp[i] != inp[i - 1]:  # 当前字符与前一个字符不同
            currentLength += 1  # 更新当前神奇数列的长度
        else:
            # 如果当前长度大于等于3，检查是否需要更新最长的神奇数列
            if currentLength >= 3:
                candidate = inp[start:start + currentLength]
                if currentLength > maxLength:
                    maxLength = currentLength
                    maxlist = candidate  # 更新最长神奇数列

            # 重置当前神奇数列
            start = i
            currentLength = 1  # 重新计数

    # 处理最后一段神奇数列
    if currentLength >= 3:
        candidate = inp[start:start + currentLength]
        if currentLength > maxLength:
            maxlist = candidate  # 更新最长神奇数列

    return maxlist  # 返回最长的神奇数列


if __name__ == "__main__":
    # 添加测试用例
    print(solution("0101011101") == "010101")

运行结果：