- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

【万字详解】JavaScript算法 | 力扣经典题~收藏起来，面试用得上

xcc-2022 发表于 2022/07/12 22:13:46 2022/07/12

【摘要】程序=算法+数据结构+程序设计方法+语言工具和环境@[toc] 字符串转换整数atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数，实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整...

程序=算法+数据结构+程序设计方法+语言工具和环境

@[toc]

字符串转换整数

atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数，实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

示例

示例 1:

输入: "42
输出: 42

示例 2:

输入: "-42"
输出: -42

示例 3:

输入: "4193 with words"
输出: 4193

示例 4:

输入: "words and 987"
输出: 0

示例 5:

输入: "-91283472332"
输出: -2147483648

解释: 数字 “-91283472332” 超过 32 位有符号整数范围。因此返回 INT_MIN (−2147483648) 。

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(nlogn)O(n log n)O(nlogn) , nnn 是数组的大小。

方法一正则匹配

思路

第一步，使用正则提取满足条件的字符，/^(-|\+)?\d+/g，(-|\+)?表示第一位是-或+或都不是，\d+ 表示匹配多个数字

const result = str.trim().match(/^(-|\+)?\d+/g);

第二步，判断目标是否超过 Int 整形最大值或最小值

 return result
    ? Math.max(Math.min(Number(result[0]), Math.pow(2,31)-1), -Math.pow(2,31))
    : 0;

代码

/**
 * @param {string} str
 * @return {number}
 */
const myAtoi = function (str) {
  // 提取需要的字符
  const result = str.trim().match(/^(-|\+)?\d+/g);
  return result
    ? Math.max(Math.min(Number(result[0]), Math.pow(2, 31) - 1), -Math.pow(2, 31))
    : 0;
};

复杂度分析

时间复杂度：O(1)O(1)O(1)

上述解法中，代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，因此时间复杂度为 O(1)O(1)O(1)
空间复杂度: O(1)O(1)O(1)

上述解法中，额外所分配的空间都不随着处理数据量变化，所以空间复杂度为 O(1)O(1)O(1)

方法二逐个判断

思路

第一步，去除字符串之中的空格

const news = str.trim();

第二步，通过执行 parseInt 判断是否为数字，不是数字返回 0 ，是数组继续解析

if(parseInt(news)){
  return retrunNum(parseInt(news));
} else {
  return 0;
}

第三步，判断目标是否超过 Int 整形最大值或最小值

if(parseInt(news)){
  return retrunNum(parseInt(news));
} else {
  return 0;
}

代码

/**
 * @param {string} str
 * @return {number}
 */
const myAtoi = function (str) {
  const news = str.trim();
  if (parseInt(news)) {
    return retrunNum(parseInt(news));
  } else {
    return 0;
  }
};
const retrunNum = function (num) {
  if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
    return num;
  } else {
    return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
  }
};

复杂度分析

时间复杂度：O(1)O(1)O(1)

上述解法中，代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，因此时间复杂度为 O(1)O(1)O(1)
空间复杂度: O(1)O(1)O(1) 上述解法中，额外所分配的空间都不随着处理数据量变化，所以空间复杂度为 O(1)O(1)O(1)

报数、反转字符串和字符串中的第一个唯一字符

报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 “one 1” (“一个一”) , 即 11。 11 被读作 “two 1s” (“两个一”）, 即 21。 21 被读作 “one 2”, “one 1” （“一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。示例

输入: 1
输出: "1"

输入: 4
输出: "1211"

方法一递归

想要获取第 n 项的结果，需要先获取到第 n-1 项的结果，然后报出第 n-1 项的结果做为第 n 项的结果。所以可以采用递归调用法。

const countAndSay = function (n) {
  if (n === 1) {
    return '1';
  }
  const preResult = countAndSay(n - 1); // 获取第 n-1 项的结果。
  /**
    * \d 匹配一个数字
    * \1 匹配前面第一个括号内匹配到的内容
    * (\d)\1* 匹配相邻数字相同的内容
    * 使用replace方法将匹配到的内容处理为长度 + 内容的第一个字符
    * 结果为所求报数
    **/
  return preResult.replace(/(\d)\1*/g, item => `${item.length}${item[0]}`);
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

本算法涉及递归，代码的调用次数为 nnn 次。故而时间复杂度为O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)

递归算法，调用次数随 nnn 增加而成线性增加，每次调用申明变量数相同。故而空间复杂度为O(n)O(n)O(n)。

方法二循环法

递归法是由 n 到 1 计算相应的值并层层返回的，循环法正好相反，循环法由 1 计算到 n。然后将最终值返回。

const countAndSay = function (n) {
  let result = '1'; // 第一个数为'1'
  for (let i = 1; i < n; i++) { // 循环获取知道第 n 项。
    // 同方法一
    result = result.replace(/(\d)\1*/g, item => `${item.length}${item[0]}`);
  }
  return result;
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

本算法代码的调用次数为 nnn 次。故而时间复杂度为O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)

申明对象数量为固定值。空间复杂度为常量O(1)O(1)O(1)。

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1)O(1)O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例1

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例2

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

