前端算法入门：刷算法题常用的JS基础扫盲

介绍

此篇属于前端算法入门系列的第一篇，主要介绍常用的数组方法、字符串方法、遍历方法、高阶函数、正则表达式以及相关数学知识。

文章主要包含以下内容：

  • 数组常用方法
  • 字符串常用方法
  • 常用遍历方法&高阶函数
  • 常用正则表达式
  • 数学知识

一、数组常用方法

1.push()

在尾部追加，类似于压栈，原数组会变。

  1. const arr = [1, 2, 3]
  2. arr.push(8)
  3. console.log(arr) // [1, 2, 3, 8]

2.pop()

在尾部弹出，类似于出栈，原数组会变。数组的 push & pop 可以模拟常见数据结构之一：栈。

  1. const arr = [1, 2, 3]
  2. const popVal = arr.pop()
  3. console.log(popVal) // 3
  4. console.log(arr) // [1, 2]
  6. // 数组模拟常见数据结构之一：栈
  7. const stack = [0, 1]
  8. stack.push(2) // 压栈
  9. console.log(stack) // [0, 1, 2]
  11. const popValue = stack.pop() // 出栈
  12. console.log(popValue) // 2
  13. console.log(stack) // [0, 1]

3.unshift()

在头部压入数据，类似于入队，原数组会变。

  1. const arr = [1, 2, 3]
  2. arr.unshift(0)
  3. console.log(arr) // [0, 1, 2, 3]

4.shift()

在头部弹出数据，原数组会变。数组的 push（入队） & shift（出队） 可以模拟常见数据结构之一：队列。

  1. const arr = [1, 2, 3]
  2. const shiftVal = arr.shift()
  3. console.log(shiftVal) // 1
  4. console.log(arr) // [2, 3]
  6. // 数组模拟常见数据结构之一：队列
  7. const queue = [0, 1]
  8. queue.push(2) // 入队
  9. console.log(queue) // [0, 1, 2]
  11. const shiftValue = queue.shift() // 出队
  12. console.log(shiftValue) // 0
  13. console.log(queue) // [1, 2]

5.concat()

concat会在当前数组尾部拼接传入的数组，然后返回一个新数组，原数组不变。

  1. const arr = [1, 2, 3]
  2. const arr2 = arr.concat([7, 8, 9])
  3. console.log(arr) // [1, 2, 3]
  4. console.log(arr2) // [1, 2, 3, 7, 8, 9]

6.indexOf()

在数组中寻找该值，找到则返回其下标，找不到则返回-1。

  1. const arr = [1, 2, 3]
  2. console.log(arr.indexOf(2)) // 1
  3. console.log(arr.indexOf(0)) // -1

7.includes()

在数组中寻找该值，找到则返回true，找不到则返回false。

  1. const arr = [1, 2, 3]
  2. console.log(arr.includes(2)) // true
  3. console.log(arr.includes(4)) // false

8.join()

将数组转化成字符串，并返回该字符串，不传值则默认逗号隔开，原数组不变。

  1. const arr = [1, 2, 3]
  2. console.log(arr.join()) // ‘1, 2, 3’
  3. console.log(arr) // [1, 2, 3]

9.reverse()

翻转原数组，并返回已完成翻转的数组，原数组改变。

  1. const arr = [1, 2, 3]
  2. console.log(arr.reverse()) // [3, 2, 1]
  3. console.log(arr) // [3, 2, 1]

10.slice(start，end)

从start 开始截取到end，但是不包括end

  1. const arr = [1, 2, 3, 4, 5]
  2. console.log(arr.slice(1, 4)) // [2, 3, 4]
  3. console.log(arr) // [1, 2, 3, 4, 5]

11.splice(start, deleteCount, item1, item2……)

  • start参数 开始的位置
  • deleteCount要截取的个数
  • 后面的items为要添加的元素
  • 如果deleteCount为0，则表示不删除元素，从start位置开始添加后面的几个元素到原始的数组里面。
  • 返回值为由被删除的元素组成的一个数组。如果只删除了一个元素，则返回只包含一个元素的数组。如果没有删除元素，则返回空数组。
  • 这个方法会改变原始数组，数组的长度会发生变化
  1. const arr3 = [1, 2, 3, 4, 5, 6, 7, "f1", "f2"];
  2. const arr4 = arr3.splice(2, 3) // 删除第三个元素以后的三个数组元素(包含第三个元素)
  3. console.log(arr4); // [3, 4, 5];
  4. console.log(arr3); // [1, 2, 6, 7, "f1", "f2"]; 原始数组被改变
  6. const arr5 = arr3.splice(2, 0, "wu", "leon"); 
  7. // 从第2位开始删除0个元素，插入"wu","leon"
  8. console.log(arr5); // [] 返回空数组
  9. console.log(arr3); // [1, 2, "wu", "leon", 6, 7, "f1", "f2"]; 原始数组被改变
  11. const arr6 = arr3.splice(2, 3, "xiao", "long");
  12. // 从第 2 位开始删除 3 个元素，插入"xiao", "long"
  13. console.log(arr6); // ["wu", "leon", 6]
  14. console.log(arr3); //[ 1, 2, "xiao", "long", 7, "f1", "f2"]
  16. const arr7 = arr3.splice(2); // 从第三个元素开始删除所有的元素
  17. console.log(arr7);// ["xiao", "long", 7, "f1", "f2"]
  18. console.log(arr3); // [1, 2]

12.sort()

  • 对数组的元素进行排序，并返回数组。
  • 默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。
  • 由于它取决于具体实现，因此无法保证排序的时间和空间复杂性。

