2022-12-29 • 于双指针, 数列, 算法阅读

找出最长的神奇数列

问题

问题描述

小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。这意味着数列中至少要有 3 个连续的 0 或 1，并且这些 0 和 1 是交替出现的。比如10101 是神奇数列，而1010就不是。

数据结构选择

由于我们处理的是字符串，可以直接使用字符串操作。

算法步骤

遍历字符串：从字符串的第一个字符开始，逐个检查字符。
检测交替模式：对于每个字符，检查它是否与前一个字符不同，如果是，则继续检查下一个字符是否与当前字符不同，以此类推。
记录最长神奇数列：在检测到交替模式（交替模式在本题中指的是序列中的 0 和 1 交替出现）时，记录当前的子串长度，并与之前记录的最长长度进行比较。如果当前长度更长，则更新最长神奇数列的起始和结束位置。
返回结果：遍历结束后，返回最长的神奇数列。

关键点

如何高效地检测交替模式。
如何记录和更新最长神奇数列的起始和结束位置。

这道题目综合运用了字符串处理和双指针算法知识，是一道典型的字符串处理问题，适合练习字符串操作和算法优化的同学。

思路说明

题目要求找出由 0 和 1 交替组成的、长度至少为 3 的最长子序列。我们可以通过遍历字符串，使用双指针来识别和记录这些交替出现的子序列。具体来说，我们使用两个指针 i 和 j，其中 i 指向当前子序列的开始，j 用于扩展子序列，直到遇到与前一个字符相同的字符为止。通过这种方式，我们可以找到所有符合条件的子序列，并记录其中最长的那个。

解题过程

初始化：
1. 初始化指针 i 为 0，表示当前子序列的起始位置。
2. 初始化变量 ans 为空字符串，用于存储最长的神奇数列。
遍历字符串：
1. 使用 while 循环遍历字符串，直到 i 达到字符串的长度。
2. 初始化指针 j 为 i + 1，表示当前子序列的下一个字符。
扩展子序列：
1. 使用 while 循环，当 j 未超出字符串长度且 inp[j] 不等于 inp[j - 1] 时，继续扩展子序列。
2. 每次扩展后，j 增加 1。
更新最长子序列：
1. 如果当前子序列的长度 j - i 大于 ans 的长度，则更新 ans 为当前子序列 chars[i..j].iter().collect()。
2. 更新 i 为 j，继续寻找下一个子序列。
返回结果：
1. 如果最终找到的最长子序列长度小于 3，则返回空字符串。
2. 否则，返回 ans。

复杂度分析

时间复杂度：
- 遍历字符串一次，时间复杂度为 O(n)，其中 n 是字符串的长度。
- 在每次遍历中，j 指针最多移动 n 次，因此总体时间复杂度为 O(n)。
空间复杂度：
- 只使用了常数级别的额外空间，空间复杂度为 O(1)。

知识点扩展

字符串处理：
- 字符串的基本操作，如遍历、切片等。
- 双指针技巧在字符串处理中的应用，用于高效地识别和处理子序列。
双指针算法：
- 双指针算法是一种常用的优化技巧，适用于需要在数组或字符串中寻找特定模式的场景。
- 在本题中，双指针 i 和 j 分别用于标记子序列的起始和结束位置，通过这种方式可以高效地找到符合条件的子序列。

解答

fn solution(inp: &str) -> String {
    // chars 是一个字符串切片（&str）的 chars() 方法返回的迭代器，它将字符串转换为一个字符的迭代器。
    let chars: Vec<char> = inp.chars().collect();
    // 初始化指针 i 为 0，表示当前子序列的起始位置。
    let mut i = 0;
    // 初始化变量 ans 为空字符串，用于存储最长的神奇数列
    let mut ans = String::new();
    
    // - Note: 遍历字符串，初始化指针 j 为 i + 1，表示当前子序列的下一个字符
    while i < chars.len() {
        let mut j = i + 1;
        // - Note: 扩展子序列，每次扩展后，j 增加 1
        // 找到不再交替的位置：当 j 未超出字符串长度且 inp[j] 不等于 inp[j - 1] 时，继续扩展子序列
        // 也就是是当前和前一个数不相同时
        while j < chars.len() && chars[j] != chars[j - 1] {
            j += 1;
        }
        
        // - Note: 更新最长子序列
        // 如果找到更长的序列：如果当前子序列的长度 j - i 大于 ans 的长度，则更新 ans 为当前子序列
        if j - i > ans.len() {
            // [i..j] 是一个切片操作，表示从索引 i 开始到索引 j 结束（不包括 j）的子切片。
            // iter() 方法将这个子切片转换为一个迭代器。这个迭代器会逐个返回子切片中的字符。
            // collect() 方法将迭代器中的元素收集到一个集合中。具体收集到什么类型的集合取决于上下文。
            // 例如，如果上下文允许，它可以将字符收集到一个字符串中，或者收集到一个向量中。
            // 等价与 python 中的 ans = inp[i:j]
            ans = chars[i..j].iter().collect();
        }
        // 更新 i 为 j，继续寻找下一个子序列
        i = j;
    }
    
    // 如果序列长度小于3，返回空字符串
    if ans.len() < 3 {
        ans.clear();
    }
    
    ans
}

fn main() {
    println!("{}", solution("0101011101") == "010101");
    println!("{}", solution("1110101010000") == "10101010");
    println!("{}", solution("1010101010101010") == "1010101010101010");
}

字符串处理：
1. 在 Rust 中，字符串不能像 Python 那样直接用下标访问字符
2. 需要先将字符串转换为字符数组：let chars: Vec = inp.chars().collect()
3. 切片操作需要使用 collect() 来收集字符：chars[i..j].iter().collect()
变量声明：
1. Rust 需要使用 mut 关键字声明可变变量
2. 使用 String::new() 创建空字符串
循环和条件：
1. while 循环的语法基本相同
2. 条件判断不需要括号
字符串操作：
1. Python 的字符串切片 inp[i:j] 变成了 Rust 的 chars[i..j].iter().collect()
2. 清空字符串使用 ans.clear() 而不是赋值空字符串

跃迁引擎