右旋字符串

时间限制：1.000S  空间限制：128MB

题目描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入描述

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述

输出共一行，为进行了右旋转操作后的字符串。

输入示例

2
abcdefg

输出示例

fgabcde

提示信息

数据范围：
$1\le k<10000$,
$1\le s.length<10000$;

解法一(模拟)

思路分析：

1. 读取字符串，然后将字符串转化为字符数组，再在该字符数组的基础上进行旋转

2. 由k将字符串分成两部分[0, n-k]和[n-k+1, n-1]两部分，而最终得到的结果将第二部分移动到第一部分前面

3. 可以先将整个字符串反转，然后再将这两部分分别反转，即可完成

实现代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        // 读取k
        int k = Reader.nextInt();
        // 读取字符串
        String s = Reader.nextLine();
        // 将字符串转化为字符数组
        char[] str = s.toCharArray();

        // 先反转整个字符串
        reverseString(str, 0, str.length-1);
        // 再反转原先的第二部分
        reverseString(str, 0, k-1);
        // 反转原先的第一部分
        reverseString(str, k, str.length-1);

        // 输出右旋转后的字符串
        PrintWriter out = new PrintWriter(System.out);
        out.println(new String(str));
        out.flush();    // 刷新快速输出流

    }
    // 相向双指针 实现字符串反转
    public static void reverseString(char[] str, int left, int right) {
        while (left < right) {
            str[left] ^= str[right];
            str[right] ^= str[left];
            str[left] ^= str[right];
            ++ left;
            -- right;
        }
    }
}
class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
        static String nextLine() throws IOException {       // 读取下一行字符串
            return reader.readLine();
        }
        static String next() throws IOException {      // 读取下一个单词
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }
        static int nextInt() throws IOException {       // 读取一个Int型整数值
            return Integer.parseInt(next());
        }
}

提交结果如下：

time_space_table:
/1065/sample.in:AC mem=11296k time=108ms
/1065/test1.in:AC mem=11328k time=115ms
/1065/test2.in:AC mem=11372k time=115ms
/1065/test3.in:AC mem=11372k time=113ms
/1065/test4.in:AC mem=11372k time=114ms
/1065/test5.in:AC mem=11372k time=116ms
/1065/test6.in:AC mem=11372k time=112ms
/1065/test7.in:AC mem=11372k time=114ms

复杂度分析：

• 时间复杂度：$O(n)$，遍历字符串数组
• 空间复杂度：$O(n)$，使用了一个字符串数组进行反转