JavaScript-Algorithms

JavaScript-Algorithms copied to clipboard

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

附赠姚老板的 ：JavaScript正则表达式迷你书（1.1版）.pdf

leetcode

function reverseStr(str) {
    return str.match(/[\w!,]+/g).reverse().join(" ");
}

方法一

const reverseWords = s => {
    let arr = s.split(' ').filter(function (s) {
        return s && s.trim();
    })
    const result = arr.reverse().join(' ')
    return result;
};

方法二

const reverseWords = s => {
    return s.match(/[\w!,]+/g).reverse().join(' ');
}

解法一：正则 + JS API

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};

解法二：双端队列（不使用 API）

双端队列，故名思义就是两端都可以进队的队列

解题思路：

• 首先去除字符串左右空格
• 逐个读取字符串中的每个单词，依次放入双端队列的对头
• 再将队列转换成字符串输出（已空格为分隔符）

画图理解：

代码实现：

var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let queue = []
    let word = ''
    while (s.charAt(left) === ' ') left ++
    while (s.charAt(right) === ' ') right --
    while (left <= right) {
        let char = s.charAt(left)
        if (char === ' ' && word) {
            queue.unshift(word)
            word = ''
        } else if (char !== ' '){
            word += char
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')
};

leetcode

@WeCheung：

function reverseStr(str) {
    return str.match(/[\w!,]+/g).reverse().join(" ");
}

你这种写法有问题，一是匹配的字符有限（[\w!,]），二是需要考虑一下 "" 或 " " 的情况，这种情况下 str.match(/[\w!,]+/g) 会返回 null ，就没办法继续执行下去了

function reverseStr(str) {
    return str.split(' ').filter(item => item).reverse().join(' ')
}

function reverseString(params) { const stringList = params.split(' ').filter((one) => one); return stringList.reverse().join(' ') }

希望增加inplace的做法

function reverseStr(str){
  return str.split(' ').filter(item => item).reverse().join(' ')
}

/**
 * 翻转字符串里的单词
 * @param {*} str
 * @returns
 */
function reverseWords(str) {
  // 方法1：reverse
  // return str.split(' ').reverse().filter(Boolean).join(' ');

  // 方法2：手动翻转
  const strArr = str.split(' ').filter(Boolean);
  const newArr = [];
  let len = strArr.length;
  while (len-- > 0) {
    newArr.push(strArr[len]);
  }
  return newArr.join(' ');
}

console.log(reverseWords('hello   word!')); // word! hello
console.log(reverseWords('the   sky   is blue')); // blue is sky the

官方题解，他不香吗？

var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

解法一：正则 + JS API

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};

解法二：双端队列（不使用 API）

双端队列，故名思义就是两端都可以进队的队列

解题思路：

• 首先去除字符串左右空格
• 逐个读取字符串中的每个单词，依次放入双端队列的对头
• 再将队列转换成字符串输出（已空格为分隔符）

画图理解：

代码实现：

var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let queue = []
    let word = ''
    while (s.charAt(left) === ' ') left ++
    while (s.charAt(right) === ' ') right --
    while (left <= right) {
        let char = s.charAt(left)
        if (char === ' ' && word) {
            queue.unshift(word)
            word = ''
        } else if (char !== ' '){
            word += char
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')
};

leetcode

如果在第一种方法执行前进行一个判断会更加高效 var reverseWords = function(s) { if( s==0) return ""
return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};

 const reverseWords = str => str.split(' ').filter(Boolean).reverse().join(' ')

str.replace(/ +/g,' ').trim().split(' ').reverse().join(' ')

解法一确实可以优化一下

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};

to

var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ')
};

const reverseWords = str => str.split(/\s+/).filter(Boolean).reverse().join(' ')

var reverseWords = str => str.trim().split(' ').reverse().join(' ')

// 需要处理单词间多个空格
const reverseWords = str => str.trim().split(/\s+/).reverse().join(' ')

// 使用正则表达式，将连续空格替换为单个空格
var reverseWords = function(s) {
	return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
	// return s.trim().split(/\s+/g).reverse().join(' ')
};

// 使用双端队列
var reverseWords = function(s) {
	let left = 0, right = s.length - 1
	const deque = []
	let word = ''

	while (s[left] === ' ') left++
	while (s[right] === ' ') right--

	while (left <= right) {
		const c = s[left]
		if (c === ' ' && word) {
			deque.unshift(word)
			word = ''
		} else if (c !== ' ') {
			word += c
		}
		left++
	}

	deque.unshift(word)

	return deque.join(' ')
};

// 不使用双端队列
var reverseWords = function(s) {
	let res = ''
	let word = ''
	s = s.trim()

	for (let i = s.length - 1; i >= 0; i--) {
		if (s[i] !== ' ') {
			word = s[i] + word
		} else if (s[i] === ' ' && word) {
			res += word + ' '
			word = ''
		}
	}

	return res + word
};

var reverseWords = function (s) {
    let trimStr = s.trim();
    let word = '';
    let strQueue = [];
    for (let i = 0; i < trimStr.length; i++) {
        if (trimStr[i] === ' ' && word) {
            strQueue.unshift(word);
            word = '';
        } else {
            word += trimStr[i];
        }
        word = word.trim();
    }
    word && strQueue.unshift(word);
    return strQueue.join(' ');
};

var reverse = function (sts) {
    return sts.trim().split(" ").reverse().join(" ")
}