方法一首尾替换法

思路

首尾替换法，逐位遍历，进行交换

详解

设置变量 i = 0；
替换字符串的第i位和倒数第 i 位，替换方式：使用es6的解构赋值进行变量的交换；
变量 i + 1，继续替换替换字符串的第 i 位和倒数第 i 位；
直到 i 大于字符串s的长度的中位数，完成真个字符串的反转

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
const reverseString = function (s) {
  for (let i = 0; i < s.length / 2; i++) {
    [s[i], s[s.length - 1 - i]] = [s[s.length - 1 - i], s[i]];
  }
  return s;
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

空间复杂度：O(1)O(1)O(1)

没有新开辟的内存空间

方法二中间变量首尾替换法

思路

中间变量首尾替换法，逐位遍历，进行交换

详解

设置变量 i = 0；
替换字符串的第i位和倒数第i位，替换方式：设置一个中间变量，替换两个字符串的值；
变量 i + 1，继续替换替换字符串的第i位和倒数第i位；
直到i大于字符串s的长度的中位数，完成真个字符串的反转

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
const reverseString = function (s) {
  for (let i = 0; i < s.length / 2; i++) {
    const a = s[i];
    s[i] = s[s.length - i - 1];
    s[s.length - i - 1] = a;
  }
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

遍历次数：如果字符串长度为nnn，nnn是偶数，遍历次数位 n/2n/2n/2 ，如果nnn是奇数，遍历次数为 (n+1)/2(n+1)/2(n+1)/2

空间复杂度：O(1)O(1)O(1)

1个临时变量

字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

方法一库函数

思路

某个字符从头开始开始的索引和从尾开始找的索引如果相等，就说明这个字符只出现了一次

详解

从头到尾遍历一遍字段串；
判断每个位置的字符的 index() 和 lastIndexOf() 的结果是否相等；

代码

/**
 * @param {string} s
 * @return {number}
 */
const firstUniqChar = function (s) {
  for (let i = 0; i < s.length; i += 1) {
    if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
      return i;
    }
  }
  return -1;
};

复杂度分析

时间复杂度：O(n2)O(n^2)O(n2)

外层遍历，时间复杂度为 O(n)O(n)O(n)，调用 indexOf 的复杂度为 O(n)O(n)O(n)，得出总的时间复杂度为 O(n2)O(n^2)O(n2)

空间复杂度：O(1)O(1)O(1)

因为除了临时变量 i，没有开辟额外的空间

方法二哈希

思路

遍历两次。第一次遍历，用一个哈希对象记录所有字符的出现次数；第二次遍历，找出哈希对象中只出现一次的字符的下标

详解

第一次遍历，用一个哈希对象记录所有字符的出现次数；
第二次遍历，找出哈希对象中只出现一次的字符的下标；

代码

/**
 * @param {string} s
 * @return {number}
 */
const firstUniqChar = function (s) {
  const hash = {};
  for (let i = 0; i < s.length; i += 1) {
    if (!hash[s[i]]) {
      hash[s[i]] = 1;
    } else {
      hash[s[i]] += 1;
    }
  }
  for (let i = 0; i < s.length; i += 1) {
    if (hash[s[i]] === 1) {
      return i;
    }
  }
  return -1;
};

复杂度分析

空间复杂度：O(1)O(1)O(1)

因为变量只有 hash 和 i，开辟空间大小不随输入的变量变化
时间复杂度：O(n)O(n)O(n)

因为有两次遍历，且每次遍历都只有一层没有嵌套，所以遍历的次数只和入参字符串 s 的长度线性正相关

翻转整数、有效的字母异位词和翻转整数

验证回文字符串、实现 strStr() 、最长公共前缀和最长回文子串

验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

方法一

思路

首先，去除字符串中的非字母和数字，再将字符串转换为数组，再对数组首尾一一比较，即可得出结果。

详解

将传入的字符串，利用 toLowerCase() 方法统一转化为小写，再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字，最后将字符串转换为数组。
转换数组后，利用循环一一比较元素，先比较第一个和最后一个，再比较第二个和倒数二个，依次类推，若中间有不相等则不是回文串，反之，则是回文串。

代码

/**
 * @param {string}
 * @return {boolean}
 */
const isPalindrome = (s) => {
  // 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组
  const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '').split('');
  let i = 0;
  let j = arr.length - 1;
  // 循环比较元素
  while (i < j) {
    // 从首尾开始, 一一比较元素是否相等
    if (arr[i] === arr[j]) {
      // 若相等,即第二个元素和倒数第二个元素继续比较,依次类推
      i += 1;
      j -= 1;
    } else {
      // 只要有一个相对位置上不相等,既不是回文串
      return false;
    }
  }
  // 是回文串
  return true;
};

