时间复杂度,101算法JavaScrpts描述

时间复杂度,101算法JavaScrpts描述

小册子简介

数据结构和算法是计算机专业的必修课，但是对于前端工程师来说，沉浸在业务代码中，很少直接处理算法，即使他们根本不需要用什么算法。那么我们为什么要学习算法，又有什么意义呢？不能使用算法是没有能力的。把一件事做到极致是一种非常必要的职业心态，这与数据结构和算法密不可分。另一方面，说一下面试，这和你学生时代为什么要学数学、物理和化学是一样的。面试官制造火箭和工作螺丝并不奇怪，面试官通过问几个算法问题来了解你的编程和逻辑思维能力也就不足为奇了。

从零开始，我们掌握的基础知识在一定程度上决定了我们的技术能走多远。想做一件事，就必须有扎实的基础，努力练好“内功”。对于工程师来说，所谓的“内功”无非就是大学里学的那些基础课，比如计算机网络、数据结构、算法等。

内容从浅到深大致分为3部分：

这部分的内容从求值算法的复杂性介绍开始，然后从更基础的字符串和数组开始，最后是一些数学相关的话题。让大家先从简单的内容开始，练好基本功时间复杂度,101算法JavaScrpts描述，不要一上来就被算法吓到。

对稍微复杂的数据结构和算法的分析，加上经典题目的实践练习，将帮助你理解算法的本质，提升算法思维，开始练习更深刻的“内功”。

这部分介绍一些更高级的算法，可以理解为深奥的“心法”。虽然学起来难时间复杂度,101算法JavaScrpts描述，但是学了以后会发现很有用，走遍世界也不怕。

我们无法解决半知半解的问题。对于每个问题和每个解决方案，我们都编写了解决问题的思路和详细的问题解决步骤。在解决问题的过程中，读者可以更好地训练自己的思维，知道答案是怎么来的，并且能够从一个案例中得出结论。

本册共精选101道大厂面试高频算法题。大部分题至少有两个JavaScript解法，并附有详细思路和解题流程时间复杂度，帮助大家巩固和强化算法知识。 .

你会得到什么？您需要为合适的人群准备什么样的学习指南？

这本小册子可能包含很多内容。为了更好的帮助大家，在阅读小册子的时候有更好的体验，我将整本书整理在这里。宣传册目录结构。

小册子分为9章：

也希望读者能通过思维导图了解小册子的内容。更清晰的理解会增加阅读的好处。

如果你觉得自己的水平不错，可以跳过阅读，选择能帮助你提高阅读能力的内容。

有效的研究

大家都经历过高考，其实刷算法题和刷高考题是一样的。例如，如果你已经很好地掌握了立体几何，而导数是一门薄弱的学科，那么做 100 个立体几何就不会像 10 个导数那样进步。经常做自己熟悉的题目，进度不大，投入产出比不高。算法也是如此。你需要经常做你不知道的问题，同时你需要为一个问题挖掘更多、更有效的解决方案。如果你在学习的时候发现脑袋疼，恭喜你，你真的进步了。

一起变得更好

如果您在阅读过程中发现任何错误，请留言，我们会尽快回复，希望您的留言对其他同学有所帮助。

小册子的解题方法还是比较详细的时间复杂度，但这只是我们的想法。不是我们，而是每个人。毕竟每个人的底子都不一样。阅读过程中有什么不明白的，欢迎后台留言。

我们一直非常关注读者的阅读体验。如果您觉得小册子的版式不够好，我们期待您的宝贵建议。

终于

数据结构和算法的学习是一个循序渐进的过程。如果你能仔细阅读这本小册子，相信一定会对你有所帮助。同时，自己的思考和坚持也很重要。好了，说了这么多，先不急着学吧。

简介——复杂性

算法复杂度是评估算法执行效率和资源消耗的重要指标。在满足算法本身要求的基础上，编写的程序运行时间越短，运行过程中占用的内存空间越少，说明算法越好。

时间复杂度

时间复杂度描述了算法运行所需的时间。我们将算法所需的操作数表示为输入大小 nn 的函数，用 T(n)T(n) 表示。时间复杂度通常用mathcal{O}(n)O(n)表示，公式为T(n) = mathcal{O}(f(n))T(n)=O(f(n))，其中f(n) f(n)表示每行代码执行次数之和，注意执行次数。

常见时间复杂度名称运行时间T(n)T(n)T(n)时间示例

常数

O(1)@ >mathcal{O}(1)@>O(1)@>

3

–

线性

mathcal{O}(n)O(n)

nn

操作数组

平方

mathcal{O}( n^2)O(n2)

n^2n2

冒泡排序

对数

mathcal{O}(log(n))O(log(n))

log(n)log(n)log(n)

二分查找

执行算法所需的时间不随变量n的大小而变化，即该算法的时间复杂度是一个常数，可以表示为mathcal{O}(1)@>O (1)@ >

直接编码

const a = 1;
console.log(a);

