题目分析

1. 题目给出我们若干条字符串
2. 我们要将这些字符串以8位长按行输出
3. 对于长度不足8位的字符串要补充0在末尾并输出
4. 对于长度大于8位的字符串要截断成一个个8位的子字符串输出，对于最后一行不足8位的情况同样要补0输出

方法一：递归

• 实现思路

  • 我们规定递归函数的意义表示对于一个字符串str，本轮递归要处理的字符串起点位置在i，仍旧还未处理的字符串剩余长度为size

  • 在递归函数体内

    • 首先判断剩余长度是否是小于8
    • 如果小于8则进行补0操作并输出
    • 如果大于8则需要输出截断部分，并继续进行递归

  • 对于所有的字符串都调用递归函数处理

#include<iostream>
#include<string>

using namespace std;

void output(string str, int i, int size) {
    if(size <= 8) {                            // 对于最后的不足长度8的部分单独处理
        int rp = 8 - str.size();
        string s = str.substr(i, size);
        s.resize(8, '0');                      // 适当补充0，将其resize为8
        cout << s << endl;
    } else {
        cout << str.substr(i, 8) << endl;      // 对于长的部分不需要补0，则直接截断输出
        output(str, i + 8, size - 8);          // 对于剩下的部分继续递归调用，调整下次需要输出的起点和剩余字符的size
    }
}


int main() {
    string s;
    while(cin >> s) {                        // 处理输入
        output(s, 0, s.size());              // 对于每行输入进行递归函数处理
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历了所有的字符串
• 空间复杂度：$O(n)O(n)$，对于每个字符串都有递归的空间栈使用，使用空间和字符串的长度呈线性关系

方法二：迭代

• 实现思路
  • 对于输入的字符串计算该字符串长度下需要截断的次数，和最后剩余的长度
  • 对于计算到的截断次数，直接输出子字符串截断后的结果即可
  • 对于剩余的部分来计算是否需要补0输出

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

using namespace std;

int main(){
    string s;
    while(cin >> s){
        int n = s.size();     
        int turn = n / 8;                        // 表示不用补充0的组数
        int rp = 8 - n % 8;                      // 需要补充0的位数
        
        int i = 0;
        while(turn) {                            // 将不用补充0的部分直接截断输出
            turn--;
            cout << s.substr(i,8) <<endl;
            i += 8;
        }
        
        string fn = s.substr(i, s.size());       // 将最后一部分需要补0的单独拿出来
        while(rp && rp != 8) {                   // 按需补0
            fn += "0";
            rp--;
        }
        if(fn != "") cout << fn <<endl;          // 判断我们最后截取的fn是否为空，为空则不输出

    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历所有的字符串
• 空间复杂度：$O(1)O(1)$，只是用了常量级别的空间代价如一些变量等