541.反转字符串II

2023-12-16 09:32:34

题目描述

给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,剩余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"
解释: 从字符串开头算起,第一组 2k 字符是 "ab",第二组 2k 字符是 "cd",所以最终答案是 "bacdfeg"

提示:

  • 该字符串只包含小写英文字母。
  • 给定字符串的长度和 k 在 [1, 10000] 范围内。

解题思路

类比和解题步骤

考虑类比:假设你有一条领带,你希望每隔一段距离将其中的一部分领带反转。你可以通过遍历字符串,按照规定的间隔(2k)对每一部分进行反转。

  1. 遍历字符串: 从字符串的开头开始,按照 2k 的间隔遍历字符串。
  2. 反转部分字符: 对每一部分的前 k 个字符进行反转。
  3. 处理剩余字符: 如果剩余字符少于 k 个,则将其全部反转。
特殊案例
  • 如果输入字符串为空,则直接返回空字符串。

C#代码实现

public string ReverseStr(string s, int k) {
    // 如果字符串为空或者 k 小于等于 0,则直接返回
    if (string.IsNullOrEmpty(s) || k <= 0) {
        return s;
    }

    // 将字符串转换为字符数组
    char[] charArray = s.ToCharArray();
    int n = charArray.Length;

    // 遍历字符数组,每隔 k 个字符反转一次
    for (int i = 0; i < n; i += 2 * k) {
        // 左指针
        int left = i;
        // 右指针,取最小值,防止数组越界
        int right = Math.Min(i + k - 1, n - 1);

        // 交换左右指针指向的字符,并移动指针
        while (left < right) {
            // 反转前 k 个字符
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;

            // 移动指针
            left++;
            right--;
        }
    }

    // 将字符数组转换为字符串
    return new string(charArray);
}

C代码实现

char* reverseStr(char* s, int k) {
    // 如果传入的字符串为空或者 k 小于等于 0,则直接返回
    if (s == NULL || k <= 0) {
        return s;
    }

    // 获取字符串长度
    int n = strlen(s);

    // 遍历字符串,每隔 k 个字符反转一次
    for (int i = 0; i < n; i += 2 * k) {
        // 记录左指针
        int left = i;
        // 记录右指针,如果右指针超过字符串长度,则取字符串最后一个字符
        int right = fmin(i + k - 1, n - 1);

        // 交换左右指针指向的字符,并移动指针
        while (left < right) {
            // 反转前 k 个字符
            // 交换左右指针指向的字符
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            // 移动指针
            left++;
            right--;
        }
    }

    return s;
}

时间复杂度和空间复杂度

  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。遍历字符串一次。
  • 空间复杂度:O(1)。只使用了常数级别的额外空间。

文章来源:https://blog.csdn.net/Ammmmmmmmn/article/details/135026077
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。