题目链接

字符串挪移

题目描述

给定一个长度为 的、只包含小写字母的字符串 。进行 次操作，输出最终的字符串。

这道题的描述非常具有迷惑性，并不能直接按照字面意思“将 s[i] 移动到末尾”来理解。通过示例和测试用例分析，可以发现其本质是一个类似约瑟夫环的模拟问题。正确的操作可以理解为：

  1. 将当前字符串的第一个字符移动到字符串末尾。
  2. 将此时字符串的第一个字符（即原字符串的第二个字符）作为结果的下一个字符。
  3. 在剩下的字符串上重复此过程，直到所有字符都被取出。

解题思路

这是一个模拟题。我们可以使用双端队列（deque）来高效地模拟上述过程。

  1. 将输入字符串 的所有字符存入一个双端队列中。
  2. 创建一个空的结果列表（或 StringBuilder）用来存放最终的字符序列。
  3. 当队列不为空时，重复以下操作： a. 将队首的元素弹出，再加入队尾（模拟“将顶牌放到牌堆底”）。 b. 将此时的队首元素弹出，加入结果列表（模拟“派发下一张牌”）。 c. 特殊处理最后剩下的一个元素，直接将其加入结果列表即可。
  4. 将结果列表中的字符拼接成字符串，即为答案。

以 paectc 为例:

  • 初始队列: [p, a, e, c, t, c], 结果: []
  1. p 到队尾: [a, e, c, t, c, p]. 取出 a: [e, c, t, c, p], 结果: [a]
  2. e 到队尾: [c, t, c, p, e]. 取出 c: [t, c, p, e], 结果: [a, c]
  3. t 到队尾: [c, p, e, t]. 取出 c: [p, e, t], 结果: [a, c, c]
  4. p 到队尾: [e, t, p]. 取出 e: [t, p], 结果: [a, c, c, e]
  5. t 到队尾: [p, t]. 取出 p: [t], 结果: [a, c, c, e, p]
  6. 只剩 t: [], 结果: [a, c, c, e, p, t]

最终拼接为 accept。

代码

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;

    deque<char> d;
    for (char c : s) {
        d.push_back(c);
    }

    string res = "";
    while (!d.empty()) {
        if (d.size() > 1) {
            char front = d.front();
            d.pop_front();
            d.push_back(front);
        }
        res += d.front();
        d.pop_front();
    }
    
    cout << res << endl;

    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        Deque<Character> d = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            d.add(c);
        }
        
        StringBuilder res = new StringBuilder();
        while (!d.isEmpty()) {
            if (d.size() > 1) {
                d.addLast(d.pollFirst());
            }
            res.append(d.pollFirst());
        }
        
        System.out.println(res.toString());
    }
}

from collections import deque

s = input()
n = len(s)
d = deque(list(s))
res = []

while len(d) > 0:
    if len(d) > 1:
        d.append(d.popleft())
    res.append(d.popleft())

print("".join(res))

算法及复杂度

  • 算法：模拟。使用双端队列模拟“取牌-放回牌堆底-再取牌”的过程。
  • 时间复杂度： - 每个字符都只入队和出队常数次，双端队列的头尾操作都是 。
  • 空间复杂度： - 需要一个额外的双端队列来存储所有字符。