剑指 Offer 58-II 左旋转字符串LeetCode-Book 中四种解法与字符串拼接效率深度解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库 剑指 Offer 58 - II. 左旋转字符串字符串.md) 的完整解析围绕将字符串s的前n个字符移动到末尾这一核心操作系统讲解字符串切片、列表遍历拼接、字符串遍历拼接、三次翻转四种解法。读完后你不仅能掌握各语言Python / Java / C的实现细节还能理解字符串是不可变对象这一底层概念对拼接效率的巨大影响在面试与工程实践中做出正确的选型。题目与核心思想本题要求实现函数reverseLeftWords(s, n)把字符串s的前n个字符移动到字符串的尾部保持其余字符相对顺序不变。例如s abcdefg、n 2时结果为cdefgba。从数学视角看这本质上是循环队列的视角变换字符串被看作一个长度为N的环旋转操作只是把起点从下标0移动到下标n字符本身没有任何搬移。这一认识是后续所有解法包括求余简化写法的共同基础。原文档给出四种方法各有明确的适用场景方法核心手段时间复杂度空间复杂度典型适用场景方法一字符串切片切片 拼接O(N)O(N)一般场景效率最高方法二列表遍历拼接可变缓冲区逐字符追加O(N)O(N)面试禁用切片函数时方法三字符串遍历拼接不可变字符串反复拼接O(N)O(N)Python 禁用join()、Java 只能用String时方法四三次翻转原地区间反转O(N)O(1)C 等字符串可变语言仓库中每种语言均提供了可独立运行的完整代码文件统一使用测试用例s abcdefg,n 2预期输出cdefgba。以下逐一展开。方法一字符串切片应用字符串切片函数是最直接的做法取出s[n:]与s[:n]两个切片用拼接运算符组合即可返回结果。class Solution: def reverseLeftWords(self, s: str, n: int) - str: return s[n:] s[:n]class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) s.substring(0, n); } }class Solution { public: string reverseLeftWords(string s, int n) { return s.substr(n, s.size()) s.substr(0, n); } };复杂度分析时间复杂度 O(N)其中N为字符串s的长度。切片/substring为线性时间复杂度。空间复杂度 O(N)两个切片的总长度为N。该方法新建两切片字符串后一次拼接成结果字符串全程无冗余的逐字符操作是三种 Python 方法中效率最高的写法。仓库中三种语言对应实现分别是 Python 切片解法、Java 切片解法 与 C 切片解法均附带main/ 驱动代码可直接运行验证。方法二列表遍历拼接含求余简化若面试规定不允许使用切片函数则采用逐字符遍历拼接。算法流程新建一个listPython、StringBuilderJava记为res先向res添加第n1位至末位的字符再向res添加首位至第n位的字符将res转化为字符串并返回。class Solution: def reverseLeftWords(self, s: str, n: int) - str: res [] for i in range(n, len(s)): res.append(s[i]) for i in range(n): res.append(s[i]) return .join(res)class Solution { public String reverseLeftWords(String s, int n) { StringBuilder res new StringBuilder(); for(int i n; i s.length(); i) res.append(s.charAt(i)); for(int i 0; i n; i) res.append(s.charAt(i)); return res.toString(); } }复杂度分析时间复杂度 O(N)线性遍历s并逐个添加使用线性时间。空间复杂度 O(N)辅助列表res使用 O(N) 额外空间。对应仓库实现为 Python 列表拼接解法 与 Java StringBuilder 解法。求余简化写法由于旋转本质是环上的视角移动用i % len(s)可以直接从下标n绕环读回下标0把两段循环合并为一段class Solution: def reverseLeftWords(self, s: str, n: int) - str: res [] for i in range(n, n len(s)): res.append(s[i % len(s)]) return .join(res)class Solution { public String reverseLeftWords(String s, int n) { StringBuilder res new StringBuilder(); for(int i n; i n s.length(); i) res.append(s.charAt(i % s.length())); return res.toString(); } }仓库中 Python 求余版 与 Java 求余版 验证了该写法在两种语言下行为一致。从源码结构看求余写法在n len(s)的越界情形下同样能安全绕环而朴素切片写法则会因substring参数越界而抛出异常这是两者鲁棒性上的一个隐性差异。方法三字符串遍历拼接含求余简化若规定 Python 不能使用join()函数或规定 Java 只能用String则使用此方法。它与方法二思路一致区别是用不可变字符串代替可变列表。class Solution: def reverseLeftWords(self, s: str, n: int) - str: res for i in range(n, len(s)): res s[i] for i in range(n): res s[i] return resclass Solution { public String reverseLeftWords(String s, int n) { String res ; for(int i n; i s.length(); i) res s.charAt(i); for(int i 0; i n; i) res s.charAt(i); return res; } }对应仓库实现为 Python 字符串拼接解法。复杂度分析时间复杂度 O(N)线性遍历s并添加使用线性时间。空间复杂度 O(N)假设循环过程中内存能被及时回收内存中至少同时存在长度为N和N-1的两个字符串新建长度N的res需要前一个长度N-1的res因此至少使用 O(N) 额外空间。同样可利用求余运算简化为单循环class Solution: def reverseLeftWords(self, s: str, n: int) - str: res for i in range(n, n len(s)): res s[i % len(s)] return resclass Solution { public String reverseLeftWords(String s, int n) { String res ; for(int i n; i n s.length(); i) res s.charAt(i % s.length()); return res; } }对应 Python 字符串求余版。效率对比字符串不可变对象是性能分水岭三种 Python/Java 解法都涉及字符串为不可变对象这一关键概念导致效率差距显著。原文档给出了实测数据以 Python 为例结论同样适用于 Java测试数据长度为10000000的全为1的字符串s 1 * 10000000方法一测试新建两切片后一次拼接无冗余操作效率最高# 运行时间: 0.01 秒 def func1(s): cut len(s) // 3 return s[:cut] s[cut:]方法二测试列表 / StringBuilder 均为可变对象每轮只是向尾部追加一个元素最终转字符串时系统仅申请一次内存# 运行时间: 1.86 秒 def func2(s): res [] for i in range(len(s)): res.append(s[i]) # 仅需在列表尾部添加元素 return .join(res)方法三测试字符串是不可变对象每轮拼接都需新建一个字符串系统需申请 N 次内存数据量大时效率低下# 运行时间: 6.31 秒 def func3(s): res for i in range(len(s)): res s[i] # 每次拼接都需要新建一个字符串 return res同一量级下方法一0.01 秒与方法三6.31 秒相差近三个数量级。这里的根本原因可以归纳为可变 vs 不可变list/StringBuilder的append是 O(1) 均摊操作而res ch每次都构造一个全新的字符串对象并拷贝已有内容总拷贝量呈 O(N²) 的趋势增长常数层面却表现为申请 N 次内存一次性定容.join(res)在调用时已知总长度可一次分配目标内存再批量填充避免了反复扩容与拷贝工程结论在需要逐字符构造长字符串的场景优先选可变缓冲区 一次性转串方法二能直接用切片时优先切片方法一尽量避免在循环里对不可变字符串做拼接方法三。方法四三次翻转法C 原地操作O(1) 空间由于 C 中的std::string是可变类型可以在原字符串上直接操作实现旋转从而把空间复杂度压到 O(1)。数学原理设s s₁s₂即前n个字符为s₁其余为s₂记反转操作为ˆ则左旋转结果s₂s₁满足s₂s₁ ˆ(ˆs₁ · ˆs₂)即先分别反转两段再整体反转。原文档给出的例子s abcdefg、s₁ ab、s₂ cdefg则ˆs₁ ba、ˆs₂ gfedcˆ(bagfedc) cdefgba即为所求。复杂度分析时间复杂度 O(N)共线性遍历s两轮三次区间反转合计 1.5 倍长度。空间复杂度 O(1)原地字符串操作仅使用常数大小额外空间除函数调用栈外。实现一自行实现翻转函数reverseString()class Solution { public: string reverseLeftWords(string s, int n) { reverseString(s, 0, n - 1); reverseString(s, n, s.size() - 1); reverseString(s, 0, s.size() - 1); return s; } private: void reverseString(string s, int i, int j) { while(i j) swap(s[i], s[j--]); } };实现二使用 STL 库函数reverseclass Solution { public: string reverseLeftWords(string s, int n) { reverse(s.begin(), s.begin() n); reverse(s.begin() n, s.end()); reverse(s.begin(), s.end()); return s; } };仓库中 C 自定义翻转版 与 C 库函数版 分别对应上述两种实现均以标准测试用例s abcdefg,n 2驱动运行输出cdefgba。从源码结构看两次区间反转均要求i j才交换begin() n到end()在n恰好等于长度时退化为空区间因此该方法对空区间天然安全而方法一至三在n 0或n len(s)边界下分别表现为原样返回行为同样正确面试时可按需说明。解法选型小结与仓库代码索引通用场景优先切片法方法一一行代码、O(N) 时间且实测最快禁用切片时用列表 /StringBuilder逐字符追加方法二注意最终必须一次性join/toString禁用join且只能用不可变String时方法三可用但应明确知道循环内拼接在大输入下的内存申请代价追求原地、常数空间C三次翻转法掌握ˆ(ˆs₁ˆs₂) s₂s₁这一恒等式即可推导。各语言全部实现均在仓库中可运行建议配合原文档交叉阅读题目解析剑指 Offer 58 - II. 左旋转字符串Pythons1 切片 / s2 列表 / s3 列表求余 / s4 字符串 / s5 字符串求余sfo_58ii_left_rotation_of_a_string_s1.py、sfo_58ii_left_rotation_of_a_string_s2.py、sfo_58ii_left_rotation_of_a_string_s3.py、sfo_58ii_left_rotation_of_a_string_s4.py、sfo_58ii_left_rotation_of_a_string_s5.pyJavas1 切片 / s2 StringBuilder / s5 求余版sfo_58ii_left_rotation_of_a_string_s1.java、sfo_58ii_left_rotation_of_a_string_s2.java、sfo_58ii_left_rotation_of_a_string_s5.javaCs1 切片 / s2 自定义翻转 / s3 库函数翻转sfo_58ii_left_rotation_of_a_string_s1.cpp、sfo_58ii_left_rotation_of_a_string_s2.cpp、sfo_58ii_left_rotation_of_a_string_s3.cpp本地运行时各语言代码目录自带测试驱动s abcdefg,n 2预期输出cdefgbaPython 可直接python sfo_58ii_left_rotation_of_a_string_s1.py运行Java / C 需先编译含main的入口文件再执行各文件均通过相对include头引用公共依赖。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考