541 Reverse String II 反轉(zhuǎn)字符串 II
Description:
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]
題目描述:
給定一個(gè)字符串和一個(gè)整數(shù) k夕吻，你需要對(duì)從字符串開(kāi)頭算起的每個(gè) 2k 個(gè)字符的前k個(gè)字符進(jìn)行反轉(zhuǎn)涉馅。如果剩余少于 k 個(gè)字符黄虱，則將剩余的所有全部反轉(zhuǎn)。如果有小于 2k 但大于或等于 k 個(gè)字符晤揣，則反轉(zhuǎn)前 k 個(gè)字符朱灿，并將剩余的字符保持原樣。
示例 :
輸入: s = "abcdefg", k = 2
輸出: "bacdfeg"
要求:
該字符串只包含小寫的英文字母滞诺。
給定字符串的長(zhǎng)度和 k 在[1, 10000]范圍內(nèi)环疼。
思路:
每次取間隔 2k的長(zhǎng)度, 判斷是否超過(guò)字符串長(zhǎng)度, 將前 k位反轉(zhuǎn)即可
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
string reverseStr(string s, int k)
{
for (int i = 0; i < s.size(); i += k * 2)
{
if (i + k < s.size()) reverse(s, i, i + k - 1);
else reverse(s, i, s.size() - 1);
}
return s;
}
private:
void reverse(string &s, int i, int j)
{
while (i < j)
{
s[i] ^= s[j];
s[j] ^= s[i];
s[i++] ^= s[j--];
}
}
};
Java:
class Solution {
public String reverseStr(String s, int k) {
char c[] = s.toCharArray();
for (int i = 0; i < c.length; i += k * 2) {
if (i + k < c.length) reverse(c, i, i + k);
else reverse(c, i, c.length);
}
return new String(c);
}
private void reverse(char[] s, int from, int end) {
int i = from, j = end - 1;
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i++] ^= s[j--];
}
}
}
Python:
class Solution:
def reverseStr(self, s: str, k: int) -> str:
return ''.join([s[i:i + k][::-1] + s[i + k: i + 2 * k] for i in range(0, len(s), 2 * k)])
