题⽬描述

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

思路及解答

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

暴力移位

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

  • 时间复杂度：O(k×n)，其中k为移动次数，n为字符串长度

  • 空间复杂度：O(1)，只使用固定额外空间

字符串切片法（推荐）

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

  • 时间复杂度 O(n)

  • 空间复杂度 O(n) 。

或者可以用substring 的API

  • 时间复杂度：O(n)，substring操作需要线性时间

  • 空间复杂度：O(n)，创建新的字符串对象

三次反转（数学优美）

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

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

  • 时间复杂度：O(n)，每个字符被访问两次

  • 空间复杂度：O(1)，原地操作，只使用常数空间