Fridolph Notes

Appearance

知识点梳理 ​

  • 常见的数据结构
  • 栈、队列、链表
  • 集合、字典、散列集
  • 常见算法
  • 递归
  • 排序
  • 枚举
  • 算法复杂度分析
  • 算法思维
  • 分治
  • 贪心
  • 动态规划
  • 高级数据结构
  • 树、图
  • 深度优先和广度优先搜索

数据结构和算法 ​

数据结构决定了数据存储的空间和时间效率，数据的写入和提取速度要求也决定了应该选择怎样的数据结构。

  • 简单数据结构（必须掌握理解）
    • 有序数据结构：栈、队列、链表，有序结构节省空间（空间小）
    • 无序数据结构：集合、字典、散列表，无序数据结构省时间（读取快）
  • 复杂数据结构
    • 树、堆
    • 图

根据真实面试题来介绍数据结构设计：

使用JS代码实现一个事件类，包含以下功能：绑定事件、解绑事件和派发事件

该题目核心是事件类型对应回调函数的数据设计。为实现绑定，我们需要一个_cache对象来记录绑定了哪些事件。而事件发生时，我们需要从_cache中读取出来事件回调，依次执行。一般页面中派发（读）比事件绑定（写）要多。所以我们设计的数据结构应该尽量地能够在事件发生时，更快地找到对应事件的回调函数，然后执行：

js
class Event {
  constructor() {
    // 存储事件的数据结构
    // 为了迅速查找，使用字典（对象）
    this._cache = {}
  }

  // 绑定
  on(type, callback) {
    // 为了按类方便查找和节省空间爱你，将同类型事件放到一个数组中
    // 这里的数组是队列，遵循先进先出，即先绑定的事件先触发
    let fns = (this._cache[type] = this._cache[type] || [])
    if (fns.indexOf(callback) === -1) {
      fns.push(callback)
    }
    return this
  }

  // 触发
  trigger(type, data) {
    let fns = this._cache[type]
    if (Array.isArray(fns)) {
      fns.forEach(fn => {
        fn(data)
      })
    }
    return this
  }

  // 解绑
  off(type, callback) {
    let fns = this._cache[type]
    if (Array.isArray(fns)) {
      if (callback) {
        let index = fns.indexOf(callback)
        if (index !== -1) {
          fns.splice(index, 1)
        }
      } else {
        // 全部清空
        fns.length = 0
      }
    }
    return this
  }
}

// 测试用例
const event = new Event()
event.on('test', data => {
  console.log(data)
})
event.trigger('test', 'hello world') // Event hello world
event.off('test') // Event
event.trigger('test', 'hello world') // Event

算法的效率是通过算法复杂度来衡量的 ​

算法复杂度包括时间复杂度和空间复杂度。时间复杂度由于好估算、好评估等特点，是面试中考察的重点，空间复杂度稍少些。

常见的时间复杂度有：

  • 常阶数 O(1)
  • 对阶数 O(logN)
  • 线性阶 O(n)
  • 线顶对数阶 O(nlogN)
  • 平方阶 O(n^2)
  • 立方阶 O(n^3)
  • k次方阶 O(n^k)
  • 指数阶 O(2^n)

随着问题规模 n 的不断增大，上述时间复杂度不断增加，算法执行效率越低。

一般做算法复杂度分析时，遵循下面技巧：

  1. 看看有几重循环，一般来说一重就是O(n)，两重就是O(n^2)以此类推
  2. 如果有二分，则为O(logN)
  3. 保留最高项，去除常数项

题目：分析下面代码的算法复杂度

js
let i = 0 // 语句执行一次
while (i < n) { // 语句执行n次
  console.log(`Current i is ${i}`) // 语句执行n次
  i++ // 语句执行n次
}
// 根据注释，算法复杂度为 1 + n + n + n = 3n + 1，去除常数项，为O(n)

let num = 1 // 1
while (num < n) { // logN
  num *= 2 // logN
}
// 2logN + 1 ，复杂度为 O(logN)

for (let i = 0; i < n; i++) { // n
  for (let j = i + 1; j < n; j++) { // n^2 - 1次
    console.log('hello') // n^2 - 1
  }
}
// 2n^2 + n - 1 最终 O(n^2)

必掌握的基础算法 ​

枚举和递归是最简单的算法，也是复杂算法的基础。枚举相对简单，重点说下递归，组成部分如下：

  1. 递归主体，就是要循环解决问题的部分
  2. 递归的跳出条件，递归不能一直递归下去，需要完成一定条件后跳出

实现JS对象的深拷贝

js
function deepCopy(target, newObj) {
  for (let key in target) {
    if (typeof target[key] === 'object') {
      if (Array.isArray(target[key])) {
        newObj[key] = []
        deepCopy(newObj[key], target[key])
      } else
      newObj[key] = {}
      deepCopy(newObj[key], target[key])
    } else {
      newObj[key] = target[key]
    }
  }
  return newObj
}