可参考 MDN：Sort

  1. const arr = [1, 2, 3]
  2. arr.sort((a, b) => b - a)
  3. console.log(arr) // [3, 2, 1]

13.toString()

将数组转化成字符串，并返回该字符串，逗号隔开，原数组不变。

  1. const arr = [1, 2, 3, 4, 5]
  2. console.log(arr.toString()) // ‘1, 2, 3, 4, 5’
  3. console.log(arr) // [1, 2, 3, 4, 5]

二、字符串常用方法

1.charAt()

返回指定索引位置处的字符。类似于数组用中括号获取相应下标位置的数据。

  1. var str = 'abcdefg'
  2. console.log(str.charAt(2)) // 输出 'c' 
  3. console.log(str[2]) // 输出 'c'

2.concat()

类似数组的concat()，用来返回一个合并拼接两个或两个以上字符串。原字符串不变。

  1. const str1 = 'abcdefg'
  2. const str2 = '1234567'
  3. const str3 = str1.concat(str2)
  4. console.log(str3) // 输出 'abcdefg1234567'

3.indexOf()、lastIndexOf()

indexOf,返回一个字符在字符串中首次出现的位置,lastIndexOf返回一个字符在字符串中最后一次出现的位置。

  1. const str = 'abcdcefcg'
  2. console.log(str.indexOf('c')) // 输出 '2'
  3. console.log(str.lastIndexOf('c')) // 输出 '7'

4.slice()

提取字符串的片断，并把提取的字符串作为新的字符串返回出来。原字符串不变。

  1. const str = 'abcdefg'
  2. console.log(str.slice()) // 输出 'abcdefg', 不传递参数默认复制整个字符串
  3. console.log(str.slice(1)) // 输出 'bcdefg',传递一个，则为提取的起点，然后到字符串结尾
  4. console.log(str.slice(2, str.length-1)) // 输出'cdef',传递两个，为提取的起始点和结束点

5.split()

使用指定的分隔符将一个字符串拆分为多个子字符串数组并返回，原字符串不变。

  1. const str = 'A*B*C*D*E*F*G'
  2. console.log(str.split('*')) // 输出 ["A", "B", "C", "D", "E", "F", "G"]

6.substr(), substring()

  • 这两个方法的功能都是截取一个字符串的片段，并返回截取的字符串。
  • substr和substring这两个方法不同的地方就在于参数二，substr的参数二是截取返回出来的这个字符串指定的长度，substring的参数二是截取返回这个字符串的结束点，并且不包含这个结束点。而它们的参数一，都是一样的功能，截取的起始位置。
  • 注意事项：substr的参数二如果为0或者负数，则返回一个空字符串，如果未填入，则会截取到字符串的结尾去。substring的参数一和参数二为NAN或者负数，那么它将被替换为0。
  1. const str = 'ABCDEFGHIJKLMN'
  2. console.log(str.substr(2))  // 输出 'CDEFGHIJKLMN'
  3. console.log(str.substring(2)) // 输出 'CDEFGHIJKLMN'
  5. console.log(str.substr(2, 9))  // 输出 'CDEFGHIJK'
  6. console.log(str.substring(2, 9))  // 输出 'CDEFGHI'

7.match()

match()方法可在字符串内检索指定的值，或找到一个或多个正则表达式的匹配，并返回一个包含该搜索结果的数组。

  1. const str = '2018年结束了，2019年开始了，2020年就也不远了'
  2. const reg = /\d+/g  // 这里是定义匹配规则，匹配字符串里的1到多个数字
  3. console.log(str.match(reg))  // 输出符合匹配规则的内容，以数组形式返回 ['2018', '2019', '2020']
  4. console.log(str.match('20'))  // 不使用正则 ["20", index: 0, input: "2018年结束了，2019年开始了"]
  5. 复制代码

注意事项:如果match方法没有找到匹配，将返回null。如果找到匹配，则 match方法会把匹配到以数组形式返回，如果正则规则未设置全局修饰符g，则 match方法返回的数组有两个特性：input和index。input属性包含整个被搜索的字符串。index属性包含了在整个被搜索字符串中匹配的子字符串的位置。

8.replace()

replace接收两个参数，参数一是需要替换掉的字符或者一个正则的匹配规则，参数二，需要替换进去的字符，参数二，你可以换成一个回调函数。

  1. const str = '2018年结束了，2019年开始了，2020年就也不远了'
  2. const rex = /\d+/g  // 这里是定义匹配规则，匹配字符串里的1到多个数字
  3. const str1 = str.replace(rex, '****') 
  4. console.log(str1) // 输出："****年结束了，****年开始了,****年也不远了"
  5. const str2 = str.replace(rex, function(item){
  6.     console.log(arguments)  // 看下面的图片
  7.     const arr = ['零', '壹', '贰', '叁', '肆', '伍', '陆', '柒', '捌', '玖']
  8.     let newStr = ''
  9.     item.split('').map(function(i){
  10.             newStr += arr[i]
  11.     })                    
  12.     return newStr       
  13. })
  14. console.log(str2) // 输出：贰零壹捌年结束了，贰零壹玖年开始了,贰零贰零年也不远了

9.search()

在目标字符串中搜索与正则规则相匹配的字符，搜索到，则返回第一个匹配项在目标字符串当中的位置，没有搜索到则返回一个-1。

  1. const str = '2018年结束了，2019年开始了，2020年就也不远了'
  2. const reg = /\d+/i  // 这里是定义匹配规则,匹配字符串里的1到多个数字
  3. console.log(str.search(reg)) // 输出 0  这里搜索到的第一项是从位置0开始的

