网站如何防注册机,安徽省卫生计生网站医共体建设,聊城做手机网站推广,西安网站建设网站#x1f600;前言 在程序设计中#xff0c;字符串处理问题屡见不鲜#xff0c;其中“字符串左旋”是一种常见操作#xff0c;今天我们一起来探讨一个经典的左旋转字符串题目#xff0c;以及一种优雅的解决方案——三步翻转法。 #x1f3e0;个人主页#xff1a;尘觉主页… 前言 在程序设计中字符串处理问题屡见不鲜其中“字符串左旋”是一种常见操作今天我们一起来探讨一个经典的左旋转字符串题目以及一种优雅的解决方案——三步翻转法。 个人主页尘觉主页 文章目录 左旋转字符串题目链接题目描述分析与思路举例说明 代码实现代码详解 复杂度分析总结 左旋转字符串
题目链接
牛客网
题目描述
题目要求将给定字符串 SSS 从第 KKK 个位置分割为两个子串并互换位置。例如
输入 S abcXYZdefK 3输出XYZdefabc
解题的关键在于实现有效的字符串左旋即将字符串的前 KKK 个字符移到末尾形成新的字符串。
分析与思路
左旋转字符串可以通过切分字符串并拼接两部分的方式实现但这种方法可能会导致大量的内存复制。三步翻转法是一种更加高效的方式仅需对字符数组进行三次局部翻转即可完成目标操作
将前 KKK 个字符翻转。将剩余字符翻转。最后对整个字符串再翻转一次。
举例说明
以 S abcXYZdefK 3 为例
第一步翻转前 3 个字符 abc得到 cbaXYZdef。第二步翻转后续字符 XYZdef得到 cbaZYXfed。第三步将整个字符串翻转得到 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连支持一下创造不易您们的支持是我的动力