递归容易造成爆栈，尾部调用可以解决递归的这个问题。Chrome的V8引擎做了尾部调用优化，我们在写代码时也要注意尾部调用写法。递归的爆栈问题可以通过将递归改写为枚举的方式解决，就是通过for或者while来替代递归

求斐波那契数列的第n项

下面的代码中 count记录递归的次数，我们来看下两种差异性的代码中count的值:

js
let count = 0
function fn(n) {
  let chache = {}
  function _fn(n) {
    if (cache[n]) {
      return cache[n]
    }
    count++
    if (n == 1 || n == 2) {
      return 1
    }
    let prev = _fn(n - 1)
    cache[n - 1] = prev
    let next = _fn(n - 2)
    cache[n - 2] = next
    return prev + next
  }
  return _fn(n)
}

let count2 = 0
function fn2(n) {
  count++
  if (n == 1 || n == 2) {
    return 1
  }
  return fn2(n - 1) + fn2(n - 2)
}

console.log(fn(20), count); // 6765 20
console.log(fn2(20), count2); // 6765 13529

快速排序 ​

快排和二分查找都基于一种叫做分而治之的算法思想，通过对数据进行分类处理，不断降级数量级，实现O(logN)的复杂度（对数级别，对O(n)这种线型复杂度更低的一种，快排核心是二分法的O(logN)，实际复杂度为O(N*logN)）

快速排序

大致流程：

  1. 随机选择数组中的一个数A，以这个数为基准
  2. 其他数字跟这个数进行比较，比这个数小的放其左边，大的放其右边
  3. 经过一次循环，A左边为小于A的，右边为大于A的
  4. 这时将左边和右边的数再递归上面的过程
js
const arr = [85, 24, 63, 45, 17, 31, 96, 50];
function quickSort(arr) {
  let len = arr.length
  if (len <= 1) return arr
  let pointIdx = Math.floor(len / 2)
  let point = arr.splice(pointIdx, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < len; i++) {
    if (arr[i] < point) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([point], quickSort(right))
}
quickSort(arr)

二分查找 ​

二分查找猪哟呵是解决 - 在一堆有序的数中找出指定的数 这类问题，不管这些数是一维数组还是多维数组，只要有序，就可以用二分查找来优化。

二分查找也是一种分而治之思想算法，流程如下：

  1. 在数组中排在中间的数num, 与要找的数比较大小
  2. 因数组有序 a. num较大则说明要查找数该从前半部分找 b. num较小则说明要查找数该从后半部分找
  3. 这样不断查找缩小数量级，（扔掉一半数组）直到找完数组为止

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

js
function binary(target, array) {
  let i = 0
  let j = array[i].length - 1
  while (i < array.length && j >= 0) {
    if (array[i][j] < target) {
      i++
    } else if (array[i][j] > target) {
      j--
    } else {
      return true
    }
  }
  return false
}

遇到不会的算法题 ​

听好关键词，比如：有序的数列做查找、要求算法复杂度是O(logN)这类一般用二分思想

算法题一般解决思路：

  1. 想降低数量级，拿可以计算出来的情况来构思解题思路
  2. 根据解题思路编写程序，优先将特殊情况做好判断处理，比如一个大数组的问题，如果数组长度为2的情况
  3. 校验程序正确性
  4. 是否可优化，由浅到深

正则匹配解题 ​

字符串中第一次给出现一次的字符

如果用纯算法来遍历统计字符出现次数，过程较繁琐，用正则就简化了许多：

js
function firstLetter(str) {
  for (let i = 0, len = str.length; i < len; i++) {
    let char = str[i]
    let reg = new RegExp(char, 'g')
    let l = str.match(reg).length
    if (l === 1) {
      return char
    }
  }
}

千分位标注。将1234567变成1,234,567

该题可以利用正则的零宽断言(?=exp)，意思是它断言自身出现的位置后面能匹配表达式exp。

对于零宽断言的详细介绍可以阅读「零宽断言」这篇文章。

数字千分位的特点是，第一个逗号后面的数字个数是3的倍数，正则：/\d{3}+$/; 第一个逗号前最多可以有1~3个数字，正则：/\d{1,3}/, 加起来就是/\d{1,3}(\d{3})+$/，分隔符要从前往后加。

js
function exchange(num) {
  num += '' // 先转成字符串
  if (num.length < 3) return num

  num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, v => {
    console.log(v)
    return v + ','
  })
  return num
}

总结 ​

本节介绍了数据结构与算法的关系，作为一名前端也应该学习数据结构和算法知识，顺带介绍下正则匹配。

当然算法还有很多知识，比如动态规划这些算法思想，还有图和树常用到的广度有限搜索和深度有限搜索。

共 20 个模块，1301 篇 Markdown 文档。

Built with VitePress