全栈大前端
  • 反转字符串
// 定义被反转的字符串 
const str = 'juejin'  
// 定义反转后的字符串
const res = str.split('').reverse().join('')

console.log(res) // nijeuj
1
2
3
4
5
6
  • 判断一个字符串是否是回文字符串

字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——“对称性” 和 “双指针”。这两个工具一起上，足以解决大部分的回文字符串衍生问题。

# 高频题

# 反转字符串(简单) (opens new window)

  • 对撞指针
  1. 借助双指针left、right 分别指向头尾
  2. 两个指针不断夹逼,进行交换位置完成反转
const reverseString =function (s){
    let left = 0,right =s.length -1;
    while(left <right){
        [s[left],s[right]]= [s[right],s[left]]
        left++
        right--
    }
}

//时间复杂度: O(n)
//空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12

# 字符串全排列

  • 全排列，通过回溯剪枝。修剪掉有当前元素的path，最后保留与原字符串长度相等的所有元素。
     const _permute = string => {
                // 补全代码
                const res=[]
                function backtrace(path){
                    if(string.length== path.length){
                      return res.push(path)
                    }
                    for(let item of string){
                        if(!path.includes(item)){
                        backtrace(path+item)
                        }
                    }
                }
                backtrace('')
                return res
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 最长公共前缀(简单) (opens new window)

  • 暴力循环，逐个比较
const longestCommonPrefix =function(strs){
    if(strs ===null || strs.length ===0) return ""
    let prevs =strs[0]
    for(let i = 1; i<strs.length; i++){
        let j =0;
        for(;j<prevs.length && j<strs[i].length; j++){
            if(prevs.charAt(j) !== strs[i].charAt(j)){
                break
            }
            prevs =prevs.substring(0,j)
            if(prevs ==""){
                return ""
            }
        }
    }
    return prevs
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 解法二：分治策略 归并思想

分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

  1. 分解成多个相似的子问题：求两个字符串的最长公共前缀
  2. 子问题可以简单求解：两个字符串的最长公共前缀求解很简单
  3. 原问题的解为子问题解的合并：多个字符串的最长公共前缀为两两字符串的最长公共前缀的最长公共前缀，我们可以归并比较两最长公共前缀字符串的最长公共前缀，知道最后归并比较成一个，则为字符串数组的最长公共前缀：LCP(S1, S2, ..., Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    return lCPrefixRec(strs)
};

// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
  let length = arr.length
  if(length === 1) {
    return arr[0]
  }
  let mid = Math.floor(length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length)
  return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}

// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
    let j = 0
    for(; j < str1.length && j < str2.length; j++) {
        if(str1.charAt(j) !== str2.charAt(j)) {
            break
        }
    }
    return str1.substring(0, j)
}
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

# 字符串相加(简单) (opens new window)

  • 双指针
  1. 我们定义两个指针i和j分别指向num1和num2的末尾，即最低位，
  2. 同时定义一个变量 add 维护当前是否有进位，然后从末尾到开头逐位相加即可。
  3. 你可能会想两个数字位数不同怎么处理，这里我们统一在指针当前下标处于负数的时候返回 00，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理
