LeetCode 541. 反转字符串 II

题目描述

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

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

数据范围

$1 \le s.length \le 10^4$ ，
$s$ 仅由小写英文组成，
$1 \le k \le 10^4$ 。

样例

输入样例1：

s = "abcdefg", k = 2

输出样例1：

"bacdfeg"

输入样例2：

s = "abcd", k = 2

输出样例2：

"bacd"

思路

每 $2k$ 为一组，翻转每组的前 $k$ 个字符。不足 $k$ 个字符，有多少翻转多少。

枚举每组的左端点 $i$ 和右端点 $min(i + k, n)$ 。（ $n$ 为整个字符串的长度，区间左闭右开）最后一组可能不足 $k$ 个字符，所以和字符串长度取最小值。

代码

C++

class Solution {
public:
    string reverseStr(string s, int k) {
        for ( int i = 0; i < s.size(); i += 2 * k ) 
            reverse(s.begin() + i, s.begin() + min(i + k, (int) s.size()));
        return s;
    }
};

Java

class Solution {
    public String reverseStr(String s, int k) {
        StringBuilder ss = new StringBuilder(s);
        for ( int i = 0; i < s.length(); i += 2 * k )
            reverse(ss, i, Math.min(i + k - 1, s.length() - 1));
        return ss.toString();
    }

    void reverse(StringBuilder s, int l, int r)
    {
        r --;
        while ( l < r )
        {
            char tmp = s.charAt(l);
            s.setCharAt(l ++, s.charAt(r));
            s.setCharAt(r --, tmp);
        }
    }
}