【C++经典例题】字符串特定规则反转问题的解法

问题描述

在字符串处理的编程领域中，经常会遇到各种复杂的规则要求。

本文将深入探讨一个给定字符串 s 和整数 k，按照特定规则反转字符串的问题。

要求从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符

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

原题链接

541. 反转字符串 II - 力扣（LeetCode）

解题思路

1. 区间划分：解题的核心在于将字符串按照每 2k 个字符为一个区间进行划分。通过双指针的方式，定义一个左指针 left 来标记每个区间的起始位置，初始时 left 指向字符串的开头 s.begin()。
2. 确定右边界：对于每个 2k 区间，需要确定其右边界 right。如果当前区间有足够的字符，即 left + 2*k 小于字符串的末尾 s.end()，那么右边界 right 就是 left + 2*k；否则，右边界 right 就是字符串的末尾 s.end()。这一步是为了确定一个2k区间
3. 确定实际反转的右边界：在每个 2k 区间内，需要进一步确定实际反转的右边界 rightend。如果从 left 开始往后数 k 个字符不超过字符串末尾，即 (left + k) < s.end()，那么实际反转的右边界 rightend 就是 left + k；否则，实际反转的右边界 rightend 就是字符串的末尾 s.end()。这一步是为了满足题目中关于剩余字符数量不同时的反转规则
4. 反转操作：确定了实际反转的左右边界后，使用 reverse 函数对 [left, rightend) 区间内的字符进行反转。
5. 移动指针：完成一个区间的处理后，将左指针 left 移动到当前右边界 right 的位置，以便处理下一个 2k 区间。重复上述步骤，直到左指针 left 到达字符串的末尾。

代码实现

class Solution {
public:
    string reverseStr(string s, int k) 
    {
        string::iterator left = s.begin();//初始左区间
        

        while(left < s.end())
        {
            //初始右区间
            string::iterator right = (left + 2*k )< s.end() ?  left+ 2*k : s.end();
            
            //确定右区间的实际值
            //剩余数量小于k，就全部反转；剩下数量大于k，就反转前k
            string::iterator rightend =(left + k)<s.end() ? (left + k) : s.end();

            reverse(left,rightend);
            
            //移动
            left = right;
            
        }
        return s;
    }
};

1. 初始化左指针：string::iterator left = s.begin(); 这行代码初始化了左指针 left，使其指向字符串 s 的开头。
2. 循环处理区间：while(left < s.end()) 循环用于遍历整个字符串，只要左指针 left 还未到达字符串末尾，就继续处理下一个 2k 区间。
3. 确定右边界：string::iterator right = (left + 2*k )< s.end()? left+ 2*k : s.end(); 这行代码根据当前 left 的位置和 2k 的长度，确定了当前 2k 区间的右边界 right。
4. 确定实际反转的右边界：string::iterator rightend =(left + k)<s.end()? (left + k) : s.end(); 这行代码根据当前 left 的位置和 k 的长度，确定了实际需要反转的右边界 rightend。
5. 反转操作：reverse(left,rightend); 这行代码调用 reverse 函数，对 [left, rightend) 区间内的字符进行反转。
6. 移动左指针：left = right; 这行代码将左指针 left 移动到当前右边界 right 的位置，为处理下一个 2k 区间做准备。

复杂度分析

1. 时间复杂度：由于每个字符最多被处理一次，所以时间复杂度为 O(n)，其中 n 是字符串的长度
2. 空间复杂度：代码中只使用了常数级别的额外空间，如指针 left、right 和 rightend，所以空间复杂度为 O(1)

通过上述解题思路和代码实现，我们可以高效地解决这个字符串特定规则反转的问题。这种方法不仅逻辑清晰，而且在时间和空间复杂度上都达到了较好的性能。