const a = 1;
console.log(a, 1);
console.log(a, 2);
console.log(a, 2);

mathcal{O}(1) @>O(1)@>表示常数级复杂度，不管你是mathcal{O}(几)O(几)，都会算进去作为数学{O}(1)@>O(1)

for (let i = 0; i < n; i++) {
    // do something
}

上面的代码写了一个for循环，从0到nn，不管n是多少，都要循环n次，而且只能循环n次，所以复杂度是mathcal{O}(n)O(n)

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; i++) {
        // do something
    }
}

上面的程序嵌套了两个循环，外层是0到n，内层也是根据每个不同的i从0到n执行，导致复杂度为mathcal{O}(n^2)O(n2).是的，可以看出随着n的增加，复杂度会呈平方级增加。

顺便复习一下高中数学知识，函数y = log_a{x}y=logax称为对数函数，aa是对数函数的底。

对数复杂度是一种比较常见的复杂度，也是一种难以分析的复杂度。观察上面的代码，i从1开始，每个循环乘以2一次，直到i大于n结束循环。

2 ^1 –> 2^2 –> 2^3 … –>2^x21−−>22−−> 23…−−>2x

观察上面列出的 i 值被发现是一个比例序列。要知道它已经循环了多少次，请找到 x 的值。由2^x = n2x=n得到，x = log_2{n}x=log2n，所以这段代码的时间复杂度是log_2{n}log2n。

如果将上面的 i *= 2 改为 i *= 3，那么这段代码的时间复杂度是 log_3{n}log3n。

根据换基公式：

log_c{a} * log_a{b} = log_c{b}logca∗logab=logcb

所以 log_3{n} = log_3{2} * log_2{n}log3n=log32∗log2n，而 log_3{2}log32 是一个常数，导致 mathcal{O}(log_3(n)) = mathcal{O }(log_2(n))O(log3(n))=O(log2(n))。因此，在对数时间复杂度的表示中，我们忽略了对数的“底”。我不在乎你的基数是多少，它统一计算为 mathcal{O}(log(n))O(log(n))。

递归的时间复杂度

面试的时候可能会写一些递归的程序，那么如何考虑递归的时间复杂度呢？

在递归算法中，每个递归函数的时间复杂度是O(s)O(s)，递归调用的次数是nn，那么递归算法的时间复杂度是O(n) = n * O(s)O(n)=n∗O(s)

我们先来看一个经典问题，斐波那契数列：

F(0)=1, F(1)@>=1, F(n)=F(n – 1)@>+F(n – 2) (n ≥ 2, n ∈ N*) F(0)=1, F(1)@>=1, F(n)=F(n−1)@>+F(n−2)@ >(n≥2,n∈N∗)

1)7@>

我们可以很容易的写出上面的递归代码，但是往往忽略了时间复杂度，也就是调用了多少次。你可以代入一个数字，比如n = 5，你就可以理解递归时间复杂度是怎么来的了。

1)8@>

上图列出了n = 5的情况，可以看出虽然代码很简单，但在实际操作中会出现很多重复计算。

在nn级的完全二叉树中，节点总数为2^n -12n−1，因此F(n)F(n)中递归次数的上限为2^n -12n -1。因此，我们可以估计 F(n)F(n ) 的时间复杂度为 {mathcal{O}(2^n)}O(2n)。

时间复杂度是mathcal{O}(2^n)O(2n)，指数级时间复杂度显然不是最优解，电脑被骗过很多次，面试的时候要注意如果你写这样的代码，你的面试官可能会不满意。

空间复杂度

空间复杂度是算法运行过程中临时占用空间大小的度量。一个算法需要的存储空间用f(n)f(n)表示，S可以得到(n)=mathcal{O}(f(n))S(n)=O(f(n)) ，其中 nn 是问题的大小，S(n)S(n) 表示空间复杂度。通常用S(n)(n)S(n)来定义。

公共空间复杂度

算法执行所需的临时空间不随某个变量n的大小而变化，即该算法的空间复杂度是一个常数，可以表示为{mathcal{O}(1)}O(1)@>

const a = 1;
const b = 2;
console.log(a);
console.log(b);

以上代码，分配的空间不会随着处理的数据量而变化，所以空间复杂度是{math cal{O}(1)@>}O(1)@>

先看这样一段代码

const arr = new Array(n);
for (let i = 0; i < n; i++) {
    // do something
}

上面代码的第一行，申请了一个长度为nn的数组空间，在后面的for循环中没有分配新的空间。可以得出，这段代码的时间复杂度是{mathcal{O}(n)}O(n)。

对数阶的空间复杂度是非常少见的，空间复杂度的分析比时间复杂度的分析简单很多，所以这部分不再细说。

时空互换

对于一个算法来说，它的时间复杂度和空间复杂度往往会相互影响。

我们熟悉的Chrome在流畅度上比其他厂商好很多，但是占用内存空间稍大。

当追求更好的时间复杂度时，可能需要消耗更多的存储空间。反之，如果追求更好的空间复杂度，算法的执行时间可能会变长。