复杂度分析

时间复杂度：O(n)O(n)O(n) 该解法中 while 循环最多执行 n/2n/2n/2 次，即回文时，因此，时间复杂度为 O(n)O(n)O(n)。

空间复杂度：O(n)O(n)O(n) 该解法中，申请了 1 个大小为 nnn 的数组空间，因此，空间复杂度为 O(n)O(n)O(n)。

方法二

思路

首先，去除字符串中的非字母和数字，然后，利用数组将字符串翻转，再和原字符串进行比较，即可得到结果。

详解

将传入的字符串，利用 toLowerCase() 方法统一转化为小写，再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字，得到字符串 arr。
将字符串 arr 转换为数组，利用数组的方法反转数组，再将数组转为字符串 newArr。
将字符串 arr 和字符串 newArr 进行比较，相等即为回文串，不相等则不为回文串。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
const isPalindrome = (s) => {
  // 方便比较,统一转化为小写,并去除非字母和数字
  const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '');
  // 将新字符串转换为数组,利用数组的方法获得反转的字符串
  const newArr = arr.split('').reverse().join('');
  // 将2个字符进行比较得出结果
  return arr === newArr;
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

该解法中，toLowerCase(), replace(), split(), reverse(), join() 的时间复杂度都为 O(n)O(n)O(n)，且都在独立的循环中执行，因此，总的时间复杂度依然为 O(n)O(n)O(n)。

空间复杂度：O(n)O(n)O(n)

该解法中，申请了 1 个大小为 nnn 的字符串和 1 个大小为 nnn 的数组空间，因此，空间复杂度为 O(n∗2)O(n*2)O(n∗2) ，即 O(n)O(n)O(n)。

实现strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

以下称 haystack 字符串为匹配字符串，needle 字符串为查找字符串

示例

给定 haystack = 'hello world', needle = 'll'

返回2

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

方法一遍历截取字符串对比

思路

截取字符串对比的思路很简单，从匹配字符串 haystack 中截取出与需查找字符串 needle 长度相等的内容后，对比截取的内容与匹配字符串是否相等，如果相等返回开始截取的下标。

详解

首先处理几个特殊场景

needle 的长度为0，直接返回0

needle 的字符串长度大于 haystack，肯定不匹配

needle 的字符串长度等于 haystack，判断是否相等，相等则匹配否则不匹配

剩下的就是 needle 字符串长度小于 haystack 的情况，遍历 haystack

此处需要注意的是，当 haystack 剩余字符串长度小于 needle 长度时，肯定是不相等，无需再次比较。

在遍历中判断 将要截取的字符串的首位与 needle 字符串的首位是否相同 ，如果不相同也就不需要后续截取、比较，跳过该次循环

代码

