LeetCode 541. Reverse String II

1. 问题描述

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.

Example:

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]

2. 代码实现

2.1 方法1

使用整除运算和取模运算，以及swap函数，C++实现code如下：

class Solution { public: string reverseStr(string s, int k) { //处理可以被2k倍整除的字符 int nums_k = s.size() / (2 * k); int gap; for (int i = 0; i < nums_k; i++){ gap = i * 2 * k; for (int j = 0; j<k / 2; j++){ swap(s[j + gap], s[k - 1 - j + gap]); } } gap = nums_k * 2 * k; //处理2k整除后剩下的 int nums_left = s.size() % (2 * k); //如果剩下的字符个数比k少 if (nums_left < k){ for (int i = 0; i<nums_left / 2; i++){ swap(s[gap + i], s[gap + nums_left - 1 - i]); } } //如果剩下的字符个数大于等于k且小于2k else if (nums_left < 2 * k){ for (int i = 0; i < k / 2; i++){ swap(s[gap + i], s[gap + k - 1 - i]); } } return s; } };

2.2 方法2

使用标准库函数reverse()，C++实现code如下：

class Solution { public: string reverseStr(string s, int k) { //如果剩下的字符个数比k少 if (s.size() < k){ reverse(s.begin(), s.end()); } //如果剩下的字符个数大于等于k且小于2k else if (s.size() >= k && s.size() < 2 * k){ reverse(s.begin(), s.begin() + k); } else{ for (int i = 0; i<s.size(); i += 2 * k){ if ((i + k) < s.size()){ reverse(s.begin() + i, s.begin() + i + k); } else{ reverse(s.begin() + i, s.end()); } } } return s; } };

2.3 方法3

使用标准库函数reverse()和min()函数的简洁实现：

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