【C++经典例题】字符串特定规则反转问题的解法
💓 博客主页：倔强的石头的ZEEKLOG主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：C++经典例题
期待您的关注
目录
问题描述
在字符串处理的编程领域中，经常会遇到各种复杂的规则要求。
本文将深入探讨一个给定字符串 s 和整数 k，按照特定规则反转字符串的问题。
要求从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符
- 如果剩余字符少于 k 个，则将剩余字符全部反转；
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
原题链接
解题思路
- 区间划分：解题的核心在于将字符串按照每 2k 个字符为一个区间进行划分。通过双指针的方式，定义一个左指针 left 来标记每个区间的起始位置，初始时 left 指向字符串的开头 s.begin()。
- 确定右边界：对于每个 2k 区间，需要确定其右边界 right。如果当前区间有足够的字符，即 left + 2*k 小于字符串的末尾 s.end()，那么右边界 right 就是 left + 2*k；否则，右边界 right 就是字符串的末尾 s.end()。这一步是为了确定一个2k区间
- 确定实际反转的右边界：在每个 2k 区间内，需要进一步确定实际反转的右边界 rightend。如果从 left 开始往后数 k 个字符不超过字符串末尾，即 (left + k) < s.end()，那么实际反转的右边界 rightend 就是 left + k；否则，实际反转的右边界 rightend 就是字符串的末尾 s.end()。这一步是为了满足题目中关于剩余字符数量不同时的反转规则
- 反转操作：确定了实际反转的左右边界后，使用 reverse 函数对 [left, rightend) 区间内的字符进行反转。
- 移动指针：完成一个区间的处理后，将左指针 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; } };- 初始化左指针：string::iterator left = s.begin(); 这行代码初始化了左指针 left，使其指向字符串 s 的开头。
- 循环处理区间：while(left < s.end()) 循环用于遍历整个字符串，只要左指针 left 还未到达字符串末尾，就继续处理下一个 2k 区间。
- 确定右边界：string::iterator right = (left + 2*k )< s.end()? left+ 2*k : s.end(); 这行代码根据当前 left 的位置和 2k 的长度，确定了当前 2k 区间的右边界 right。
- 确定实际反转的右边界：string::iterator rightend =(left + k)<s.end()? (left + k) : s.end(); 这行代码根据当前 left 的位置和 k 的长度，确定了实际需要反转的右边界 rightend。
- 反转操作：reverse(left,rightend); 这行代码调用 reverse 函数，对 [left, rightend) 区间内的字符进行反转。
- 移动左指针：left = right; 这行代码将左指针 left 移动到当前右边界 right 的位置，为处理下一个 2k 区间做准备。
复杂度分析
- 时间复杂度：由于每个字符最多被处理一次，所以时间复杂度为 O(n)，其中 n 是字符串的长度
- 空间复杂度：代码中只使用了常数级别的额外空间，如指针 left、right 和 rightend，所以空间复杂度为 O(1)
通过上述解题思路和代码实现，我们可以高效地解决这个字符串特定规则反转的问题。这种方法不仅逻辑清晰，而且在时间和空间复杂度上都达到了较好的性能。