10.toLowerCase(),toUpperCase()

toLowerCase把字母转换成小写，toUpperCase()则是把字母转换成大写。

  1. const str1 = 'abcdefg'
  2. const str2 = 'ABCDEFG'
  3. console.log(str2.toLowerCase())  // 输出：'abcdefg'
  4. console.log(str1.toUpperCase())  // 输出：'ABCDEFG'

11.includes(), startsWith(), endsWith()

includes、startsWith、endsWith，es6的新增方法，includes 用来检测目标字符串对象是否包含某个字符，返回一个布尔值，startsWith用来检测当前字符是否是目标字符串的起始部分，相对的endwith是用来检测是否是目标字符串的结尾部分。

  1. const str = 'Excuse me, how do I get to park road?'
  2. console.log(str.includes('how')) // 输出：true
  3. console.log(str.startsWith('Excuse')) // 输出： true
  4. console.log(str.endsWith('?')) // 输出： true

12.repeat()

返回一个新的字符串对象，新字符串等于重复了指定次数的原始字符串。接收一个参数，就是指定重复的次数。原字符串不变。

  1. const str = 'http'
  2. const str2 = str.repeat(3)
  3. console.log(str) // 输出：'http'
  4. console.log(str2) // 输出：'httphttphttp'

三、常用遍历方法&高阶函数

1.for()

最常用的for循环，经常用的数组遍历，也可以遍历字符串。

  1. const arr = [1, 2, 3]
  2. const str = 'abc'
  3. for (let i = 0; i < arr.length; i++) {
  4.     console.log(arr[i])
  5.     console.log(str[i])
  6. }

2.while() / do while()

while、do while主要的功能是，当满足while后边所跟的条件时，来执行相关业务。这两个的区别是，while会先判断是否满足条件，然后再去执行花括号里面的任务，而do while则是先执行一次花括号中的任务，再去执行while条件，判断下次还是否再去执行do里面的操作。也就是说 do while至少会执行一次操作.

  1. while(条件){
  2.      执行...
  3. }
  4. ------------
  5. do{
  6.     执行...
  7. }
  8. while(条件)

3.forEach()

拷贝一份遍历原数组。

  • return无法终止循环。不过可以起到continue效果。
  • 本身是不支持的continue与break语句的我们可以通过some和 every来实现。
  1. const arr = [5,1,3,7,4]
  2. arr.forEach((item, index) => {
  3.     if (item < 2) return
  4.     console.log(`索引：${index}，数值：${item}`)
  5.     arr[5] = 0
  6. })
  7. console.log(arr)
  8. // 打印结果：
  9. // 索引：0，数值：5
  10. // 索引：2，数值：3
  11. // 索引：3，数值：7
  12. // 索引：4，数值：4
  13. // [5, 1, 3, 7, 4, 0]

4.for…in

  • for...in 是 ES5 标准， 此方法遍历数组效率低，主要是用来循环遍历对象的属性。
  • 遍历数组的缺点：数组的下标index值是数字，for-in遍历的index值"0","1","2"等是字符串。
  • Object.defineProperty，建立的属性，默认不可枚举。
  1. const foo = {
  2.     name: 'bar',
  3.     sex: 'male'
  4. }
  5. Object.defineProperty(foo, "age", { value : 18 })
  6. for(const key in foo){
  7.     console.log(`可枚举属性：${key}`)
  8. }
  9. console.log(`age属性：${foo.age}`)
  10. // 打印结果：
  11. // 可枚举属性：name
  12. // 可枚举属性：sex
  13. // age属性：18

5.for…of

for…of是ES6新增的方法，但是for…of不能去遍历普通的对象，for…of的好处是可以使用break跳出循环。

  • for-of这个方法避开了for-in循环的所有缺陷
  • 与forEach()不同的是，它可以正确响应break、continue和return语句
  • for-of循环不仅支持数组，还支持大多数类数组对象，例如DOM NodeList对象。
  • for-of循环也支持字符串遍历
  1. // for of 循环直接得到的就是值
  2. const arr = [1, 2, 3]
  3. for (const value of arr) {
  4.  console.log(value)
  5. }

面试官：说一下 for...in 和 for...of 区别？

  1. （1）for…in 用于可枚举数据，如对象、数组、字符串
  2. （2）for…of 用于可迭代数据，如数组、字符串、Map、Set

6.every / some

返回一个布尔值。当我们需要判定数组中的元素是否满足某些条件时，可以使用every / some。这两个的区别是，every会去判断判断数组中的每一项，而 some则是当某一项满足条件时返回。

  1. // every
  2. const foo = [5,1,3,7,4].every((item, index) => {
  3.     console.log(`索引：${index}，数值：${item}`)
  4.     return item > 2
  5. })
  6. console.log(foo)
  7. // every 打印：
  8. // 索引：0，数值：5
  9. // 索引：1，数值：1
  10. // false
  12. // some
  13. const foo = [5,1,3,7,4].some((item, index) => {
  14.     console.log(`索引：${index}，数值：${item}`)
  15.     return item > 2
  16. })
  17. console.log(foo)
  18. // some 打印：
  19. // 索引：0，数值：5
  20. // true

