二、基本概念

常常听到算法的时候，就会有人说到 时间复杂度， 空间复杂度。那么这俩玩意是啥呢，下面我就来一一解释

1. 时间复杂度

其实就是一个函数，用大 O 表示， 比如 O(1)、 O(n)...

它的作用就是用来定义描述算法的运行时间

2. 空间复杂度

和时间复杂度一样，空间复杂度也是用大 O 表示，比如 O(1)、 O(n)...

它用来定义描述算法运行过程中临时占用的存储空间大小(占用越少 代码写的就越好)

三、数据结构

1. 栈

一个后进先出的数据结构

按照常识理解就是有序的挤公交，最后上车的人会在门口，然后门口的人会最先下车

js中没有栈的数据类型，但我们可以通过Array来模拟一个

const stack = [];

stack.push(1); // 入栈
stack.push(2); // 入栈

const item1 = stack.pop();  //出栈的元素

1）十进制转二进制

// 时间复杂度 O(n) n为二进制的长度
// 空间复杂度 O(n) n为二进制的长度
const dec2bin = (dec) => {
  // 创建一个字符串
  let res = "";

  // 创建一个栈
  let stack = []

  // 遍历数字 如果大于0 就可以继续转换2进制
  while (dec > 0) {
    // 将数字的余数入栈
    stack.push(dec % 2);

    // 除以2
    dec = dec >> 1;
  }

  // 取出栈中的数字
  while (stack.length) {
    res += stack.pop();
  }

  // 返回这个字符串
  return res;
};

const isValid = (s) => {

  // 如果长度不等于2的倍数肯定不是一个有效的括号
  if (s.length % 2 === 1) return false;

  // 创建一个栈
  let stack = [];

  // 遍历字符串
  for (let i = 0; i < s.length; i++) {

    const c = s[i];

    // 如果是左括号就入栈
    if (c === '(' || c === "{" || c === "[") {
      stack.push(c);
    } else {

      // 如果不是左括号 且栈为空 肯定不是一个有效的括号 返回false
      if (!stack.length) return false

      // 拿到最后一个左括号
      const top = stack[stack.length - 1];

      // 如果是右括号和左括号能匹配就出栈
      if ((top === "(" && c === ")") || (top === "{" && c === "}") || (top === "[" && c === "]")) {
        stack.pop();
      } else {

        // 否则就不是一个有效的括号
        return false
      }
    }

  }
  return stack.length === 0;
};

2）判断字符串的有效括号

const isValid = (s) => {

  // 如果长度不等于2的倍数肯定不是一个有效的括号
  if (s.length % 2 === 1) return false;

  // 创建一个栈
  let stack = [];

  // 遍历字符串
  for (let i = 0; i < s.length; i++) {

    const c = s[i];

    // 如果是左括号就入栈
    if (c === '(' || c === "{" || c === "[") {
      stack.push(c);
    } else {

      // 如果不是左括号 且栈为空 肯定不是一个有效的括号 返回false
      if (!stack.length) return false

      // 拿到最后一个左括号
      const top = stack[stack.length - 1];

      // 如果是右括号和左括号能匹配就出栈
      if ((top === "(" && c === ")") || (top === "{" && c === "}") || (top === "[" && c === "]")) {
        stack.pop();
      } else {

        // 否则就不是一个有效的括号
        return false
      }
    }

  }
  return stack.length === 0;
};

2. 队列

和栈相反 先进先出的一个数据结构

按照常识理解就是银行排号办理业务, 先去领号排队的人, 先办理业务

同样 js中没有队列的数据类型，但我们可以通过 Array来模拟一个

const queue = [];

// 入队
queue.push(1);
queue.push(2);

// 出队
const first = queue.shift();
const end = queue.shift();

1）最近的请求次数

var RecentCounter = function () {
  // 初始化队列
  this.q = [];
};

// 输入 inputs = [[],[1],[100],[3001],[3002]] 请求间隔为 3000ms
// 输出 outputs = [null,1,2,3,3]   

// 时间复杂度 O(n) n为剔出老请求的长度
// 空间复杂度 O(n) n为最近请求的次数
RecentCounter.prototype.ping = function (t) {
  // 如果传入的时间小于等于最近请求的时间，则直接返回0
  if (!t) return null

  // 将传入的时间放入队列
  this.q.push(t);

  // 如果队头小于 t - 3000 则剔除队头
  while (this.q[0] < t - 3000) {
    this.q.shift();
  }

  // 返回最近请求的次数
  return this.q.length;
};

3. 链表

多个元素组成的列表，元素存储不连续，通过 next 指针来链接, 最底层为 null

就类似于 父辈链接关系 吧， 比如：你爷爷的儿子是你爸爸，你爸爸的儿子是你，而你假如目前还没有结婚生子，那你就暂时木有儿子

js中类似于链表的典型就是原型链, 但是js中没有链表这种数据结构，我们可以通过一个object来模拟链表

const a = {
  val: "a"
}

const b = {
  val: "b"
}

const c = {
  val: "c"
}

const d = {
  val: "d"
}

a.next = b;
b.next = c;
c.next = d;

// const linkList = {
//    val: "a",
//    next: {
//        val: "b",
//        next: {
//            val: "c",
//            next: {
//                val: "d",
//                next: null
//            }
//        }
//    }
// }

// 遍历链表
let p = a;
while (p) {
  console.log(p.val);
  p = p.next;
}

// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;


// 删除
c.next = d;

1）手写instanceOf

const myinstanceof = (val, target) => {
            if(!val) return
            let data = val
            while(data) {
                if(data.__proto__ == target.prototype)  return true
                data =  data.__proto__
            }
            return false
        }

        myinstanceof(str, String)

2）删除链表中的节点

const deleteNode = (node) => {
  // 把当前链表的指针指向下下个链表的值就可以了
  node.val = node.next.val;
  node.next = node.next.next
}

4. 集合

一种无序且唯一的数据结构

ES6中有集合 Set类型

const arr = [1, 1, 1, 2, 2, 3];

// 去重
const arr2 = [...new Set(arr)];

// 判断元素是否在集合中
const set = new Set(arr);
set.has(2) // true

//  交集
const set2 = new Set([1, 2]);
const set3 = new Set([...set].filter(item => set.has(item)));

1）去重

具体代码在上面介绍中有写过，就不再重写了

2）两个数组的交集

const intersection = (nums1, nums2) => {

  // 通过数组的filter选出交集
  // 然后通过 Set集合 去重 并生成数组
  return [...new Set(nums1.filter(item => nums2.includes(item)))];
}

5. 字典

与集合类似，一个存储唯一值的结构,以键值对的形式存储