前端需要掌握的算法（一）

简介

算法是我们程序员或多或少要掌握得一项基本技能，对于我们前端开发来着也需要掌握一定的算法来拓展我们的思维和代码逻辑性。对此我会在以后篇章中介绍一下算法对于我们前端开发有哪些好处和作用，还有就是需要掌握哪些算法才能在前端中立于永不抛弃的地位。

首先本篇主要介绍算法对于我们前端开发者有什么好处和作用。

介绍

按通俗来讲：算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

他有什么特征呢？一个算法应该具有以下五个重要的特征：

• 有穷性(Finiteness)：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
• 确切性(Definiteness)：算法的每一步骤必须有确切的定义；
• 输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
• 输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

数据结构和算法是分不开，也是我们程序员必须要掌握的，不管前端技术更新的多快，框架怎么更新，版本如何迭代，它终究不会变的。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模

的函数
，算法的时间复杂度也因此记做：

因此，问题的规模
越大，算法执行的时间的增长率与

的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

类型

下面介绍几种数据结构和相应常见算法思想，首先介绍一下数据结构：

• 字符串（常用）
• 数组（常用）
• 链表
• 哈希表
• 二叉树
• 栈和队列

还有一些常见的算法：

• 递推法（常用）
• 递归法（常用）
• 穷举法
• 贪心算法
• 回溯算法
• 双指针法
• 动态规划法
• 分治法
• 迭代法
• 分支界限法

对于前端来说我们所熟知数据结构就是字符串、数组、也可以利用对象实现哈希表。对于算法来说在写业务时经常用到递推、递归、穷举等

这期我们先介绍一下字符串以及长碰见的问题

字符串

字符串的概念我这边就不多说了，大家都是常用的。

先来个简单的题吧

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 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”]

思路

一般大家见到这个题的时候直接reverse，但这么做就没有这个题的理解了，

我们可以使用双指针的方法。对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

const reverse = (s) => {
  let l = -1, r = s.length
  while (++l < --r) {
    [s[l], s[r]] = [s[r], s[l]];
  }
}

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20″。

示例 1： 输入：s = “We are happy.”
输出：”We%20are%20happy.”

思路

一眼看见这个题把空格去除，再进行替换重组就可以了，但这明显是简单了。我们可以换个思路，首先扩充数组到每个空格替换成”%20″之后的大小。然后从后向前替换空格，也就是双指针法，这样我们就把O(n^2)变成了O(n)

const replaceSpace = (s) => {
  const s = Array.from(s)
  const count = s.reduce((prev, cur) => {
    return prev += cur === ' ' ? 1 : 0
  }, 0)
  
  let l = s.length - 1
  let r = s.length + count * 2 - 1
  
  while (l >= 0) {
    if (s[l] === ' ') {
      s[r--] = '0'
      s[r--] = '2'
      s[r--] = '%'
      l--
    } else {
      s[r--] = s[l--]
    }
  }
  
  return s.join('')
]

重复的字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:
输入: “aba”
输出: False

示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路

我们可以用一个for循环获取子串的终止位置，然后判断子串是否能重复构成字符串，又嵌套一个for循环，就可以得出我们想要的结果，但是时间复杂度O(n^2)很难是我们想要的。

我们可以使用KMP（KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数)本身包含了模式串的局部匹配信息）。

const substringPattern = (s) => {
    if (s.length === 0) return false;
    let nextStep = getnextStep(s);

    if (
        nextStep[nextStep.length - 1] !== -1 && 
        s.length % (s.length - (nextStep[nextStep.length - 1] + 1)) === 0
    ) { return true; }
    return false;
};

const getNextStep = (s) => {
    let nextStep = [];
    let j = -1;

    nextStep.push(j);

    for (let i = 1; i < s.length; ++i) {
        while (j >= 0 && s[i] !== s[j + 1]) j = nextStep[j];
        if (s[i] === s[j + 1]) j++;
        nextStep.push(j);
    }

    return nextStep;
}

本次分享先到这，后面会给大家介绍数组、链表、哈希等数据结构的算法