题目链接

字符串解密

题目描述

给定一个由字符 '0' 和 '1' 构成的字符串 。我们从字符串开头开始，按照一个循环变化的长度规则依次取出以下子串并解析为十进制数：

  • 长度 1 的子串；
  • 长度 2 的子串；
  • ...
  • 长度 10 的子串；
  • 然后循环回长度 1，依此类推；

子串被取走后，视为从原字符串中删除，下一次从剩余的字符串开头继续取。直到剩余字符不足以组成当前所需长度的子串时，解析过程结束。

请输出解析得到的十进制数字序列。

输入:

  • 一个由 '0' 和 '1' 构成的字符串 。

输出:

  • 第一行输出一个整数 ，表示解析得到的数字个数。
  • 第二行输出 个整数，表示所有解析出的十进制数字，数字之间用空格隔开。

解题思路

这是一个直接的模拟问题，我们只需要按照题目描述的规则逐步切分字符串即可。

我们可以维护两个核心变量：

  • 一个指针 ，记录当前应当从字符串的哪个位置开始切分。
  • 一个变量 ，记录当前需要切分的子串长度。

算法的详细步骤如下：

  1. 初始化 为 0， 为 1。
  2. 初始化一个列表 用于存储解析出的十进制数。
  3. 进入一个循环，循环的条件是剩余字符串的长度不小于当前需要切分的长度，即 。
  4. 在循环中： a. 从字符串 中，截取从 开始，长度为 的子串。 b. 将这个二进制子串转换为十进制整数。 c. 将转换后的整数添加到 列表中。 d. 更新 ，将它的值增加 ，以指向下一次切分的起始位置。 e. 更新 。根据题意，长度从 1 递增到 10，然后重新循环回 1。所以我们将 加 1，如果它超过 10，就将它重置为 1。
  5. 当循环结束时（因为剩余字符串长度不足）， 列表中就包含了所有按规则解析出的数字。
  6. 最后，按照题目要求的格式输出 的大小和内容。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    string s;
    cin >> s;

    vector<long long> results;
    int current_index = 0;
    int current_length = 1;

    // 当剩余字符串足够长时，继续切分
    while (current_index + current_length <= s.length()) {
        // 截取子串
        string sub = s.substr(current_index, current_length);
        // 将二进制子串转为十进制数，并存入结果
        results.push_back(stoll(sub, nullptr, 2));
        
        // 更新下一次切分的起始位置
        current_index += current_length;
        // 更新下一次切分的长度 (1-10 循环)
        current_length++;
        if (current_length > 10) {
            current_length = 1;
        }
    }

    // 输出结果数量
    cout << results.size() << endl;
    // 输出结果序列
    for (size_t i = 0; i < results.size(); ++i) {
        cout << results[i] << (i == results.size() - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        List<Integer> results = new ArrayList<>();
        int currentIndex = 0;
        int currentLength = 1;
        
        // 当剩余字符串足够长时，继续切分
        while (currentIndex + currentLength <= s.length()) {
            // 截取子串
            String sub = s.substring(currentIndex, currentIndex + currentLength);
            // 将二进制子串转为十进制数，并存入结果
            results.add(Integer.parseInt(sub, 2));
            
            // 更新下一次切分的起始位置
            currentIndex += currentLength;
            // 更新下一次切分的长度 (1-10 循环)
            currentLength++;
            if (currentLength > 10) {
                currentLength = 1;
            }
        }
        
        // 输出结果数量
        System.out.println(results.size());
        // 输出结果序列
        for (int i = 0; i < results.size(); i++) {
            System.out.print(results.get(i) + (i == results.size() - 1 ? "" : " "));
        }
        System.out.println();
    }
}

def solve():
    s = input()
    
    results = []
    current_index = 0
    current_length = 1
    
    # 当剩余字符串足够长时，继续切分
    while current_index + current_length <= len(s):
        # 截取子串
        sub = s[current_index : current_index + current_length]
        # 将二进制子串转为十进制数，并存入结果
        results.append(int(sub, 2))
        
        # 更新下一次切分的起始位置
        current_index += current_length
        # 更新下一次切分的长度 (1-10 循环)
        current_length += 1
        if current_length > 10:
            current_length = 1
        
    # 输出结果数量
    print(len(results))
    # 输出结果序列
    print(*results)

solve()

算法及复杂度

  • 算法：模拟
  • 时间复杂度: ，其中 是字符串的长度。我们通过指针移动的方式，整个字符串的每个字符实际上只被访问和处理常数次。
  • 空间复杂度: ，用于存储解析出的十进制数。平均切分长度是 5.5，所以结果数量级约为 ，即 。