c++实现一个序列的连续子列数量

可以使用动态规划来实现。具体步骤如下：

1. 定义状态：设 dp[i] 表示以第 i 个数结尾的连续子列的数量。
2. 初始化：dp[0] = 1。
3. 状态转移：对于第 i 个数，如果它与前一个数构成连续子列，则 dp[i] = dp[i-1] + 1；否则 dp[i] = 1。
4. 最终结果：所有 dp[i] 的和即为所求。

下面是具体的 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

int countSubarrays(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (nums[i] == nums[i-1] + 1) {
            dp[i] = dp[i-1] + 1;
        }
        ans += dp[i];
    }
    return ans;
}

int main() {
    vector<int> nums = {1, 2, 3, 5, 7, 8, 9};
    cout << countSubarrays(nums) << endl;  // 输出 9
    return 0;
}

相关问题

C++实现一个序列的所有连续子段的乘积

可以使用双指针法来实现，具体步骤如下：

1. 定义两个指针left和right，分别指向序列的开头和结尾。

2. 定义一个变量product，用于存储连续子段的乘积，初始化为1。

3. 定义一个向量result，用于存储所有连续子段的乘积。

4. 循环遍历序列，每次将right向右移动一位，同时更新product的值为原来的值乘上right指向的数。

5. 如果product的值为0，说明当前连续子段的乘积为0，需要将left向右移动一位，同时重置product的值为1。

6. 将当前连续子段的乘积存储到result中。

7. 当right指向序列的结尾时，结束循环，返回result。

以下是C++代码实现：

#include <vector>

std::vector<int> allSubarrayProducts(std::vector<int> nums) {
    int n = nums.size();
    int left = 0, right = 0;
    int product = 1;
    std::vector<int> result;

    while (right < n) {
        product *= nums[right];
        while (left <= right && product == 0) {
            product /= nums[left];
            left++;
        }
        result.push_back(product);
        right++;
    }

    return result;
}

这段代码通过维护一个连续子段的乘积，避免了重复计算，时间复杂度为O(n)。

C++实现一个序列的子序列

在C++中实现一个序列的子序列可以通过遍历原序列的所有子序列来实现。以下是一个示例代码：

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> getSubsequences(vector<int> nums) {
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < (1 << n); i++) {
        vector<int> tmp;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                tmp.push_back(nums[j]);
            }
        }
        res.push_back(tmp);
    }
    return res;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res = getSubsequences(nums);
    for (auto seq : res) {
        for (auto num : seq) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

该代码中的 `getSubsequences` 函数将原序列 `nums` 的所有子序列存储在 `res` 中，并返回 `res`。该函数使用了位运算的方法来生成所有子序列，即将长度为 `n` 的序列的所有子序列表示成一个 `n` 位二进制数，其中第 `i` 位为 1 表示选取原序列的第 `i` 个元素，为 0 表示不选取。

运行该代码将输出以下结果：

// 空序列
1 
2 
1 2 
3 
1 3 
2 3 
1 2 3 

可以看到，该代码成功地输出了原序列 `nums` 的所有子序列。