JavaScript - 算法/数据结构

三月 11, 2020 12702

JavaScript数据结构和算法，面试手撕代码。

排序

这里基本语法选用ES5了，经测试ES6对性能影响蛮大的。

测试性能: 在执行前打上console.time(label)，执行后打上console.timeEnd(label)。

随机生成数组:

function randomArr(lower, upper, num) {
  var arr = []
  for (var i = 0; i < num; i++)
    arr.push(Math.floor(Math.random() * (lower - upper) + upper))
  return arr
}

var arr = randomArr(1, 100, 10000)

冒泡排序

156.190ms, O(n²), O(1), 稳定

function bubbleSort(arr) {
  var len = arr.length
  for (var i = 0; i < len; i++)
    for (var j = 0; j < len - i - 1; j++)
      if (arr[j] > arr[j + 1])
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
  return arr
}

选择排序

60.689ms, O(n²), O(1), 稳定

function selectSort(arr) {
  var len = arr.length
  for (var i = 0; i < len; i++) {
    var min = i
    for (var j = i; j < len; j++) {
      min = arr[j] < arr[min] ? j : min
    }
    [arr[i], arr[min]] = [arr[min], arr[i]]
  }
  return arr
}

快速排序

14.673ms, O(nlog₂n), O(nlog₂n), 不稳定

function quickSort(arr) {
  if (arr.length <= 1) return arr
  var left = [], right = []
  var pivot = Math.floor(arr.length / 2)
  var pivotValue = arr.splice(pivot, 1)[0]
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivotValue) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), pivotValue, ...quickSort(right)]
}

递归

这里以n的阶乘为例。

普通递归

function factorial(n) {
  if (n === 0)
    return 1
  return n * factorial(n - 1)
}

尾递归

由于普通递归过程中，每次执行都会将调用过程压入调用栈中，如果N的技术比较大，可能会栈溢出，所以这里提供尾递归方式解决这个问题。

function factorial(n, total = 1) {
  if (n === 0)
    return total
  return factorial(n - 1, n * total)
}

注意！在Node.js中需要开启harmony模式实现尾递归，如下：

node --harmony_tailcalls factorial.js

尾递归优化探索

拷贝

基本数据类型: undefined，boolean，number，string，null, symbol

存放在栈内存中的简单数据段，数据大小确定，内存空间大小可以分配，是直接按值存放的，所以可以直接访问。对其进行赋值时，拷贝的是值；修改后它的原始值是不会改变的。

引用类型: object, array

引用类型是存放在堆内存中的，变量实际上是一个存放在栈内存的指针，这个指针指向堆内存中的地址。每个空间大小不一样，要根据情况开进行特定的分配。对其进行赋值时，拷贝的是地址空间；修改后它的原始值会一起改变。

—	和原数据是否指向同一对象	第一层数据为基本数据类型	原数据中包含子对象
赋值	是	改变会使原数据一同改变	改变会使原数据一同改变
浅拷贝	否	改变不会使原数据一同改变	改变会使原数据一同改变
深拷贝	否	改变不会使原数据一同改变	改变不会使原数据一同改变

示例对象:

const user = {
  name: 'zhaoo',
  gender: 0,
  social: {
    email: 'izhaoo@163.com',
    qq: '894519210',
    wechat: undefined,
  },
  vip: null,
  friendId: [1, 43, 23, 21]
}

赋值

user1 = user

浅拷贝

assign

const user1 = Object.assign({}, user)

深拷贝

JSON

user1 = JSON.parse(JSON.stringify(user))

递归遍历

module.exports = function clone(target) {
  if (typeof target === 'object') {
    let cloneTarget = Array.isArray(target) ? [] : {};
    for (const key in target) {
      cloneTarget[key] = clone(target[key]);
    }
    return cloneTarget;
  } else {
    return target;
  }
};

防抖节流

防抖

任务频繁触发的情况下，只有任务触发的间隔超过指定间隔的时候，任务才会执行

搜索补全

function debounce(fn) {
  let timeout = null;
  return function() {
    clearTimeout(timeout);
    timeout = setTimeout(() => {
      fn.call(this, arguments);
    }, 1000);
  };
}

节流

指定时间间隔内只会执行一次任务

懒加载监听滚动条位置、发送验证码计时器

function throttle(fn) {
  let canRun = true;
  return function() {
    if(!canRun) {
      return;
    }
    canRun = false;
    setTimeout( () => {
      fn.call(this, arguments);
      canRun = true;
    }, 1000);
  };
}

手写源码

call

//每个函数有this和args两个默认参数
Function.prototype.myCall = function (context) {
  //传入的对象为空（null,number...）时指定为全局环境
  var context = context || window
  //用this获取调用myCall的函数
  //fn.call(a, 'yck', '24') => this = fn
  context.fn = this
  //args是伪数组，没有slice这个方法
  var args = [...arguments].slice(1)
  //执行并保存结果
  var result = context.fn(...args)
  //删除这个fn对象
  delete context.fn
  //返回结果
  return result
}

