0541. Reverse String II ======================= 题目信息 -------- :题号: 0541 :难度: Easy :主题: 字符串分块、每 2k 个字符、局部反转、尾部规则 :原题: `LeetCode 0541 `_ :重点: 每个 2k 分组只反转前 k 个字符、尾部少于 k 时全部反转、尾部介于 k 与 2k 时只反转前 k 个 题目重述 -------- 给定字符串 ``s`` 和正整数 ``k``。从字符串开头起,每连续 ``2k`` 个字符视为一组,把每组的前 ``k`` 个字符反转,后 ``k`` 个字符保持原顺序。 若最后剩余字符少于 ``k`` 个,则把这些字符全部反转;若剩余字符数量不少于 ``k`` 但少于 ``2k``,则只反转其中前 ``k`` 个字符。返回处理后的字符串。 自建示例 -------- 尾部介于 k 与 2k 之间: .. code-block:: text 输入:s = "abcdefghij",k = 3 输出:"cbadefihgj" 解释:前六个字符中 abc 被反转;剩余 ghij 有四个字符,只反转前 3 个得到 ihgj。 尾部少于 k: .. code-block:: text 输入:s = "abcd",k = 6 输出:"dcba" 解释:整个字符串长度小于 k,因此全部反转。 以 ``2k`` 为步长处理局部区间 ---------------------------- 从下标 0 开始,每次定位一个长度最多为 ``2k`` 的块,只反转该块的前 ``k`` 个字符;``std::min(i+k, n)`` 自动处理尾部不足 ``k`` 的情况。块的后半段从未被传给反转区间,因此保持原序。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string reverseStr(std::string s, int k) { for (int begin = 0; begin < static_cast(s.size()); begin += 2 * k) { int end = std::min(begin + k, static_cast(s.size())); std::reverse(s.begin() + begin, s.begin() + end); } return s; } }; 代码分析 -------- 每个字符恰好属于一个长度 ``2k`` 的处理块,块内只有前 ``k`` 个位置被反转;最后一个块的三种长度关系由截断边界统一覆盖。时间复杂度为 ``O(n)``,额外空间复杂度为 ``O(1)``(不计输入副本)。