j

jaryue

V1

2023/04/24阅读:25主题:默认主题

leetcode 541. 反转字符串 II

leetcode 541. 反转字符串 II


题目描述

  1. 反转字符串 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

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

剩余字符少于 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 炫耀一下:

分类:

后端

标签:

后端

作者介绍

j
jaryue
V1