var addStrings = function(num1, num2) {
    let i = num1.length - 1,
        j = num2.length - 1,
        carry = 0,
        ans = [];
    while(i >= 0 || j >= 0 || carry !== 0){
        let c1 = i >= 0 ? num1.charAt(i) - '0' : 0,
            c2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        let sum = c1 + c2 + carry;
        ans.push(sum % 10);
        carry = Math.floor(sum / 10);
        i--;
        j--;
    }
    return ans.reverse().join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  • 方法二
  1. 模拟加法，先补0对齐
  2. 从右往左做加法,计算当前位+num1[i]+num2[i]+carry, 使用+号将字符转换成数字
  3. 当前位：模10的结果+res 字符串
  4. carry 代表是否进位
  5. 如果carry 等于1,需要在res 前添加‘1’
const addString =(num1,num2)=>{
    while(num1.length > num2.length){
        num2 ='0'+ num2
    }   
    while(num1.length < num2.length){
        num1 ='0'+num1
    }
    let res = '' , carry = 0;
    for(let i = num1.length -1;i>=0;i--){
        const sum =  +num1[i] + +num2[i] +carry
        res =sum % 10 + res
        carry =sum > 9 ? 1: 0
    }
    return carry ===1 ? '1' + res : res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 字符串相乘(中等) (opens new window)

  1. 计算 num1 依次乘上 num2 的每一位的和
  2. 把得到的所有和按对应的位置累加在一起，就可以得到 num1 * num2 的结果
const multiply =function (num1,num2){
    if(num1 ==='0' || num2 ==='0') return "0"
    //用于保存计算结果
    const res =[]
    //从个位数开始逐位相乘
    for(let i =0; i< num1.length; i++){
        //num1 尾元素
        let tmp1 = +num1[num1.length-1-i]
        for(let j = 0; j<num2.length; j++){
            //num2 尾元素
            let tmp2 = +num2[num2.length -1-j]
            //判断结果集索引位置是否有值
            let pos =res[i+j]?res[i+j]+tmp1*tmp2:tmp1*tmp2
               // 赋值给当前索引位置
            res[i+j] = pos%10
            // 是否进位 这样简化res去除不必要的"0"
            pos >=10 && (res[i+j+1]=res[i+j+1] ? res[i+j+1]+Math.floor(pos/10) : Math.floor(pos/10));
        }
    }
        return res.reverse().join("");
}
//时间复杂度：O(m * n)
//空间复杂度：O(m + n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 验证回文串（简单）

//调用api
function isPalindrome(s) {
    //首先用正则去掉字符串中不是字母和数字的元素，并且都转换成小写
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
    // 先反转字符串
    const reversedStr = s.split('').reverse().join('')
    // 判断反转前后是否相等
    return reversedStr === s
}

//对称性判断
function isPalindrome(s) {
     //首先用正则去掉字符串中不是字母和数字的元素，并且都转换成小写
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
    // 缓存字符串的长度
    const len = s.length
    // 遍历前半部分，判断和后半部分是否对称
    for(let i=0;i<len/2;i++) {
        if(s[i]!==s[len-i-1]) {
            return false
        }
    }
    return true
}
//对撞指针
const isPalindrome = function (s) {
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
    let n = s.length, left = 0, right = n - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}
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
32
33
34
35
36
37
38

# 最长回文串(简单) (opens new window)

  1. 使用字母的 Unicode 编码和数组会比哈希表更优化
  2. 初始化存放字母出现次数的数组，默认都为 0 次
  3. 遍历字符串，统计字母出现的次数，65 是字母 A 的 Unicode 编码，这样可以从索引 0 开始计数
  4. time 的偶数次(time / 2)可以成为构造回文的一部分，再乘 2，可以得到次数
  5. 如果最后计算出的长度小于字符串的长度，则是奇数长度的回文，需要加 1

const longestPalindrome =function(s){
    let arr =new Array(58).fill(0)
    for(let char of s){
        arr[char.charCodeAt()-65] +=1
    }
    let max =0
    for(let time of arr){
       max += parseInt((time /2),10) *2
    }
    return max <s.length?max +1:max
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 最后一个单词的长度(简单) (opens new window)

  • 反向遍历

const lengthOfLastWord =function(s){
    if(s.length ===0){
        return 0
    }
    let count =0;
    for(let i =s.length -1;i>=0;i--){
        if(s.charAt(i)===' '){
            if(count ===0){
                continue
            }
            break
        }
        count++
    }
    return count
}
//时间复杂度：O(n)
//空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 无重复字符的最长子串(中等) (opens new window)

  • 解法一 ：滑动窗口 + 维护数组
  1. 遍历字符串，判断字符是否在滑动窗口数组里
  2. 不在则 push 进数组
  3. 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
  4. 然后将 max 更新为当前最长子串的长度
  5. 遍历完，返回 max 即可

const lengthOfLongestSubstring =function(s){
    let arr =[],max =0
    for(let i = 0;i<s.length; i++){
        let index =arr.indexOf(s[i])
        if(index!==-1){
            arr.splice(0,index+1)
        }
        arr.push(s.charAt(i))
        max =Math.max(arr.length,max)
    }
    return max
}

// 时间复杂度：O(n2)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  • 解法二： 滑动窗口 + 维护下标

const lengthOfLongestSubstring =function(s){
    let index =0,max =0
    for(let i = 0,j=0; j< s.length; j++){
        index =s.substring(i,j).indexOf(s[j])
        if(index !== -1){
            i = i+index+1
        }
        max =Math.max(max,j-i+1)
    }
    return max
}
//时间复杂度：O(n2)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 优化的Map
  1. 使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标
  2. 使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标
  3. 遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中
  4. 最后，返回 max 即可

const lengthOfLongestSubstring =function(s){
    let map =new Map(),max =0
    for(let i = 0,j=0; j<s.length;j++){
        if(map.has(s[j])){
            i =Math.max(map.get(s[j])+1,i)
        }
        max =Math.max(max, j-i +1)
        map.set(s[j],j)
    }
    return max
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 最多删除一个字符得到回文(简单) (opens new window)

  • 思路分析

这道题很多同学第一眼看过去，可能本能地会想到这样一种解法：若字符串本身不回文，则直接遍历整个字符串。遍历到哪个字符就删除哪个字符、同时对删除该字符后的字符串进行是否回文的判断，看看存不存在删掉某个字符后、字符串能够满足回文的这种情况。

这个思路真的实现起来的话，在判题系统眼里其实也是没啥毛病的。但是在面试官看来，就有点问题了——这不是一个高效的解法。 如何判断自己解决回文类问题的解法是否“高效”？其中一个很重要的标准，就是看你对回文字符串的对称特性利用得是否彻底。

字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——对称性 和 双指针。这两个工具一起上，足以解决大部分的回文字符串衍生问题。


//对称性+双指针
const validPalindrome=function(s){
    //缓存字符串的长度
    const len =s.length;
    // i、j 分别为左右指针
    let i =0,j=len-1;
    // 当左右指针均满足对称时，一起向中间前进
    while(i<j&&s[i]===s[j]){
        i++;
        j--;
    }
    // 尝试判断跳过左指针元素后字符串是否回文
    if(isPalindrome(i+1,j)){
        return true
    }

    // 尝试判断跳过右指针后字符串是否回文
    if(isPalindrome(i,j-1)){
        return true
    }

    //工具方法，用于判断字符串是否回文
    function isPalindrome(st,ed){
        while(st<ed){
            if(s[st] !==s[ed]){
                return false
            }
            st++;
            ed--;
        }
        return true
    }
    return false
}
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
32
33
34
35
36

# 有效括号(简单) (opens new window)

var isValid = function(s) {
    while (s.includes("{}")||s.includes("[]") || s.includes("()")){
       s= s.replace("{}","").replace("[]","").replace("()","")
    }
    s= s.replace("{}","").replace("[]","").replace("()","")
    return s.length ===0
};
1
2
3
4
5
6
7

# 括号生成(中等) (opens new window)

/**
 * @param {number} n
 * @return {string[]}
 * @param l 左括号已经用了几个
 * @param r 右括号已经用了几个
 * @param str 当前递归得到的拼接字符串结果
 * @param res 结果集
 */
const generateParenthesis = function (n) {
  const res = [];

  function dfs(l, r, str) {
    if (l == n && r == n) {
      return res.push(str);
    }
    // l 小于 r 时不满足条件 剪枝
    if (l < r) {
      return;
    }
    // l 小于 n 时可以插入左括号，最多可以插入 n 个
    if (l < n) {
      dfs(l + 1, r, str + "(");
    }
    // r < l 时 可以插入右括号
    if (r < l) {
      dfs(l, r + 1, str + ")");
    }
  }
  dfs(0, 0, "");
  return res;
};
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
32

← 堆、图 →