7.filter()

  • filter方法用于过滤数组成员，满足条件的成员组成一个新数组返回。
  • 它的参数是一个函数，所有数组成员依次执行该函数，返回结果为true的成员组成一个新数组返回。
  • 该方法不会改变原数组。
  1. const foo = [5,1,3,7,4].filter((item,index) => {
  2.     console.log(`索引：${index}，数值：${item}`)
  3.     return item > 2
  4. })
  5. console.log(foo)
  6. // 打印结果：
  7. // 索引：0，数值：5
  8. // 索引：1，数值：1
  9. // 索引：2，数值：3
  10. // 索引：3，数值：7
  11. // 索引：4，数值：4
  12. // [5, 3, 7, 4]

8.map()

  • map即是 “映射”的意思 ，原数组被“映射”成对应新数组。
  • map：支持return，相当与原数组克隆了一份，把克隆的每项改变了，也不影响原数组。
  1. const foo = [5,1,3,7,4].map((item,index) => {
  2.     console.log(`索引：${index}，数值：${item}`)
  3.     return item + 2
  4. })
  5. console.log(foo)
  6. // 打印结果：
  7. // 索引：0，数值：5
  8. // 索引：1，数值：1
  9. // 索引：2，数值：3
  10. // 索引：3，数值：7
  11. // 索引：4，数值：4
  12. // [7, 3, 5, 9, 6]

9. reduce() / reduceRight()

reduce 从左到右将数组元素做“叠加”处理，返回一个值。reduceRight 从右到左。

  1. const foo = [5,1,3,7,4].reduce((total, cur) => {
  2.     console.log(`叠加：${total}，当前：${cur}`)
  3.     return total + cur
  4. })
  5. console.log(foo)
  6. // 打印结果：
  7. // 叠加：5，当前：1
  8. // 叠加：6，当前：3
  9. // 叠加：9，当前：7
  10. // 叠加：16，当前：4
  11. // 20

10.Object.keys遍历对象的属性

Object.keys方法的参数是一个对象，返回一个数组。该数组的成员都是该对象自身的（而不是继承的）所有属性名，且只返回可枚举的属性。

  1. const obj = {
  2.   p1: 123,
  3.   p2: 456
  4. };
  5. Object.keys(obj) // ["p1", "p2"]

11.Object.getOwnPropertyNames() 遍历对象的属性

Object.getOwnPropertyNames方法与Object.keys类似，也是接受一个对象作为参数，返回一个数组，包含了该对象自身的所有属性名。但它能返回不可枚举的属性。

  1. const arr = ['Hello', 'World'];
  2. Object.keys(arr) // ["0", "1"]
  3. Object.getOwnPropertyNames(arr) // ["0", "1", "length"]

以上遍历方法的区别：

  1. 一：map()，forEach()，filter()循环的共同之处：
  2.   1.forEach，map，filter循环中途是无法停止的，总是会将所有成员遍历完。
  3.   2.他们都可以接受第二个参数，用来绑定回调函数内部的 this 变量，将回调函数内部的 this 对象，指向第二个参数，间接操作这个参数（一般是数组）。
  5. 二：map()、filter()循环和forEach()循环的不同：
  6.    forEach 循环没有返回值； map，filter 循环有返回值。
  8. 三：map()和filter()都会跳过空位，for 和 while 不会
  10. 四：some()和every():
  11.    some()只要有一个是true，便返回true；而every()只要有一个是false，便返回false.
  13. 五：reduce()，reduceRight()：
  14.    reduce是从左到右处理（从第一个成员到最后一个成员），reduceRight则是从右到左（从最后一个成员到第一个成员）。
  16. 六：Object对象的两个遍历 Object.keys 与 Object.getOwnPropertyNames：
  17.    他们都是遍历对象的属性，也是接受一个对象作为参数，返回一个数组，包含了该对象自身的所有属性名。但Object.keys不能返回不可枚举的属性；Object.getOwnPropertyNames能返回不可枚举的属性。

四、常用正则表达式

这里罗列一些我在刷算法题中遇到的正则表达式，如果有时间可认真学一下正则表达式不要背。

1.判断字符

  1. 由26个英文字母组成的字符串：^[A-Za-z]+$
  2. 由26个大写英文字母组成的字符串：^[A-Z]+$
  3. 由26个小写英文字母组成的字符串：^[a-z]+$
  4. 由数字和26个英文字母组成的字符串：^[A-Za-z0-9]+$

2.判断数字

  1. 数字：^[0-9]*$

持续更新，敬请期待……

五、数学知识

1.质数

若一个正整数无法被除了1 和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。

  1. function judgePrime(n) {
  2.     for (let i = 2; i * i <= n; i++) {
  3.         if (n % i == 0) return false
  4.     }
  5.     return true
  6. }

2.斐波那契数列

  1. function Fibonacci(n) {
  2.     if (n <= 1) return n  
  3.     return Fibonacci(n - 1) + Fibonacci(n - 2)
  4. }

持续更新，敬请期待……

参考文章

前端算法入门二：时间空间复杂度&8大数据结构的JS实现

介绍

此篇属于前端算法入门系列的第二篇，主要介绍如何分析算法的时间复杂度和空间复杂度，以及介绍算法题中涉及到的八大常见数据结构，并且给出相应的JavaScript（TypeScript）实现代码，还罗列其使用场景，以及相关leetcode题目。

文章主要包含以下内容：

  • 时间&空间复杂度分析介绍
  1. 时间复杂度分析方法
  2. 空间复杂度分析方法
  • 八大数据结构的JS实现
  1. 栈
  2. 队列
  3. 链表
  4. 集合
  5. 字典
  6. 树
  7. 图
  8. 堆