apply

Function.prototype.myApply = function (context) {
  var context = context || window
  context.fn = this
  var result
  if (arguments[1]) {
    result = context.fn(...arguments[1])
  } else {
    result = context.fn()
  }
  delete context.fn
  return result
}

bind

Function.prototype.myBind = function (context) {
  // if (typeof this !== 'function') {
  //   throw new TypeError('Error')
  // }
  var fn = this
  var args = [...arguments].slice(1)
  return function F() {
    if (this instanceof F) {
      return new fn(...args, ...arguments)
    }
    return fn.apply(context, args.concat(...arguments))
  }
}

new

function new() {
  let obj = new Object()
  let Constructor = [].shift.call(arguments)
  obj.__proto__ = Constructor.prototype
  let result = Constructor.apply(obj, arguments)
  return typeof result === 'object' ? result : obj
}

function student(name, gender) {
  this.name = name
  this.gender = gender
}

var zhaoo = new(student, 'zhaoo', 'male')

创建一个空的简单JavaScript对象（即{}）；
链接该对象（即设置该对象的构造函数）到另一个对象；
将步骤1新创建的对象作为this的上下文；
如果该函数没有返回对象，则返回this。

数据结构

栈

后进先出 (LIFO)

class Stack {
  constructor() {
    this.stack = []
  }
  push(item) {
    this.stack.push(item)
  }
  pop() {
    this.stack.pop()
  }
  peek() {
    return this.stack[this.getCount() - 1]
  }
  getCount() {
    return this.stack.length
  }
  isEmpty() {
    return this.getCount() === 0
  }
}

队列

先进先出 (FIFO)

class Queue {
  constructor() {
    this.queue = []
  }
  enQueue(item) {
    this.queue.push(item)
  }
  deQueue() {
    return this.queue.shift()  //使用数组比较消耗性能
  }
  getHeader() {
    return this.queue[0]
  }
  getLength() {
    return this.queue.length
  }
  isEmpty() {
    return this.getLength() === 0
  }
}

优先级队列

class PriorityQueue {
  constructor() {
    this.queue = [{
      priority
      value
    }]
  }
  enQueue(item) {
    if (this.isEmpty()) {
      this.queue.push(item)
    } else {
      var flag = false;  //判断是否排队
      for (let i = this.queue.length - 1; i > 0; i--) {
        if (this.queue[i].priority <= item.priority) {
          this.queue.splice(i, 0, item)
          flag = true
          break
        }
      }
      //循环后未入队，优先级最大，插入到第一位
      if (!flag) {
        this.queue.unshift(item);
      }
    }
  }
}

链表

// 节点
function Node (el) {
  this.el = el;
  this.next = null;
}

// 构造函数
function Link () {
  this.head = new Node('head');
}

// 链表结尾追加一个节点
Link.prototype.append = function (el) {
  var currNode = this.head;
  while (currNode.next != null) {
    currNode = currNode.next;
  }
  currNode.next = new Node(el);
}

// 按节点的值查找节点
Link.prototype.find = function (el) {
  var currNode = this.head;
  while (currNode && currNode.el != el) {
    currNode = currNode.next;
  }
  return currNode;
}

// 插入一个节点
Link.prototype.insert = function (newEl, oldEl) {
  var newNode = new Node(newEl);
  var findNode = this.find(oldEl);
  if (findNode) {
    newNode.next = findNode.next;
    findNode.next = newNode;
  } else {
    throw new Error('找不到给定插入的节点');
  }
}

// 展示链表中的元素
Link.prototype.display = function () {
  var currNode = this.head.next;
  while (currNode) {
    console.log(currNode.el);
    currNode = currNode.next;
  }
}

// 寻找给定节点的前一个节点
Link.prototype.findPrev = function (el) {
  var currNode = this.head;
  while (currNode.next && currNode.next.el !== el) {
    currNode = currNode.next;
  }
  return currNode;
}

// 删除给定的节点
Link.prototype.remove = function (el) {
  var prevNode = this.findPrev (el);
  if (prevNode.next != null) {
    prevNode.next = prevNode.next.next;
  } else {
    throw new Error('找不到要删除的节点');
  }
}

双向链表


// 双链表构造函数
function DNode (el) {
  this.el = el;
  this.prev = null;
  this.next = null;
}

function DLink() {
  this.head = new DNode('head');
}

// 在链表结尾添加一个新的节点
DLink.prototype.append = function (el) {
  var currNode = this.head;
  while (currNode.next != null) {
    currNode = currNode.next;
  }
  var newNode = new Node(el);
  newNode.next = currNode.next;
  newNode.prev = currNode;
  currNode.next = newNode;
}

