C++求解0-1向量最长交替子序列及数量的问题

问题描述 #

给定仅包含0和1的std::vector，需要找出满足相邻元素不同的最长子序列长度，以及该长度子序列的出现次数。示例如下：

• 向量v = {1,0,1,0,0,1,0,1}：最长交替子序列长度为4，共2个，输出4 2
• 向量v2 = {1,0,1,1,1,0,1,0,1,0}：最长长度为6，仅1个，输出6 1

原代码的问题 #

你提供的循环实现处理{1,0,0}这类向量时失效：该向量的最长交替子序列长度为2、次数为1，但原代码无法得到正确结果。核心问题包括：

1. 遍历结束后未处理最后一段交替序列，导致这段序列的长度和计数未被纳入判断
2. 遇到相同元素时的计数逻辑错误，会错误覆盖或重复累加计数
3. 初始值的处理未考虑边界情况（如单元素向量）

正确解决思路 #

核心逻辑 #

1. 初始化变量：
   • max_len：记录最长交替子序列长度，初始为1（单个元素本身就是长度1的有效子序列）
   • current_len：记录当前正在统计的交替子序列长度，初始为1
   • count：记录最长子序列的出现次数，初始为1
2. 遍历向量：
   • 若当前元素与前一个元素不同，current_len自增，延长当前交替序列
   • 若当前元素与前一个元素相同：
     • 先将当前current_len与max_len比较：
       • 若current_len > max_len：更新max_len为当前长度，重置count为1
       • 若current_len == max_len：count自增，累加相同长度的序列数量
       • 若current_len < max_len：不修改count
     • 重置current_len为1，开始统计新的序列
3. 遍历后收尾：
   遍历结束后，最后一段交替序列尚未参与比较，需额外判断一次，更新max_len和count
4. 边界处理：
   • 空向量直接返回0 0
   • 单元素向量返回1 1

修正后的代码示例 #

#include <vector>
#include <iostream>
#include <utility>

using namespace std;

pair<int, int> longestAlternatingSubsequence(const vector<int>& v) {
    if (v.empty()) {
        return {0, 0};
    }
    int n = v.size();
    if (n == 1) {
        return {1, 1};
    }
    
    int max_len = 1;
    int current_len = 1;
    int count = 1;
    
    for (int i = 1; i < n; ++i) {
        if (v[i] != v[i-1]) {
            current_len++;
        } else {
            if (current_len > max_len) {
                max_len = current_len;
                count = 1;
            } else if (current_len == max_len) {
                count++;
            }
            current_len = 1;
        }
    }
    
    // 处理最后一段未统计的交替序列
    if (current_len > max_len) {
        max_len = current_len;
        count = 1;
    } else if (current_len == max_len) {
        count++;
    }
    
    return {max_len, count};
}

int main() {
    vector<int> v1 = {1,0,1,0,0,1,0,1};
    auto res1 = longestAlternatingSubsequence(v1);
    cout << res1.first << " " << res1.second << endl; // 输出4 2
    
    vector<int> v2 = {1,0,1,1,1,0,1,0,1,0};
    auto res2 = longestAlternatingSubsequence(v2);
    cout << res2.first << " " << res2.second << endl; // 输出6 1
    
    vector<int> v3 = {1,0,0};
    auto res3 = longestAlternatingSubsequence(v3);
    cout << res3.first << " " << res3.second << endl; // 输出2 1
    
    return 0;
}

内容的提问来源于stack exchange，提问作者sigma