Skip to content

Latest commit

 

History

History
148 lines (107 loc) · 5.29 KB

0541.反转字符串II.md

File metadata and controls

148 lines (107 loc) · 5.29 KB
Raw

欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

简单的反转还不够，我要花式反转

541. 反转字符串II

https://leetcode-cn.com/problems/reverse-string-ii/

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

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

思路

这道题目其实也是模拟，实现题目中规定的反转规则就可以了。

一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

性能如下：

那么这里具体反转的逻辑我们要不要使用库函数呢，其实用不用都可以，使用reverse来实现反转也没毛病，毕竟不是解题关键部分。

C++代码

使用C++库函数reverse的版本如下：

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s.begin() + i, s.begin() + s.size());
        }
        return s;
    }
};

那么我们也可以实现自己的reverse函数，其实和题目344. 反转字符串道理是一样的。

下面我实现的reverse函数区间是左闭右闭区间，代码如下：

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s, i, i + k - 1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s, i, s.size() - 1);
        }
        return s;
    }
};

其他语言版本

Java：

class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();

        for (int i = 0; i < s.length(); i += (2 * k)) {
            StringBuffer temp = new StringBuffer();
            // 剩余字符大于 k 个，每隔 2k 个字符的前 k 个字符进行反转
            if (i + k <= s.length()) {
                // 反转前 k 个字符
                temp.append(s.substring(i, i + k));
                res.append(temp.reverse());

                // 反转完前 k 个字符之后，如果紧接着还有 k 个字符，则直接加入这 k 个字符
                if (i + 2 * k <= s.length()) {
                    res.append(s.substring(i + k, i + 2 * k));
                // 不足 k 个字符，则直接加入剩下所有字符
                } else {
                    res.append(s.substring(i + k, s.length()));
                }
                continue;
            }
            // 剩余字符少于 k 个，则将剩余字符全部反转。
            temp.append(s.substring(i, s.length()));
            res.append(temp.reverse());
        }
        return res.toString();
    }
}

Python：

Go：