题⽬描述

汇编语⾔中有⼀种移位指令叫做循环左移（ ROL ），现在有个简单的任务，就是⽤字符串模拟这个指令的运算结果。对于⼀个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列S=”abcXYZdef” ,要求输出循环左移3位后的结果，即“ XYZdefabc ”。是不是很简单？OK，搞定它！

思路及解答

这道题⽬的意思就是将前⾯ n 位，移动到后⾯，那么我们可以直接从第 n+1 位开始，遍历到最后⼀个，再拼接上前⾯ n 个。

暴力移位

通过k次单步左移实现循环左移。将第一个字符保存，其余字符前移，最后字符放到末尾

public class Solution {

    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n 

• 时间复杂度：O(k×n)，其中k为移动次数，n为字符串长度
• 空间复杂度：O(1)，只使用固定额外空间

字符串切片法（推荐）

值得注意的是， n 可能⼤于 str 的⻓度，那么这种情况下我们应该先对 str 的⻓度取余，保持严谨。即是： n = n % str.length(); 。

public class Solution {

	public String LeftRotateString(String str, int n) {
		if (str == null || str.length() == 0 || n 

• 时间复杂度 O(n)
• 空间复杂度 O(n) 。

或者可以用substring 的API

public class Solution {
    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n 

• 时间复杂度：O(n)，substring操作需要线性时间
• 空间复杂度：O(n)，创建新的字符串对象

三次反转（数学优美）

利用数学规律：BA = (A'B')'，通过三次反转实现循环左移。

分别反转前n位、剩余部分，最后整体反转

public class Solution {

    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n 

• 时间复杂度：O(n)，每个字符被访问两次
• 空间复杂度：O(1)，原地操作，只使用常数空间

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top