const strStr = function (haystack, needle) {
  const hayLen = haystack.length;
  const nedLen = needle.length;

  if (!needle) {
    return 0;
  } if (nedLen > hayLen) {
    return -1;
  } else if (nedLen === hayLen) {
    return haystack === needle ? 0 : -1;
  } else {
    for (let index = 0; index <= hayLen - nedLen; index++) {
      if (haystack[index] !== needle[0]) {
        continue;
      }
      if (haystack.substring(index, index + nedLen) === needle) {
        return index;
      }
    }
  }
  return -1;
};

复杂度分析：

时间复杂度：O(n)O(n)O(n)

遍历长度可能从 1 到 n−1n -1n−1，假设不同长度出现的概率均等，那么时间复杂度为 (n−1+1)/2(n-1 + 1) / 2(n−1+1)/2时间复杂度即为O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)

使用 2 个额外存储空间。

方法二双层循环对比字符

思路

循环对比字符串思路也很简单，从匹配字符串 haystack 的不同位置开始遍历，判断其中是否含有查找字符串 needle。

如：haystack 为 hello， needle 为 ll，依次判断 he、el、ll、lo是否完全和 ll 相等，相等即返回对应字符串在 haystack 中的下标。

详解

首先处理特殊边际情况，这块与第一种方法相同，就不再赘述。

以下为算法步骤：

设置最外层循环，遍历次数为 0 - haystack长度减去 needle 的长度。剩余字符串长度小于 needle 长度时，肯定不匹配
判断匹配字符串 haystack 中该次循环使用到的字符串首尾字母是否与查找字符串 needle 首尾字母相同。
- 不相等，直接跳过继续遍历。
- 相等，执行第三步。
判断查找字符串 needle 的长度
- 长度为 1，表明匹配成功，直接返回当前长字符串下标即可
- 长度大于 1，执行第四步
遍历对比字符串，循环判断匹配字符串 haystack 不同位置的字符是否与匹配字符串 needle 对应位置的字符相等
- 不相等时，跳出循环，进行下次循环。
- 到最后一位还未跳出循环表明完全匹配，返回当前遍历次数（即查找字符串在匹配字符串中首次出现的位置)

代码

const strStr = function (haystack, needle) {
  const hayLen = haystack.length;
  const nedLen = needle.length;

  if (!needle) {
    return 0;
  } if (nedLen > hayLen) {
    return -1;
  } else if (nedLen === hayLen) {
    return haystack === needle ? 0 : -1;
  } else {
    for (let hasIndex = 0; hasIndex <= hayLen - nedLen; hasIndex++) {
      if (
        haystack[hasIndex] === needle[0] &&
          haystack[hasIndex + nedLen - 1] === needle[nedLen - 1]
      ) {
        if (nedLen === 1) {
          return hasIndex;
        }
        for (let nedIndex = 1; nedIndex < nedLen; nedIndex++) {
          if (haystack[hasIndex + nedIndex] !== needle[nedIndex]) {
            break;
          }
          if (nedIndex === nedLen - 1) {
            return hasIndex;
          }
        }
      }
    }
  }
  return -1;
};

复杂度分析

时间复杂度：O(n2)O(n^2)O(n2)

假设长字符串长度为无限大的 nnn，那么对比字符串长度最大为 n−1n-1n−1，那么就需要对比 (n−1)∗n=n2−n(n-1)*n = n^2-n(n−1)∗n=n2−n 次。当 nnn 趋近无限大时，n2n^2n2 要远远大于 nnn，因此忽略减数 nnn，那么时间复杂度为O(n2)O(n^2)O(n2)

空间复杂度：O(1)O(1)O(1)

使用 2 个额外存储空间

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例

输入: ["flower","flow","flight"]
输出: "fl"

方法一递归迭代

思路

查找 n 个字符串的最长公共前缀，可以拆分成两步： 1. 查找前 n-1 个字符串的最长公共前缀 m 2. 查找 m 与最后一个字符串的公共前缀

因此，我们可以得到递归公式：

$longestCommonPrefix([S1, S2, ..., Sn]) = findCommPrefix(longestCommonPrefix([S1, S2, ..., Sn-1]), Sn)$

我们只需要实现 findCommPrefix 方法，然后遍历数组即可。

详解

获取数组中第一个字符串，当做最长公共前缀保存到变量 commonPrefix
从数组中取出下一个字符串，与当前的最长公共前缀 commonPrefix 对比，得到新的最长公共前缀存到 commonPrefix
重复第 2 步遍历完整个字符串，最后得到的即使数组中所有字符串的最长公共前缀

