Easy

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

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

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 10^4
  • s 仅由小写英文字母组成
  • 1 <= k <= 10^4

解题思路

这是一道模拟类题目，关键在于理解题意和找到规律。

思路分析：

  1. 规律观察：每 2k 个字符为一组，对每组的前 k 个字符进行反转
  2. 边界处理：当剩余字符不足时，需要分情况讨论：
    • 剩余字符 < k：全部反转
    • k ≤ 剩余字符 < 2k：只反转前 k 个

解法一：双指针反转（推荐） 遍历字符串，每次跳跃 2k 个位置，对每个区间的前 k 个字符使用双指针进行原地反转。时间复杂度 O(n)，空间复杂度 O(1)。

解法二：字符串切片 将字符串按照规律切分成段，对需要反转的段进行反转后重新拼接。实现简单但可能有额外的字符串操作开销。

核心在于正确处理边界情况和利用双指针高效反转子串。

代码实现

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.length();
        
        for (int i = 0; i < n; i += 2 * k) {
            // 确定需要反转的右边界
            int right = min(i + k - 1, n - 1);
            
            // 双指针反转
            int left = i;
            while (left < right) {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        s = list(s)  # 转换为可变列表
        n = len(s)
        
        for i in range(0, n, 2 * k):
            # 确定需要反转的右边界
            right = min(i + k - 1, n - 1)
            
            # 双指针反转
            left = i
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        
        return ''.join(s)

public class Solution {
    public string ReverseStr(string s, int k) {
        char[] chars = s.ToCharArray();
        int n = chars.Length;
        
        for (int i = 0; i < n; i += 2 * k) {
            // 确定需要反转的右边界
            int right = Math.Min(i + k - 1, n - 1);
            
            // 双指针反转
            int left = i;
            while (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new string(chars);
    }
}

var reverseStr = function(s, k) {
    const chars = s.split('');
    const n = chars.length;
    
    for (let i = 0; i < n; i += 2 * k) {
        // 确定需要反转的右边界
        let right = Math.min(i + k - 1, n - 1);
        
        // 双指针反转
        let left = i;
        while (left < right) {
            [chars[left], chars[right]] = [chars[right], chars[left]];
            left++;
            right--;
        }
    }
    
    return chars.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串，每个字符最多被访问常数次
空间复杂度O(1) 或 O(n)C++ 原地修改为 O(1)；Python/JS 需要转换为可变结构为 O(n)

相关题目