字符串的反转

344. 反转字符串

思路

双指针从两端开始替换

代码

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
  let len = s.length;
  let l = 0, r = len - 1;
  while(l < r) {
    let tmp = s[l]
    s[l] = s[r]
    s[r] = tmp
    l++
    r--
  }
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

541. 反转字符串 II

思路

每k个为1组，奇数组需要反转，偶数不需要

代码

var reverseStr = function(s, k) {
let arr = s.split(‘’), len = arr.length, flag = true;
for(let i = 0; i < len; i += k) {
if (flag) {
reverseString(arr, i, i + k-1)
}
flag = !flag;
}
return arr.join(‘’)
};
function reverseString(s, l, r) {
while(l < r) {
let tmp = s[l]
s[l] = s[r]
s[r] = tmp
l++
r—
}
};

复杂度分析

空间复杂度 $O(N)$
时间复杂度 $O(N)$

557. 反转字符串中的单词 III

思路

将字符串用空格分割，然后每个单元反转后用空格拼接

代码

/**
 * @param {string} s
 * @return {string}
 */
// 也可以用 split 直接分割
var reverseWords = function(s) {
  let res = '', tmp = '', len = s.length;
  for(let i = 0; i < len; i ++) {
    if (s[i] === ' ') {
      res = reverseStr(res, tmp) + ' '
      tmp = ''
    } else {
      tmp += s[i]
    }
  }
  res = reverseStr(res, tmp)
  return res
};
function reverseStr(res, word) {
  let i = word.length - 1;
  for(; i >= 0; i --) {
    res += word[i]
  }
  return res;
}

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

151. 翻转字符串里的单词

思路

利用栈的特性，将每个单词入栈，然后再依次出栈

代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  let arr = [], len = s.length, word = '';
  for(let i = 0; i < len; i ++) {
    if (s[i] != ' ') {
      word += s[i];
      if (s[i+1] == ' ' || i == len - 1) {
        arr.push(word)
        word = ''
      }
    }
  }
  let res = ''
  while(arr.length) {
    if (arr.length === 1) {
      res += arr.pop()
    } else {
      res += arr.pop() + ' '
    }
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)