右旋转字符串

背景

• 数据结构–右旋转字符串

• 博主以代码随想录算法公开课进行学习

问题

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

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

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

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

样例输入：

2
abcdefg 

样例输出：

fgabcde

数据范围：1 <= k < 10000, 1 <= s.length < 10000;

思路

• 三次反转
  • 反转整个字符串：把原字符串整体反转，让尾部的 k 个字符到开头，开头的 len-k 个字符到结尾。
  • 反转前 k 个字符：将第一步中移到开头的 k 个字符（原尾部）反转回原本的顺序。
  • 反转剩余 len-k 个字符：将第一步中移到结尾的 len-k 个字符（原开头）反转回原本的顺序。

代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        // 1. 读取输入的右旋转位数 k
        int n = Integer.parseInt(in.nextLine().trim());// 加trim避免输入空格干扰
        // 2. 读取需要旋转的字符串 s
        String s = in.nextLine();
        int len = s.length();
        
        // 3. 将字符串转为字符数组
        char[] chars = s.toCharArray();
        // 4. 三次反转核心逻辑
        reverseString(chars,0,len-1);// 反转整个字符串
        reverseString(chars,0,n-1);    //反转前k个字符串
        reverseString(chars,n,len-1);// 反转剩余字符
        System.out.println(chars);
    }

    public static void reverseString(char[] ch, int start,int end){
        while(start<end){
            char temp = ch[start];
            ch[start] = ch[end];
            ch[end] = temp;
            start++;
            end--;
        }
    }

}

总结

• 三次反转