leetcode 541. 反转字符串 II
- 题目描述
- 解题思路
- 执行结果
题目描述
-
反转字符串 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
区域反转+指针\
-
由示例可知需要反转操作的位置是
[2n,2n+n]n>=0
-
定义反转操作
-
使用双指针法,一个指向首位,一个指向末尾,交换两个位置,指针不断向中间移动,直到相等或大小关系交换(反转完成)结束.
-
尾部数据处理
剩余字符少于 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 炫耀一下:
本文由 mdnice 多平台发布