一、时间&空间复杂度

  • 复杂度是数量级（方便记忆、推广），不是具体数字。
  • 常见复杂度大小比较：O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)

1.时间复杂度

常见时间复杂度对应关系：

  • O(n^2)：2层循环（嵌套循环）
  • O(nlogn)：快速排序（循环 + 二分）
  • O(n)：1层循环
  • O(logn)：二分

2.空间复杂度

常见空间复杂度对应关系：

  • O(n)：传入一个数组，处理过程生成一个新的数组大小与传入数组一致

二、八大数据结构的JS实现

1. 栈

栈是一个后进先出的数据结构。JavaScript中没有栈，但是可以用Array实现栈的所有功能。

JS实现

  1. // 数组实现栈数据结构
  2. const stack = []
  4. // 入栈
  5. stack.push(0)
  6. stack.push(1)
  7. stack.push(2)
  9. // 出栈
  10. const popVal = stack.pop() // popVal 为 2

使用场景

  • 场景一：十进制转二进制
  • 场景二：有效括号
  • 场景三：函数调用堆栈

LeetCode题目

2. 队列

队列是一个先进先出的数据结构。JavaScript中没有队列，但是可以用Array实现队列的所有功能。

JS实现

  1. // 数组实现队列数据结构
  2. const queue = []
  4. // 入队
  5. stack.push(0)
  6. stack.push(1)
  7. stack.push(2)
  9. // 出队
  10. const shiftVal = stack.shift() // shiftVal 为 0

使用场景

  • 场景一：日常测核酸排队
  • 场景二：JS异步中的任务队列
  • 场景三：计算最近请求次数

LeetCode题目

3. 链表

链表是多个元素组成的列表，元素存储不连续，用next指针连在一起。JavaScript中没有链表，但是可以用Object模拟链表。

TS实现

  1. /**
  2.  * 定义一个 node 节点
  3.  */
  4. interface ILinkListNode {
  5.     value: number
  6.     next?: ILinkListNode
  7. }
  9. /**
  10.  * 根据数组创建单向链表
  11.  * @param arr 
  12.  * @returns 
  13.  */
  14. function createLinkList(arr: number[]): ILinkListNode {
  15.     const len = arr.length
  16.     if (len === 0) throw new Error('arr is empty')
  18.     let curNode: ILinkListNode = {
  19.         value: arr[len - 1]
  20.     }
  21.     if (len === 1) return curNode
  23.     for (let i = len - 2; i >= 0; i--) {
  24.         curNode = {
  25.             value: arr[i],
  26.             next: curNode 
  27.         }
  28.     }
  30.     return curNode
  31. }

使用场景

  • 场景一：JS中的原型链
  • 场景二：使用链表指针获取 JSON 的节点值

LeetCode题目

4. 集合

集合是一个无序且唯一的数据结构。ES6中有集合：Set，集合常用操作：去重、判断某元素是否在集合中、求交集。

JS实现

  1. // 去重
  2. const arr = [1, 1, 2, 2]
  3. const arr2 = [...new Set(arr)]
  5. // 判断元素是否在集合中
  6. const set = new Set(arr)
  7. const has = set.has(3) // false
  9. // 求交集
  10. const set2 = new Set([2, 3])
  11. const set3 = new Set([...Set].filter(item => set2.has(item)))

使用场景

  • 场景一：求交集、差集

LeetCode题目

5. 字典(哈希)

字典也是一种存储唯一值的数据结构，但它以键值对的形式存储。ES6中的字典名为Map，

JS实现

  1. // 字典
  2. const map = new Map()
  4. // 增
  5. map.set('key1', 'value1')
  6. map.set('key2', 'value2')
  7. map.set('key3', 'value3')
  9. // 删
  10. map.delete('key3')
  11. // map.clear()
  13. // 改
  14. map.set('key2', 'value222')
  16. // 查
  17. map.get('key2')
  18. 复制代码

使用场景

  • 场景：leetcode刷题

LeetCode题目

6. 树

树是一种分层的数据模型。前端常见的树包括：DOM、树、级联选择、树形控件……。JavaScript中没有树，但是可以通过Object和Array构建树。树的常用操作：深度/广度优先遍历、先中后序遍历。

