当前位置：首页 > article >正文

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

article 2024/10/28 10:10:08

在这里插入图片描述

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

🏠个人主页：尘觉主页

文章目录

🥰左旋转字符串
- 题目链接
- 💝题目描述
- 💞分析与思路
- - 举例说明
- 💞代码实现
- - 代码详解
- 复杂度分析
- 😄总结

🥰左旋转字符串

题目链接

牛客网

💝题目描述

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

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

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

💞分析与思路

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

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

举例说明

以 S = "abcXYZdef"，K = 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;
    }
}