抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

一:题目描述:

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

二:示例与提示

示例 1:

1
2
输入:s = "the sky is blue"
输出:"blue is sky the"

示例 2:

1
2
3
输入:s = "  hello world  "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格。

示例 3:

1
2
3
输入:s = "a good   example"
输出:"example good a"
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
  • 提示:
    • 1 <= s.length <= 104
    • s 包含英文大小写字母、数字和空格 ' '
    • s至少存在一个 单词

三:思路

正则

先调用trim()方法去除字符串首位空格,再利用正则将单词中的多个空格替换成一个空格,然后再利用split分割成数组,调用reverse()方法反转数组,最终join(‘ ‘)将数组转换成字符串

双端队列

left指针初始在0号位置,right指针初始在s.length - 1位置,遍历字符串,将每个由空格分隔的字符串加入队列,最后在转回字符串就是翻转过后的了

重点是利用到了双端队列的特性

复杂度:时间复杂度O(n),空间复杂度O(n)

四:代码

1:排序

时间复杂度O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
//1.排序之后匹配是否相同
const arr = s.split('').sort()
const arr1 = t.split('').sort()
var flag = 1
for(let i=0; i<Math.max(arr.length,arr1.length); i++){
if(arr[i] !== arr1[i]){
flag = 0
}
}
if(flag) return true
else return false
};

2:哈希表

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
//2. hashmap
// 将s中的每个字符都进map,初始值都设置为1
// 遍历t,利用hashmap,如果s中有t,值-1
// 如果值不大于0,就不是字母异位词
if(s.length !== t.length) return false

const map = new Map()
for(let n of s){
if(map.has(n)){
map.set(n, map.get(n) + 1)
}else{
map.set(n, 1)
}
}

for(let n of t){
if(map.has(n) && map.get(n) > 0){
map.set(n, map.get(n) - 1)
}else{
return false
}
}

return true
};

评论