leetcode 541. 反转字符串 II

leetcode 541. 反转字符串 II

题目描述

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

解题思路

法1

区域反转+指针\

1. 由示例可知需要反转操作的位置是

[2n,2n+n]n>=0

2. 定义反转操作

• 使用双指针法,一个指向首位,一个指向末尾,交换两个位置,指针不断向中间移动,直到相等或大小关系交换(反转完成)结束.

3. 尾部数据处理

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

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

简单来说就是只反转k个其他保持原样

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func reverseStr(s string, k int) string {
    n := len(s)
    arr := []byte(s)
    for i := 0; i < n; i += 2*k {
        l := i
        r := i + k - 1
        if r >= n {
            r = n - 1
        }
        for l < r {
            arr[l], arr[r] = arr[r], arr[l]
            l++
            r--
        }
    }
    return string(arr)
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 3.2 MB , 在所有 Go 提交中击败了 68.23% 的用户 通过测试用例： 60 / 60 炫耀一下: