白筱汐

想都是问题,做都是答案

0%

反转字符串(数组)

题目

leetcode 344 反转字符串 简单

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

解析

在不使用数组自带的方法下,我们可以创建一个新的数组,简单的完成字符串的反转

1
2
3
4
5
6
7
function reverseString(s) {
const arr = []
for (let i = s.length - 1; i > 0; i--) {
arr.push(s[i])
}
s = arr
}

但是题目要求不能使用额外的空间,我们可以通过双指针的方式实现数组的反转,遍历n/2次,时间复杂度为O(n)。

使用两个指针 i 和 j,初始时 i 指向字符串或数组的开头,j 指向末尾。通过一个 while 循环,在 i 小于 j 的条件下,不断交换 s[i] 和 s[j] 的值,并同时移动指针 i 和 j,直到 i 和 j 相遇。

js代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function reverseString(s){
let i = 0
let j = s.length - 1
while(i < j){
let temp = s[i]
s[i] = s[j]
s[j] = temp
i++
j--
}
}
// 或者这样
function reverseString2(){
const l = s.length
for (let i = 0; i < Math.floor(l/2); i++) {
let temp = s[i]
s[i] = s[l - i - 1]
s[l - i - 1] = temp
}
}

go代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverseString(s []byte) {
i, j := 0, len(s)-1
for i < j {
s[i], s[j] = s[j], s[i]
i++
j--
}
}

func resverString2(s []string) {
l := len(s)
for i := 0; i < l/2; i++ {
s[i], s[l-i-1] = s[l-i-1], s[i]
}
}