算法的学习笔记—左旋转字符串(牛客JZ58)

😀前言
在程序设计中，字符串处理问题屡见不鲜，其中“字符串左旋”是一种常见操作，今天我们一起来探讨一个经典的左旋转字符串题目，以及一种优雅的解决方案——三步翻转法。

🏠个人主页：尘觉主页

🥰左旋转字符串

题目链接

牛客网

💝题目描述

题目要求将给定字符串 SSS 从第 KKK 个位置分割为两个子串并互换位置。例如：

• 输入： S = "abcXYZdef"，K = 3
• 输出："XYZdefabc"

解题的关键在于实现有效的字符串左旋，即将字符串的前 KKK 个字符移到末尾，形成新的字符串。

💞分析与思路

左旋转字符串可以通过切分字符串并拼接两部分的方式实现，但这种方法可能会导致大量的内存复制。三步翻转法是一种更加高效的方式，仅需对字符数组进行三次局部翻转即可完成目标操作：

1. 将前 KKK 个字符翻转。
2. 将剩余字符翻转。
3. 最后对整个字符串再翻转一次。

举例说明

以 S = "abcXYZdef"，K = 3 为例：

1. 第一步：翻转前 3 个字符 abc，得到 cbaXYZdef。
2. 第二步：翻转后续字符 XYZdef，得到 cbaZYXfed。
3. 第三步：将整个字符串翻转，得到 XYZdefabc，即我们期望的结果。

💞代码实现

接下来，我们使用 Java 语言实现三步翻转法。此算法时间复杂度为 O(n)，仅需常数级的额外空间，因此在性能和空间占用上都表现优异。

public class Solution {public String LeftRotateString(String str, int n) {// 边界条件检查if (str == null || n >= str.length()) {return str;}// 转换为字符数组，方便操作char[] chars = str.toCharArray();// 第一步：翻转前 n 个字符reverse(chars, 0, n - 1);// 第二步：翻转后面的字符reverse(chars, n, chars.length - 1);// 第三步：将整个字符串翻转reverse(chars, 0, chars.length - 1);return new String(chars);}// 辅助函数：翻转指定区间的字符private void reverse(char[] chars, int i, int j) {while (i < j) {swap(chars, i++, j--);}}// 辅助函数：交换字符数组的两个元素private void swap(char[] chars, int i, int j) {char t = chars[i];chars[i] = chars[j];chars[j] = t;}
}

代码详解

• reverse函数：负责翻转字符数组中某个指定区间的字符。
• swap函数：用于交换字符数组中的两个字符。

通过这些辅助函数，我们只需 3 步完成了字符串的左旋转操作。

复杂度分析

• 时间复杂度：三次翻转，每次 O(n)O(n)O(n)，因此总时间复杂度为 O(n)O(n)O(n)。
• 空间复杂度：操作在原字符串的字符数组上进行，因此空间复杂度为 O(1)O(1)O(1)。

😄总结

在这道题目中，使用三步翻转法避免了直接拼接带来的额外开销，使得操作更加高效简洁。无论是面试还是实际开发中，这种方法都非常实用。

这个题目很好地锻炼了对字符串操作和数组翻转的理解，三步翻转法的思路在其他字符串旋转、数组循环移位等问题中也能得到广泛应用。希望这篇文章能帮助大家掌握并熟练应用这种方法。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