代码

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function (strs) {
  function findCommonPrefix (a, b) {
    let i = 0;
    while (i < a.length && i < b.length && a.charAt(i) === b.charAt(i)) {
      i++;
    }
    return i > 0 ? a.substring(0, i) : '';
  }
  if (strs.length > 0) {
    let commonPrefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
      commonPrefix = findCommonPrefix(commonPrefix, strs[i]);
    }
    return commonPrefix;
  }
  return '';
};

复杂度分析

时间复杂度：O(n)O(n)O(n)

最坏的情况下，所有个字符串都是相同的。那么会将所有字符串的所有字符串都遍历比较一次这样就会进行 nnn 次字符比较，其中 nnn 是输入数据中所有字符数量。最好的情况下，所有的字符串都不一样，那么每个字符串只会访问一次，复杂度是 nnn, nnn即数组长度。

空间复杂度：O(1)O(1)O(1)，除了保存当前公共前缀外无需其他存储空间。

方法二循环迭代

思路

最长公共前缀一定是数组中所有数组都包含的前缀子串，我们可以将任意字符串的前缀作为公共前缀，从长度 0 到 nnn (nnn为该字符串长度），横向扫描数组中的所有字符串，看是否都有该前缀，直到找到不满足的为止。

详解

先假设最长公共子串的长度为 1，存到变量 iii。以第一个字符串为基准，取它的第 $i$ 个字符与数组中其他所有的字符串第 iii 个字符进行比较，如果都相等，那么将最长公共子串的长度加 1，否则停止查找，已找到最长公共前缀的长度，设置完成匹配标记 flag为 false
重复第 1 步，直到 iii 等于第一个字符串的长度，或者匹配标记 flag 为 false
返回第一个字符串的前 iii 个字符，即为当前数组的最长公共前缀

代码

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function (strs) {
  if (strs.length === 0) {
    return '';
  }
  let i = 0;
  let flag = true;
  while (flag) {
    if (strs[0].length > i) {
      const char = strs[0].charAt(i);
      for (let j = 1; j < strs.length; j++) {
        if (strs[j].length <= i || strs[j].charAt(i) !== char) {
          flag = false;
          break;
        }
      }
    } else {
      flag = false;
    }
    i++;
  }
  return strs[0].substring(0, i - 1);
};

复杂度分析：

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1)

整个过程只需要存储匹配标志。

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

方法一动态规划法

思路

动态规划的思想，是希望把问题划分成相关联的子问题；然后从最基本的子问题出发来推导较大的子问题，直到所有的子问题都解决。

根据字符串的长度，建立一个矩阵 dp, 通过不同情况的判断条件，通过 dp[i][j] 表示 s[i] 至 s[j] 所代表的子串是否是回文子串。

详解

建立矩阵 dp
循环遍历字符串，取得不同长度的子串
不同长度的子串，根据不同的条件进行判断是否为回文子串

（1）长度为 1，一定回文

（2）长度为 2 或 3，判断首尾是否相同：s[i] === s[j]

（3）长度 > 3, 首尾字符相同，且去掉首尾之后的子串仍为回文：(s[i] === s[j]) && dp[i + 1][j -1]
取得长度最长的回文子串

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function (s) {
  const dp = [];
  for (let i = 0; i < s.length; i += 1) {
    dp[i] = [];
  }
  let max = -1; let str = '';
  for (let l = 0; l < s.length; l += 1) {
    // l为所遍历的子串长度 - 1，即左下标到右下标的长度
    for (let i = 0; i + l < s.length; i += 1) {
      const j = i + l;
      // i为子串开始的左下标，j为子串开始的右下标
      if (l === 0) {
        // 当子串长度为1时，必定是回文子串
        dp[i][j] = true;
      } else if (l <= 2) {
        // 长度为2或3时，首尾字符相同则是回文子串
        if (s[i] === s[j]) {
          dp[i][j] = true;
        } else {
          dp[i][j] = false;
        }
      } else {
        // 长度大于3时，若首尾字符相同且去掉首尾之后的子串仍为回文，则为回文子串
        if ((s[i] === s[j]) && dp[i + 1][j - 1]) {
          dp[i][j] = true;
        } else {
          dp[i][j] = false;
        }
      }
      if (dp[i][j] && l > max) {
        max = l;
        str = s.substring(i, j + 1);
      }
    }
  }
  return str;
};

