【LeetCode】541. 反转字符串 II(简单)——代码随想录算法训练营Day08

发布时间:2024年01月17日

题目链接:541. 反转字符串 II

题目描述

给定一个字符串?s?和一个整数?k,从字符串开头算起,每计数至?2k?个字符,就反转这?2k?字符中的前?k?个字符。

  • 如果剩余字符少于?k?个,则将剩余字符全部反转。
  • 如果剩余字符小于?2k?但大于或等于?k?个,则反转前?k?个字符,其余字符保持原样。

示例 1:

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

输出:"bacdfeg"

示例 2:

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

输出:"bacd"

提示:

  • 1 <= s.length <= 104
  • s?仅由小写英文组成
  • 1 <= k <= 104

文章讲解:代码随想录

视频讲解:字符串操作进阶! | LeetCode:541. 反转字符串II_哔哩哔哩_bilibili

题解1:暴力法

思路:重新构建一个结果字符串,将原字符串分为多个长度为 2k 的部分。倒序输出每个部分前 k 个元素,正序输出后 k 个元素,最后再处理最后一个不足 2k 的部分。

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    let res = "";
    const part = 2 * k;
    let n = Math.floor(s.length / part);
    let i = 0;
    // 处理前面够 2k 元素的部分
    while (n--) {
        // 倒序输出前 k 个元素
        for (let j = i + k - 1; j >= i; j--) {
            res += s[j];
        }
        // 正序输出后 k 个元素
        for (let j = i + k; j < i + part; j++) {
            res += s[j];
        }
        i += part;
    }
    // 处理最后不足 2k 的部分
    if (s.length - i < k) {
        for (let j = s.length - 1; j >= i; j--) {
            res += s[j];
        }
    } else {
        for (let j = i + k - 1; j >= i; j--) {
            res += s[j];
        }
        for (let j = i + k; j < s.length; j++) {
            res += s[j];
        }
    }
    return res;
};

分析:虽然看起来循环套了多层,但实际上只对原字符串进行了一次遍历。时间复杂度为 O(n),空间复杂度为 O(n)。

题解2:模拟

思路:模拟题目中的规则,直接在原字符串上反转需要反转的部分。

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const sArr = s.split("");
    for (let i = 0; i < sArr.length; i += 2 * k) {
        let left = i;
        let right = i + k <= sArr.length ? i + k - 1 : sArr.length - 1;
        while (left < right) {
            let _ = sArr[left];
            sArr[left++] = sArr[right];
            sArr[right--] = _;
        }
    }
    return sArr.join("");
};

分析:时间复杂度为 O(n),空间复杂度为 O(n)。

收获

这道题目的处理逻辑比上道题稍微复杂了一点,多了些条件。处理好边界判定是非常重要的,进一步提升了我的编码能力。

文章来源:https://blog.csdn.net/m0_57521762/article/details/135648509
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。