C#LeetCode刷题之#541-反转字符串 II（Reverse String II）

问题

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

输入: s = "abcdefg", k = 2

输出: "bacdfeg"

要求:

该字符串只包含小写的英文字母。

给定字符串的长度和 k 在[1, 10000]范围内。

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Input: s = "abcdefg", k = 2

Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.

Length of the given string and k will in the range [1, 10000]

示例

public class Program {

    public static void Main(string[] args) {

        var s = "abcdefg";

        var k = 2;

        var res = ReverseStr(s, k);

        Console.WriteLine(res);

        s = "abcdefg";

        k = 3;

        res = ReverseStr2(s, k);

        Console.WriteLine(res);

        s = "abcdefg";

        k = 8;

        res = ReverseStr3(s, k);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static string ReverseStr(string s, int k) {

        if(k > s.Length) return new string(s.Reverse().ToArray());

        var nums = Math.Ceiling(s.Length / (double)k);

        var sb = new StringBuilder(s);

        for(var i = 0; i < nums; i += 2) {

            var start = i * k;

            var end = Math.Min(s.Length - 1, start + k - 1);

            while(start < end) {

                var swap = sb[start];

                sb[start] = sb[end];

                sb[end] = swap;

                start++;

                end--;

            }

        }

        return sb.ToString();

    }

    private static string ReverseStr2(string s, int k) {

        var chars = s.ToCharArray();

        var offset = 2 * k;

        for(var i = 0; i < chars.Length; i += offset) {

            if(i + k > chars.Length) Array.Reverse(chars, i, chars.Length - i);

            else Array.Reverse(chars, i, k);

        }

        return new string(chars);

    }

    private static string ReverseStr3(string s, int k) {

        var list = new List<string>();

        for(var i = 0; i < s.Length; i += k) {

            if(i + k < s.Length) list.Add(s.Substring(i, k));

            else list.Add(s.Substring(i, s.Length - i));

        }

        return string.Join("", list.Select((v, i) => i % 2 == 0 ? new string(v.Reverse().ToArray()) : v));

    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

bacdfeg

cbadefg

gfedcba

分析：

显而易见，以上3种算法的时间复杂度均为 $O(n)$ 。

巴特西

C#LeetCode刷题之#541-反转字符串 II（Reverse String II）

最新文章

热门文章