TS实现

  1. /**
  2.  * 前序遍历：root -> left -> right
  3.  * 中序遍历：left -> root -> right
  4.  * 后序遍历：left -> right -> root
  5.  * 问1：为什么二叉树很重要，而不是三叉树、四叉树？
  6.  * 答：
  7.  * （1）数组、链表各有缺点
  8.  * （2）特定的二叉树（BBST，平衡二叉树）可以结合数组 & 链表的优点，让整体查找效果最优（可用二分法）
  9.  * （3）各种高级二叉树（红黑数、B树），继续优化，满足不同场景
  10.  * 问2：堆特点？和二叉树的关系？
  11.  * 答：
  12.  * （1）逻辑结构是一棵二叉树
  13.  * （2）物理结构是一个数组
  14.  * （3）数组：连续内存 + 节省空间
  15.  * （4）查询比 BST 慢
  16.  * （5）增删比 BST 快，维持平衡更快
  17.  * （6）整体时间复杂度都在 O(logn) 级别，与树一致
  18.  * @description 二叉搜索树
  19.  * @author hovinghuang
  20.  */
  22. interface ITreeNode {
  23.     value: number
  24.     left: ITreeNode | null
  25.     right: ITreeNode | null
  26. }
  28. const treeArr: number[] = []
  30. /**
  31.  * 前序遍历
  32.  * @param node 
  33.  * @returns 
  34.  */
  35. function preOrderTraverse(node: ITreeNode | null): void {
  36.     if (node == null) return
  37.     console.info(node.value)
  38.     treeArr.push(node.value)
  39.     preOrderTraverse(node.left)
  40.     preOrderTraverse(node.right)
  41. }
  43. /**
  44.  * 中序遍历
  45.  * @param node 
  46.  * @returns 
  47.  */
  48. function inOrderTraverse(node: ITreeNode | null): void {
  49.     if (node == null) return
  50.     inOrderTraverse(node.left)
  51.     console.info(node.value)
  52.     treeArr.push(node.value)
  53.     inOrderTraverse(node.right)
  54. }
  56. /**
  57.  * 后序遍历
  58.  * @param node 
  59.  * @returns 
  60.  */
  61. function postOrderTraverse(node: ITreeNode | null): void {
  62.     if (node == null) return
  63.     postOrderTraverse(node.left)
  64.     postOrderTraverse(node.right)
  65.     console.info(node.value)
  66.     treeArr.push(node.value)
  67. }
  69. function getKthValue(node: ITreeNode, k: number): number | null {
  70.     inOrderTraverse(bst)
  71.     return treeArr[k - 1] || null
  72. }
  74. const bst: ITreeNode = {
  75.     value: 5,
  76.     left: {
  77.         value: 3,
  78.         left: {
  79.             value: 2,
  80.             left: null,
  81.             right: null
  82.         },
  83.         right: {
  84.             value: 4,
  85.             left: null,
  86.             right: null,
  87.         }
  88.     },
  89.     right: {
  90.         value: 7,
  91.         left: {
  92.             value: 6,
  93.             left: null,
  94.             right: null
  95.         },
  96.         right: {
  97.             value: 8,
  98.             left: null,
  99.             right: null
  100.         }
  101.     }
  102. }
  104. // 功能测试
  105. // preOrderTraverse(bst)
  106. // inOrderTraverse(bst)
  107. // postOrderTraverse(bst)
  108. // console.info('第3小值', getKthValue(bst, 3))

使用场景

  • 场景一：DOM树
  • 场景二：级联选择器

LeetCode题目

7. 图

图是网络结构的抽象模型，是一组由边连接的节点。图可以表示任何二元关系，比如道路、航班。JS中没有图，但是可以用Object和Array构建图。图的表示法：邻接矩阵、邻接表、关联矩阵。

  1. // 邻接表表示图结构
  2. const graph = {
  3.     0: [1, 2],
  4.     1: [2],
  5.     2: [0, 3],
  6.     3: [3]
  7. }
  9. // 深度优先遍历
  10. const visited = new Set()
  11. function dfs(n, visited) { // n 表示开始访问的根节点
  12.     console.log(n)
  13.     visited.add(n)
  14.     graph[n].forEach((item) => {
  15.         if (!visited.has(item)) dfs(item, visited) 
  16.     })
  17. }
  18. dfs(2, visited) // 2 0 1 3
  19. console.log(visited) // {2, 0, 1, 3}
  21. // 广度优先遍历
  22. function bfs(n) { // n 表示开始访问的根节点
  23.     const visited = new Set()
  24.     visited.add(n)
  25.     const queue = [n]
  26.     while (queue.length) {
  27.         const shiftVal = queue.shift()
  28.         graph[shiftVal].forEach((item) => {
  29.             if (!visited.has(item)) {
  30.                 queue.push(item)
  31.                 visited.add(item)
  32.             } 
  33.         })
  34.     }
  35.     console.log(visited) // {2, 0, 3, 1}
  36. }
  37. bfs(2)

使用场景

  • 场景一：道路
  • 场景二：航班

LeetCode题目

8. 堆

堆是一种特殊的完全二叉树。所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。由于堆的特殊结构，我们可以用数组表示堆。

  1.     1
  2.    / \
  3.   2   3
  4.  / \  /\
  5. 4  5 6
  7. // 数组表示堆结构
  8. const heap = [1, 2, 3, 4, 5, 6]
  10. // 实现一个最小堆类
  11. class MinHeap {
  12.     constructor() {
  13.         this.heap = [];
  14.     }
  15.     swap(i1, i2) {
  16.         const temp = this.heap[i1];
  17.         this.heap[i1] = this.heap[i2];
  18.         this.heap[i2] = temp;
  19.     }
  20.     getParentIndex(i) {
  21.         return (i - 1) >> 1;
  22.     }
  23.     getLeftIndex(i) {
  24.         return i * 2 + 1;
  25.     }
  26.     getRightIndex(i) {
  27.         return i * 2 + 2;
  28.     }
  29.     shiftUp(index) {
  30.         if (index == 0) { return; }
  31.         const parentIndex = this.getParentIndex(index);
  32.         if (this.heap[parentIndex] > this.heap[index]) {
  33.             this.swap(parentIndex, index);
  34.             this.shiftUp(parentIndex);
  35.         }
  36.     }
  37.     shiftDown(index) {
  38.         const leftIndex = this.getLeftIndex(index);
  39.         const rightIndex = this.getRightIndex(index);
  40.         if (this.heap[leftIndex] < this.heap[index]) {
  41.             this.swap(leftIndex, index);
  42.             this.shiftDown(leftIndex);
  43.         }
  44.         if (this.heap[rightIndex] < this.heap[index]) {
  45.             this.swap(rightIndex, index);
  46.             this.shiftDown(rightIndex);
  47.         }
  48.     }
  49.     insert(value) {
  50.         this.heap.push(value);
  51.         this.shiftUp(this.heap.length - 1);
  52.     }
  53.     pop() {
  54.         this.heap[0] = this.heap.pop();
  55.         this.shiftDown(0);
  56.     }
  57.     peek() {
  58.         return this.heap[0];
  59.     }
  60.     size() {
  61.         return this.heap.length;
  62.     }
  63. }
  65. const h = new MinHeap();
  66. h.insert(3);
  67. h.insert(2);
  68. h.insert(1);
  69. h.pop();

