T1.小牛的文本加密 - 美团机试真题

题目描述

小牛有一个加密的字符串s，你无意间得到了他的加密方式，尝试解开它！ 初始时，解密字符串t为空，除此之外，还有一个记录位移的整数p为0。依次对每一个i = 1,2,…,|s|进行以下操作（其中|s|代表字符串s的长度）：

• 如果s的第i个字符为数字x，则需要对p修改，具体地：
  • 若p = 0，则将p置为x（即p → x）；
  • 若p ≠ 0，则将p中的数字全部向高位移动一位，随后将空出来的个位填上x（即p → 10p + x）；
• 如果s的第i个字符不为数字，则需要先将字符串左移p位（即），随后将p重新置为0，再对t修改，具体地：
  • 若字符为R，则反转字符串t；
  • 若字符不为R，则直接将这个字符添加到字符串t的结尾；

请你直接输出解密完成后的字符串t。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤ T≤ 10)代表数据组数，每组测试数据描述如下： 在一行上输入一个长度为|s|(1 ≤|s|≤ 1000)，且由大小写字母和数字混合构成的字符串代表小牛的加密串。

输出描述

对于每一组测试数据，在一行上输出一个字符串，代表解密完成后的字符串。

示例1

输入：
2
meRD2o
D0ame3

输出：
Demo
Dame

说明：无

C++

#include <bits/stdc++.h>

using namespace std;

// 左移字符串 t 的 p 位
void leftShift(deque<char> &dq, int k) {
    while (k-- > 0) {
        dq.push_back(dq.front());  // 把队列的头部元素移动到尾部
        dq.pop_front();
    }
}

int main() {
    int T;
    cin >> T;
    while (T-- > 0) {
        string s;
        cin >> s;

        deque<char> dq;
        int p = 0;

        for (char x : s) {
            if (isdigit(x)) {
                // 计算 p 值
                if (p == 0) p = x - '0';
                else p = 10 * p + (x - '0');
            } else {
                // 先进行 p 位左移
                leftShift(dq, p);
                p = 0;

                if (x == 'R') {
                    reverse(dq.begin(), dq.end());
                } else {
                    dq.push_back(x);
                }
            }
        }

        // 输出结果
        string ans(dq.begin(), dq.end());
        cout << ans << endl;
    }

    return 0; 
}

题目分析

这道题属于模拟类问题，需要按照题目描述的规则逐步解析字符串，并构造最终的解密字符串。

• 通过一个变量 p 记录数字所表示的位移量。

• 遇到数字时，更新 p 的值。

• 遇到字母时，首先按照 p 的值进行字符串左移，然后进行操作：

  • R 代表翻转字符串。

  • 其他字符添加到字符串尾部。

由于字符串的左移和翻转操作可能会频繁进行，适合使用**双端队列（deque）**来进行优化。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