复杂度分析

时间复杂度：O(n2)O(n^2)O(n2) 遍历次数取决于字符串的长度，因为是两层循环嵌套，所以遍历的最大次数为 n2n^2n2。
空间复杂度：O(n)O(n)O(n)需要申请空间为字符串长度 nnn 的数组来记录不同长度子串的情况。

方法二中心扩展

思路

回文子串一定是对称的，所以我们可以每次选择一个中心，然后从中心向两边扩展判断左右字符是否相等。

中心点的选取有两种情况：

当长度为奇数时，以单个字符为中心；

当长度为偶数时，以两个字符之间的空隙为中心。

详解

1.循环遍历字符串取得不同长度的子串

2.通过定义好的中心扩展方法，选取奇数对称和偶数对称的中心

3.通过比较选择出两种组合较大的回文子串长度，然后对比之前的长度，判断是否更新起止位置

4.全部遍历完成后，根据最后的起止位置的值，截取最长回文子串

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function (s) {
  if (s == null || s.length < 1) {
    return '';
  }
  let start = 0; let end = 0;
  // 从中心向两边扩展
  const expandFromCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left -= 1;
      right += 1;
    }
    return right - left - 1;
  };
  for (let i = 0; i < s.length; i += 1) {
    // 中心的两种选取（奇对称和偶对称）
    const len1 = expandFromCenter(s, i, i);
    const len2 = expandFromCenter(s, i, i + 1);
    // 两种组合取最大的回文子串长度
    const len = Math.max(len1, len2);
    // 如果此位置为中心的回文数长度大于之前的长度，则进行处理
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
};

复杂度分析

时间复杂度：O(n2)O(n^2)O(n2)

遍历次数取决于字符串的长度，因为是两层循环嵌套，所以遍历的最大次数为 n2n^2n2。
空间复杂度：O(1)O(1)O(1)

只使用到常数个临时变量，与字符串长度无关。

数学

在做算法时，可能需要运用一些数学知识。数学也是计算机的基础，这部分章节的内容相对于后面的章节比较轻松。在实际的面试中，用到的数学知识大纲为初中，极少可能超纲到高中，所以大家不用过于担心。

本章节分为 3 个部分：

Part 1
- 罗马数字转整数
- Fizz Buzz
- 计数质数
Part 2
- 3的幂
- Excel表序列号
- 快乐数
- 阶乘后的零
Part 3
- Pow(x, n)
- 两数相除
- 分数到小数
- x的平方根

罗马数字转整数、Fizz Buzz和计数质数

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

【万字详解】JavaScript算法 | 力扣经典题~收藏起来，面试用得上

字符串转换整数

方法一正则匹配

方法二逐个判断

报数

方法一递归

方法二循环法

反转字符串

方法一首尾替换法

方法二中间变量首尾替换法

字符串中的第一个唯一字符

方法一库函数

方法二哈希

验证回文串

方法一

方法二

实现strStr()

示例

说明:

方法一遍历截取字符串对比

方法二双层循环对比字符

最长公共前缀

方法一递归迭代

方法二循环迭代

最长回文子串

方法一动态规划法

方法二中心扩展

数学

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

【万字详解】JavaScript算法 | 力扣经典题~收藏起来，面试用得上

字符串转换整数

方法一 正则匹配

方法二 逐个判断

报数

方法一 递归

方法二 循环法

反转字符串

方法一 首尾替换法

方法二 中间变量首尾替换法

字符串中的第一个唯一字符

方法一 库函数

方法二 哈希

验证回文串

方法一

方法二

实现strStr()

示例

说明:

方法一 遍历截取字符串对比

方法二 双层循环对比字符

最长公共前缀

方法一 递归迭代

方法二 循环迭代

最长回文子串

方法一 动态规划法

方法二 中心扩展

数学

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品

方法一正则匹配

方法二逐个判断

方法一递归

方法二循环法

方法一首尾替换法

方法二中间变量首尾替换法

方法一库函数

方法二哈希

方法一遍历截取字符串对比

方法二双层循环对比字符

方法一递归迭代

方法二循环迭代

方法一动态规划法

方法二中心扩展