使用场景

  • 场景：leetcode刷题

LeetCode题目

参考文章

前端算法入门三：5大排序算法&2大搜索&4大算法思想

介绍

此篇属于前端算法入门系列的第三篇，主要介绍数据结构与算法中的的5大排序算法、2大搜索算法以及我们刷算法面试题常见的4大算法思想，总结常见的解题思路，让你的刷题事半功倍。

文章主要包含以下内容：

  • 冒泡排序
  • 快速排序
  • 插入排序
  • 归并排序
  • 选择排序
  • 顺序搜索
  • 二分搜素
  • 分而治之
  • 动态规划
  • 贪心算法
  • 回溯算法

一、5大基础排序算法

1.冒泡排序（常考）

原理如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个，如果不是相等的就跳过比下面的元素 ，这样依次的循环下去 直到所有的元素都比较完成才结束。
  2. 针对所有的元素重复以上的步骤，除了最后一个。
  3. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  1. function bubbleSort(arr) {
  2.     const len = arr.length
  3.     if (len <= 1) return
  5.     for (let i = 0; i < len - 1; i++) {
  6.         for (let j = 0; j < len - i - 1; j++) {
  7.             if (arr[j] > arr[j + 1]) {
  8.                 const temp = arr[j]
  9.                 arr[j] = arr[j + 1]
  10.                 arr[j + 1] = temp
  11.             }
  12.         }
  13.     }
  14. }
  16. // 功能测试
  17. const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
  18. bubbleSort(arr)
  19. console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

2.快速排序（常考）

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

  1. /**
  2.  * @description 快速排序
  3.  * @author hovinghuang
  4.  */
  6. /**
  7.  * 快速排序 (splice)
  8.  * @param arr 
  9.  * @returns 
  10.  */
  11. function quickSort1(arr: number[]): number[] {
  12.     const len = arr.length
  13.     if (len === 0) return arr
  15.     const midIndex = Math.floor(len / 2)
  16.     const midValue = arr.splice(midIndex, 1)[0]
  18.     const left: number[] = []
  19.     const right: number[] = []
  21.     // 注意： splice 会修改原数组，所以用 arr.length
  22.     for (let i = 0; i < arr.length; i++) {
  23.         const n = arr[i]
  24.         if (n < midValue) {
  25.             left.push(n)
  26.         } else {
  27.             right.push(n)
  28.         }
  29.     }
  30.     return quickSort1(left).concat([midValue], quickSort1(right))
  31. }
  33. /**
  34.  * 快速排序 (slice)
  35.  * @param arr 
  36.  * @returns 
  37.  */
  38.  function quickSort2(arr: number[]): number[] {
  39.     const len = arr.length
  40.     if (len === 0) return arr
  42.     const midIndex = Math.floor(len / 2)
  43.     const midValue = arr.slice(midIndex, midIndex + 1)[0]
  45.     const left: number[] = []
  46.     const right: number[] = []
  48.     for (let i = 0; i < len; i++) {
  49.         if (i === midIndex) continue
  50.         const n = arr[i]
  51.         if (n < midValue) {
  52.             left.push(n)
  53.         } else {
  54.             right.push(n)
  55.         }
  56.     }
  58.     return quickSort2(left).concat([midValue], quickSort2(right))
  59. }
  61. // 功能测试
  62. const testArr3 = [3, 2, 5, 1, 8, 7]
  63. console.info('quickSort2:', quickSort2(testArr3))

3.插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  1. function insertionSort(arr) {
  2.     for (let i = 1; i < arr.length; i++) {
  3.         const temp = arr[i];
  4.         let j = i;
  5.         while (j > 0) {
  6.             if (arr[j - 1] > temp) {
  7.                 arr[j] = arr[j - 1];
  8.             } else {
  9.                 break;
  10.             }
  11.             j--;
  12.         }
  13.         arr[j] = temp;
  14.     }
  15. }
  17. // 功能测试
  18. const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
  19. insertionSort(arr)
  20. console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

4.归并排序

分为两步：

  • 分割：将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  • 归并：将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
  1. function mergeSort(arr) {
  2.     if(arr.length === 1) return arr
  4.     let mid = Math.floor(arr.length / 2)
  5.     let left = arr.slice(0, mid)
  6.     let right = arr.slice(mid)
  8.     return merge(mergeSort(left), mergeSort(right))
  9. }
  11. function merge(a, b) {
  12.     let res = []
  14.     while (a.length && b.length) {
  15.         if (a[0] < b[0]) {
  16.             res.push(a[0])
  17.             a.shift()
  18.         } else {
  19.             res.push(b[0])
  20.             b.shift()
  21.         }
  22.     }
  24.     if(a.length){
  25.         res = res.concat(a)
  26.     } else {
  27.         res = res.concat(b)
  28.     }
  30.     return res
  31. }
  33. // 功能测试
  34. const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
  35. console.log(mergeSort(arr)) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

5.选择排序

