【C语言】字符串左旋的三种解题方法详细分析

💯前言

• 在这篇文章中，我们将深入探讨字符串左旋的三种解决方案，系统分析每种方法的算法设计、时间复杂度与空间复杂度，以及其适用场景和局限性。这些方法从简单到高效，分别展示了逐字符移动法、使用辅助空间法和三次反转法的不同特点及其理论基础。
  通过对这些方法的详细对比与讨论，读者将对字符串操作的基本原理有更为深入的理解，掌握在不同应用场景下如何选择最优的解决方案，以提升代码的效率与鲁棒性。
  C语言
  

💯题目描述

实现一个函数，能够左旋字符串中的 k 个字符。

例如：

• 给定字符串 ABCD，如果左旋 1 个字符，得到 BCDA。
• 如果左旋 2 个字符，得到 CDAB。

左旋是指将字符串的前面部分字符移到字符串的末尾。我们将使用三种不同的实现方式来解决这一问题：逐字符移动法、使用辅助空间法、以及三次反转法。

💯方法一：逐字符移动法

思路

逐字符移动法是一种直观的实现方式，通过多次迭代将字符串的第一个字符移动到末尾，直到完成所需的旋转次数。该方法依赖于不断移动字符的位置以达到最终目标。其本质是一种线性搬移操作，容易理解，但在大数据量的情况下效率较低。

代码实现

void leftRound(char* str, int k) {
    int len = strlen(str);
    int time = k % len;

    for (int i = 0; i < time; i++) {
        char tmp = str[0];
        int j = 0;
        for (; j < len - 1; j++) {
            str[j] = str[j + 1];
        }
        str[j] = tmp;
    }
}

int main() {
    char str[] = "abcdef";
    leftRound(str, 7);
    printf("%s\n", str);
    return 0;
}

解释

• 获取字符串长度 len。
• 计算实际旋转次数 time = k % len，这样可以避免 k 超过字符串长度导致的冗余操作。
• 外层循环用于执行 time 次旋转，每次只移动一个字符。
• 使用内部的 for 循环，将每个字符依次前移一个位置，最后将原来的第一个字符移到末尾。

时间复杂度和空间复杂度

• 时间复杂度：O(k * len)，对于每次旋转都需要遍历整个字符串，因而效率较低。
• 空间复杂度：O(1)，只需一个额外的字符变量来暂存被移动的字符。

优缺点

• 这种方法的优点是实现简单且易于理解，适合初学者用于理解字符串旋转的基本概念。但其缺点在于效率较低，尤其在 k 较大和字符串长度较长时，由于需要多次逐字符移动，时间开销会显著增加。

💯方法二：使用辅助空间法

思路

使用辅助空间法通过将旋转后的字符串临时保存，再将结果复制回原字符串。借助辅助空间将两个部分拼接，可以有效避免逐字符移动带来的低效问题。该方法的核心在于利用辅助数组，快速完成字符串的局部重组与合并。

代码实现

void leftRound(char* str, int k) {
    int len = strlen(str);
    int time = k % len;
    char tmp[256] = { 0 };

    strcpy(tmp, str + time); 
    strncat(tmp, str, time); 
    strcpy(str, tmp);
}

int main() {
    char str[] = "abcdef";
    leftRound(str, 7);
    printf("%s\n", str);
    return 0;
}

解释

• 通过 strlen 获取字符串的长度。
• 计算实际的旋转次数 time = k % len，以应对 k 过大时的情况。
• 使用临时数组 tmp 存储旋转后的结果。
• 利用 strcpy 函数将原字符串从 time 索引位置开始的部分复制到 tmp 中。
  • strcpy(tmp, str + time)：str + time 表示指向原字符串从第 time 个位置开始的指针，strcpy 函数将从这个位置开始的所有字符（直到字符串结束符 �）复制到 tmp 中。因此，tmp 中最初会存储字符串的后半部分。例如，若 str = "ABCD" 且 time = 2，strcpy(tmp, str + time) 将 "CD" 复制到 tmp，结果为 tmp = "CD"。
• 使用 strncat 函数将原字符串的前 time 个字符拼接到 tmp 的末尾。
  • strncat(tmp, str, time)：strncat 用于将源字符串的指定数量字符拼接到目标字符串的末尾。在这里，str 表示原字符串，time 表示从 str 开头开始的 time 个字符。因此，strncat(tmp, str, time) 将原字符串的前 time 个字符（即 "AB"）拼接到 tmp 的末尾，形成最终结果。例如，当 tmp = "CD"，time = 2 时，拼接后结果为 tmp = "CDAB"。
• 最后使用 strcpy 将 tmp 的内容复制回原字符串 str，完成旋转操作。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，只需遍历字符串几次即可完成旋转。
• 空间复杂度：O(n)，需要额外的存储空间来保存旋转后的结果。

