541. 反转字符串 II

转载自Leet Code

题目描述

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。 如果剩余字符少于 k 个，则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例: >输入: s = "abcdefg", k = 2 >输出: "bacdfeg"

提示： - 该字符串只包含小写英文字母。 - 给定字符串的长度和 k 在 [1, 10000] 范围内。

---

我的代码

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}

class MySolution541 
{
    public String reverseStr(String s, int k) 
    {
    	if (s==null||s.length()<=0) return s;
    	char []str = s.toCharArray();
    	
    	int i0 = 0, ik = k-1, j = 2*k-1;
    	while (i0<str.length&&ik<str.length&&j<str.length)
    	{
    		for (int ii0 = i0, iik = ik; ii0<iik; ii0++,iik--)
    		{
    			char tmp = str[ii0]; str[ii0] = str[iik]; str[iik] = tmp;
    		}
    		i0 += 2*k; ik += 2*k; j += 2*k;
    	}
    	if (i0>=str.length) 
    		return new String(str);
    	else if (ik>=str.length)
    	{
    		for (int ii0 = i0, iik = str.length-1; ii0<iik; ii0++,iik--)
    		{
    			char tmp = str[ii0]; str[ii0] = str[iik]; str[iik] = tmp;
    		}
    		return new String(str);
    	}
    	else
    	{
    		for (int ii0 = i0, iik = ik; ii0<iik; ii0++,iik--)
    		{
    			char tmp = str[ii0]; str[ii0] = str[iik]; str[iik] = tmp;
    		}
    		return new String(str);
    	}
    }
}

方法：暴力 (更漂亮的代码)

\(T(N) = O(N)\), \(S(N) = O(N)\)

我们直接翻转每个2k字符块。 每个块开始于2k的倍数，也就是0, 2k, 4k, 6k, ...。 需要注意的一件事是：如果没有足够的字符，我们并不需要翻转这个块。 为了翻转从i到j的字符块，我们可以交换位于i++和j--的字符。

---

代码

{.line-numbers}

class Solution541 
{
    public String reverseStr(String s, int k) 
	{
        char[] str = s.toCharArray();

        for (int start = 0; start < str.length; start += 2 * k) 
		{
            int i = start, j = Math.min(start + k - 1, str.length - 1);
            while (i < j) 
			{
                char tmp = str[i]; str[i++] = str[j]; str[j--] = tmp;
            }
        }
        return new String(str);
    }
}