其基本思想是：

  • 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置。
  • 接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。
  • 以此类推，直到所有元素均排序完毕。
  1. function selectionSort(arr) {
  2.     for (let i = 0; i < arr.length - 1; i++) {
  3.         let indexMin = i;
  4.         for (let j = i; j < arr.length; j++) {
  5.             if (arr[j] < arr[indexMin]) {
  6.                 indexMin = j;
  7.             }
  8.         }
  9.         if (indexMin !== i) {
  10.             const temp = arr[i];
  11.             arr[i] = arr[indexMin];
  12.             arr[indexMin] = temp;
  13.         }
  14.     }
  15. }
  17. // 功能测试
  18. const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
  19. selectionSort(arr)
  20. console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

6.顺序搜索

  1. function sequentialSearch(arr, target) {
  2.     for (let i = 0; i < arr.length; i++) {
  3.         if (arr[i] === target) {
  4.             return i;
  5.         }
  6.     }
  7.     return -1;
  8. };
  9. const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
  10. console.log(sequentialSearch(arr, 8)) // 7

7.二分搜索

二分搜索，也叫折半搜索，是一种在有序数组中查找特定元素的搜索算法。所以是用二分查找的前提是数组必须是有序的.

  1. /**
  2.  * 凡是有序，必二分
  3.  * 凡是二分，时间复杂度必包含 O(logn)
  4.  * 递归代码思路清晰，非递归性能更好
  5.  * @description 二分查找 (循环)
  6.  * @author hovinghuang
  7.  */
  9. /**
  10.  * 二分查找（循环）
  11.  * @param arr 
  12.  * @param target 
  13.  * @returns 
  14.  */
  15. function binarySearch01(arr: number[], target: number): number {
  16.     const len = arr.length;
  17.     if (len === 0) return -1;
  19.     let startIndex = 0;
  20.     let endIndex = len - 1;
  22.     while (startIndex <= endIndex) {
  23.         const midIndex = Math.floor((startIndex + endIndex) / 2); // 将数字向下舍入到最接近的整数
  24.         const midValue = arr[midIndex];
  26.         if (target < midValue) {
  27.             // 目标值较少，则继续在左侧查找 
  28.             endIndex = midIndex - 1;
  29.         } else if (target > midValue) {
  30.             // 目标值较大，则继续在右侧查找 
  31.             startIndex = midIndex + 1;
  32.         } else {
  33.             return midIndex;
  34.         }
  35.     }
  36.     return -1;
  37. }
  39. /**
  40.  * 二分查找（递归）
  41.  * @param arr 
  42.  * @param target 
  43.  */
  44. function binarySearch02(arr: number[], target: number, startIndex?: number, endIndex?: number): number {
  45.     const length = arr.length
  46.     if (length === 0) return -1
  48.     // 开始和结束的范围
  49.     if (startIndex == null) startIndex = 0
  50.     if (endIndex == null) endIndex = length - 1
  52.     // 如果 start 和 end 相遇则结束
  53.     if (startIndex > endIndex) return -1
  55.     // 中间位置
  56.     const midIndex = Math.floor((startIndex + endIndex) / 2)
  57.     const midValue = arr[midIndex]
  59.     if (target < midValue) {
  60.         // 目标值较小，则继续在左侧查找
  61.         return binarySearch02(arr, target, startIndex, midIndex - 1)
  62.     } else if (target > midValue) {
  63.         // 目标值较大，则继续在右侧查找
  64.         return binarySearch02(arr, target, midIndex + 1, endIndex)
  65.     } else {
  66.         // 相等，返回
  67.         return midIndex
  68.     }
  70. }
  72. // 功能测试
  73. // const testArr = [-20, -10, 30];
  74. // const testTarget = 30;
  75. // console.info(binarySearch02(testArr, testTarget));
  77. // 性能测试
  78. // const testArr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120];
  79. // const testTarget = 30;
  80. // console.time('binarySearch01')
  81. // for (let i = 0; i < 100 * 10000; i++) {
  82. //     binarySearch01(testArr, testTarget)
  83. // }
  84. // console.timeEnd('binarySearch01')
  86. // console.time('binarySearch02')
  87. // for (let i = 0; i < 100 * 10000; i++) {
  88. //     binarySearch02(testArr, testTarget)
  89. // }
  90. // console.timeEnd('binarySearch02')

二、4大算法思想

1.分而治之

分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。

场景一：归并排序

  • 分：把数组从中间一分为二
  • 解：递归的对两个子数组进行归并排序
  • 合：合并有序子数组

场景二：快速排序

  • 分：选基准，按基准把数组分成两个子数组
  • 解：递归的对两个子数组进行快速排序
  • 合：合并两个子数组

leetcode

2.动态规划

动态规划是算法设计中的一种方法。它将一个问题分解成相互重叠的子问题，通过反复求解子问题，来解决原来的问题。

场景一：斐波那契数列

  • 定义子问题：F(n) = F(n - 1) + F(n - 2)
  • 反复执行：从2循环到n，执行上述公式

动态规划和分而治之区别？

  • 区别在于子问题是否独立
  • 动态规划的子问题是重叠的
  • 分而治之的子问题是独立的

leetcode

3.贪心算法

贪心算法是算法设计中的一种方法。期盼通过每个阶段的局部最优选择，从而达到全局最优，但是结果并不一定是最优的。常见的反面例子如：零钱兑换问题。

leetcode

4.回溯算法

回溯算法是算法设计中的一种方法。回溯算法是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

什么问题适合用回溯算法解决？

  • 有很多路
  • 这些路，有思路，也有出路
  • 通常需要递归来模拟所有的路

leetcode

参考文章