String Algorithm: Reverse the first k characters for every 2k ch

  • 时间:2020-09-23 15:11:59
  • 分类:网络文摘
  • 阅读:86 次

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]

The problem statement is actually a bit hard to understand, but once you get it, this problem is easy to solve.

How to Reverse string in C++ using std::reverse for the first k characters?

The std::C++ has a handy reverse method that takes two iterators, and reverse it. Thus, we can iterate from the start, and increment the step of 2*k, compute the range, which is then passed to the reverse function to do the work.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            reverse(begin(s) + a, begin(s) + b);
        }
        return s;
    }
};
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            reverse(begin(s) + a, begin(s) + b);
        }
        return s;
    }
};

You can also use a two pointer to swap until they meet in the middle.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};

Other string reversing algorithms:

  • How to Reverse Words in a String in Place using C++ std::reverse?
  • How to Reverse Words in a String?
  • How to Reverse Only Letters in a String?
  • How to Reverse Vowels of a String in C/C++?
  • Reverse String in C/C++

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
白酒市场虚假宣传潜规则:年份造假工艺虚标  三种适合春分时节吃的常见养生食物  电脑族需要多吃一些明目功能的食物  有些食物发芽后营养价值会变得更高  春季健康食谱:可以适当吃些新鲜蚕豆  多个品牌婴幼儿配方乳粉被曝配方都一样  新食品安全法“史上最严”建立惩罚制度  适合在夏天吃的既简单又美味的凉拌菜  薏米与红豆的多种搭配煮法可健脾养血  好时巧克力1年3上黑榜 违规使用维生素E 
评论列表
添加评论