// 根据节点的值查找链表节点
DLink.prototype.find = function (el) {
  var currNode = this.head;
  while (currNode && currNode.el != el) {
    currNode = currNode.next;
  }
  return currNode;
}

// 插入一个节点
DLink.prototype.insert = function (newEl, oldEl) {
  var newNode = new DNode(newEl);
  var currNode = this.find(oldEl);
  if (currNode) {
    newNode.next = currNode.next;
    newNode.prev = currNode;
    currNode.next = newNode;
  } else {
    throw new Error('未找到指定要插入节点位置对应的值！')
  }
}


// 顺序展示链表节点
DLink.prototype.display = function () {
  var currNode = this.head.next;
  while (currNode) {
    console.log(currNode.el);
    currNode = currNode.next;
  }
}

// 查找最后一个节点
DLink.prototype.findLast = function () {
  var currNode = this.head;
  while (currNode.next != null) {
    currNode = currNode.next;
  }
  return currNode;
}

// 逆序展示链表节点
DLink.prototype.dispReverse = function () {
  var currNode = this.head;
  currNode = this.findLast();
  while (currNode.prev != null) {
    console(currNode.el);
    currNode = currNode.prev;
  }
}

// 删除给定的节点
DLink.prototype.remove = function (el) {
  var currNode = this.find(el);
  if (currNode && currNode.next != null) {
    currNode.prev.next = currNode.next;
    currNode.next.prev = currNode.prev;
    currNode.next = null;
    currNode.previous = null;
  } else {
    throw new Error('找不到要删除对应的节点');
  }
}

循环链表

// 循环链表构造函数
function CLink() {
  this.head = new Node('head');
  this.head.next = this.head;
}

// 向循环链表结尾新增一个节点
CLink.prototype.append = function (el) {
  var currNode = this.head;
  while (currNode.next != null && currNode.next != this.head) {
    currNode = currNode.next;
  }
  var newNode = new Node(el);
  newNode.next = currNode.next;
  currNode.next = newNode;
}

// 根据节点的值查找链表节点
CLink.prototype.find = function (el) {
  var currNode = this.head;
  while (currNode && currNode.el != el && currNode.next != this.head) {
    currNode = currNode.next;
  }
  return currNode;
}

// 插入一个节点
CLink.prototype.insert = function (newEl, oldEl) {
  var newNode = new Node(newEl);
  var currNode = this.find(oldEl);
  if (currNode) {
    newNode.next = currNode.next;
    currNode.next = newNode;
  } else {
    throw new Error('未找到指定要插入节点位置对应的值！');
  }
}

// 展示链表元素节点
CLink.prototype.display = function () {
  var currNode = this.head.next;
  while (currNode && currNode != this.head) {
    console.log(currNode.el);
    currNode = currNode.next;
  }
}

// 寻找前一个节点
CLink.prototype.findPrev = function (el) {
  var currNode = this.head;
  while (currNode.next && currNode.next.el !== el) {
    currNode = currNode.next;
  }
  return currNode;
}

// 删除给定的节点
CLink.prototype.remove = function (el) {
  var prevNode = this.findPrev(el);
  if (prevNode.next != null) {
    prevNode.next = prevNode.next.next;
  } else {
    throw new Error('找不到要删除的节点');
  }
}

集合

class Collection {
  constructor(data) {
    this.collection = new Set(data);
  }

  add(data) {
    this.collection.add(data);
  }

  get() {
    return this.collection;
  }

  remove(data) {
    this.collection.remove(data);
  }

  has(data) {
    return this.collection.has(data);
  }

  size() {
    return this.collection.size;
  }

  values() {
    return this.collection;
  }

  union(collection) {
    let arr1 = Array.from(collection);
    let arr2 = Array.from(this.collection);
    return new Set(arr1.concat(arr2));
  }

  intersect(collection) {
    let arr = new Set();
    this.collection.forEach(element => {
      if (collection.has(element)) {
        arr.add(element);
      }
    });
    return arr;
  }

  difference(collection) {
    let arr = new Set();
    this.collection.forEach(element => {
      if (!collection.has(element)) {
        arr.add(element);
      }
    });
    return arr;
  }

  sub(collection) {
    if (this.size() < collection.size()) {
      return false;
    } else {
      let res = true;
      collection.values().forEach(element => {
        if (!this.collection.has(element)) {
          res = false;
        }
      });
      return res;
    }
  }
}

参考资料

js 深拷贝 vs 浅拷贝

如何写出一个惊艳面试官的深拷贝?

本文作者：zhaoo
本文链接：https://www.izhaoo.com/2020/03/11/js-structure-algorithm/index.html
版权声明：本博客所有文章均采用 BY-NC-SA 许可协议，转载请注明出处！

查看评论