总结

常见的复杂度并不多，从低到高只有几个：O(1)@>O(1)@>, {O( log(n))}O(log(n)), {O(n)}O(n)、{O(n^2)}O(n2)等。你会在章节中发现复杂度基本上是逃不掉的，它是以上所有。

字符串

在计算机中，字符串是零个或多个字符的有限序列。字符串也是JavaScript中最基本的数据类型，学习字符串是学习编程的基础。

说起弦乐，相信大家一定不陌生。你觉得它很简单吗？让我们阅读问题。

本章分为三个部分：

第 2 部分第 3 部分

阅读本章后，您将获得以下好处：

翻转整数、有效字母和翻转整数

翻转整数

给一个 32 位有符号整数，需要将整数的每一位数字取反。

例子

示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21

注意：

假设我们的环境只能存储32位有符号整数，它的取值范围是[−231,231−1][−2^{31}, 2^{31} − 1][−231,231−1]。根据这个假设，如果整数取反后溢出，则返回0。

方法一反转字符串方法

思考

如果把数字看成带符号位的字符串，那么我们可以使用JS提供的string方法来实现无符号部分的翻转，而且由于整数的翻转不影响符号，我们最后加上符号，完成算法。

详细解释

首先设置边界极值；主逻辑使用字符串翻转功能；添加符号，然后连接最终结果

代码

/**
 * @param {number} x
 * @return {number}
 */
const reverse = (x) => {
  // 非空判断
  if (typeof x !== 'number') {
    return;
  }
  // 极值
  const MAX = 2147483647;
  const MIN = -2147483648;
  // 识别数字剩余部分并翻转
  const rest =
    x > 0
      ? String(x)
        .split('')
        .reverse()
        .join('')
      : String(x)
        .slice(1)
        .split('')
        .reverse()
        .join('');
  // 转换为正常值，区分正负数
  const result = x > 0 ? parseInt(rest, 10) : 0 - parseInt(rest, 10);
  // 边界情况
  if (result >= MIN && result <= MAX) {
    return result;
  }
  return 0;
};

复杂性分析

方法2类似欧几里得算法求解

想法

我们学习了欧几里得寻找最大公约数来解决问题的方法。符号的处理逻辑与方法一相同，这里我们取模10得到最低位，然后将最低位乘以10迭代到最高位，完成Flip。

详细

设置边界极值；取给定值的绝对值，遍历循环生成每个数字，借鉴欧几里得算法，从num的最后一位开始取值，形成一个新的数字，如果最终结果是异常值，就会直接返回0；如果原始数据为负数，则将最终结果反转返回最终结果

代码

/**
 * @param {number} x
 * @return {number}
 */
const reverse = (x) => {
  // 获取相应数的绝对值
  let int = Math.abs(x);
  // 极值
  const MAX = 2147483647;
  const MIN = -2147483648;
  let num = 0;
  // 遍历循环生成每一位数字
  while (int !== 0) {
    // 借鉴欧几里得算法，从 num 的最后一位开始取值拼成新的数
    num = (int % 10) + (num * 10);
    // 剔除掉被消费的部分
    int = Math.floor(int / 10);
  }
  // 异常值
  if (num >= MAX || num <= MIN) {
    return 0;
  }
  if (x < 0) {
    return num * -1;
  }
  return num;
};

复杂性分析：有效的字母数字

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 名词的变位词。

示例 1

输入: s = "anagram", t = "nagaram"
输出: true

示例 2

输入: s = "rat", t = "car"
输出: false

方法一、使用数组sort()方法

事情

首先对字符串的字母进行排序，然后比较两个字符串是否相等。

详情

首先，将字符串转换为数组。使用数组排序方法进行排序。然后，转换成字符串进行比较，相等则返回true，否则返回false。

代码

const isAnagram = (s, t) => {
  const sArr = s.split('');
  const tArr = t.split('');
  const sortFn = (a, b) => {
    return a.charCodeAt() - b.charCodeAt();
  };
  sArr.sort(sortFn);
  tArr.sort(sortFn);
  return sArr.join('') === tArr.join('');
};

复杂性分析

方法二计数累加法

想法

声明一个对象来记录字符串中每个字母的个数，并将其他字符串的每一项与得到的对象进行匹配。最后根据count判断是否相等。

详情

首先，声明一个变量，遍历其中一个字符串s或t，并累加每个字母出现的次数。然后，遍历另一个字符串来匹配获得的对象中的每个字母。如果匹配，则对象下的字母数减1。如果不匹配，则返回false。如果两个数字都为 0，则两个字符串相等。

代码

const isAnagram = (s, t) => {
  if (s.length !== t.length) {
    return false;
  }
  const hash = {};
  for (const k of s) {
    hash[k] = hash[k] || 0;
    hash[k] += 1;
  }
  for (const k of t) {
    if (!hash[k]) {
      return false;
    }
    hash[k] -= 1;
  }
  return true;
};

复杂性分析