优缺点

• 辅助空间法的优势在于其高效的操作，尤其适合处理较大的字符串，但需要额外的空间来存储结果。因此，对于内存资源受限的情况，该方法可能不太适合。

💯方法三：三次反转法

思路

三次反转法通过对字符串的部分片段进行反转，从而达到整体左旋的效果。核心思想是将字符串划分为两部分，分别反转，再对整体反转，以实现最终的左旋。

这种方法以极少的操作步骤完成字符位置的重新排列，具有较高的效率和数学美感。

代码实现

void ReverseRange(char* str, int start, int end) {
    int left = start;
    int right = end;
    while (left < right) {
        char tmp = str[left];
        str[left] = str[right];
        str[right] = tmp;
        left++;
        right--;
    }
}

void leftRound(char* str, int k) {
    int len = strlen(str);
    int time = k % len;
    ReverseRange(str, 0, time - 1);    // 反转前 time 个字符
    ReverseRange(str, time, len - 1);  // 反转剩余部分
    ReverseRange(str, 0, len - 1);     // 反转整个字符串
}

int main() {
    char str[] = "abcdef";
    leftRound(str, 7);
    printf("%s\n", str);
    return 0;
}

解释

1. 反转前 time 个字符

   • 调用 ReverseRange(str, 0, time - 1)，反转字符串的前 time 个字符。
   • 例如，对 "ABCD" 反转前两个字符，得到 "BACD"。

2. 反转剩余部分

   • 调用 ReverseRange(str, time, len - 1)，反转剩余部分。
   • 对 "BACD" 中的后两个字符反转，得到 "BADC"。

3. 反转整个字符串

   • 调用 ReverseRange(str, 0, len - 1)，反转整个字符串。
   • 对 "BADC" 反转得到 "CDAB"，从而完成左旋操作。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，三次反转操作均为线性时间复杂度，因此总时间复杂度为 O(n)。
• 空间复杂度：O(1)，只需进行交换操作，没有额外的空间开销。

优缺点

• 三次反转法的优势在于其高效性，时间复杂度为 O(n)，空间复杂度为 O(1)，适合处理大规模字符串。该方法通过反转实现字符串的重新排列，以最小的时间和空间成本实现左旋，非常适合实际开发中的高效实现。

💯方法对比与总结

• 逐字符移动法 适合初学者理解字符串旋转的概念，但效率不高。在字符较多或者旋转次数较大时，可能会因为需要逐次移动而显得低效。
• 辅助空间法 则通过一次性拼接字符串提升了效率，但需要额外的空间存储，对于空间资源紧张的场景可能不适合。
• 三次反转法 是最优的方法，尤其适合大规模字符串。它的空间复杂度最低且效率高，是一个非常经典的字符串操作技巧。该方法不仅巧妙而且具有一定的数学美感，通过三次反转将字符串重新排列到目标位置。

拓展思考

• 这些字符串旋转的实现方法可以拓展到其他类型的数据结构，例如数组的左旋、右旋操作。对于数组来说，三次反转法同样有效，可以通过类似的思路对数组元素进行重新排列。
• 三次反转法的思想不仅可以用于字符串旋转，还可以用于链表、数组等其他序列的数据结构。它是一种通用的思想，可以帮助解决许多涉及顺序调整的问题。
• 对于多种编程语言，我们也可以找到相似的实现方法。Python 中可以使用字符串切片操作来轻松实现左旋，而 Java 中可以借助 StringBuilder 进行高效的字符串操作。Python 的切片方法非常直观，例如可以使用 s = s[k:] + s[:k] 来实现左旋操作，简洁而高效。
• 对于面试场景，理解这些方法的时间复杂度和空间复杂度，以及不同方法在实际应用中的适用性非常重要。面试官通常希望看到你对基础方法的掌握以及对最优解法的深入理解。

💯总结

• 
  字符串左旋是一个非常基础但又非常经典的字符串操作问题。通过这篇文章的深入解读，我们详细探讨了三种不同的解决方案，并对每种方法的算法复杂度、适用场景、优缺点进行了深入分析。掌握这些方法有助于我们在面试中应对字符串操作类的问题，也能帮助我们在实际开发中写出更优雅、高效的代码。这三种方法展示了从基础到高效的不同解决思路，是学习和掌握字符串操作的宝贵经验。
  希望这篇文章能够激发你对字符串操作的更深入思考与理解。未来的学习和工作中，愿你能够灵活应用这些技巧，优化代码的效率与可读性，深入理解不同方法背后的原理，并能够在解决问题时选择最合适的工具。这正是编程的艺术，也是不断提升的动力所在。