题目
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] } }
|