算法基础

• 算法基础
  • 时间复杂度和计算方法
  • 空间复杂度
  • 栈
  • 队列
  • 链表
  • 集合
  • 字典 map
  • 树

时间复杂度和计算方法

计算时间复杂度就是计算代码执行多少次，循环多少次。

例:

o(1)
n+1=2
console.log(n)

o(n)
for(let i = 0;i < n;i++){
    console.log(i)
}

o(n^2)
for(let i =0;i<n;i++){
    for(let j = 0;j < n;j++){
        console.log()
    }
}

o(logN)
let i =1
while(i<n){
    i* = 2
    console.log(n)
}

递归进行一次递归调用，每次递归调用的最大深度为 logn。考虑递归最大深度即可

时间复杂度为 O(logn)

一次递归中调用多次递归，这里需要画出递归树进行分析，考虑的是递归调用次数

也就是二叉树的节点个数，O(2^n)

对于较复杂的情况，也是调用多次递归，这里计算复杂度是通过话出递归树，然后计算层数和每个节点处理的时间复杂度

归并排序和快速排序，一共有 logn 层，然后每一层需要处理的节点是 n 个节点，所以时间复杂度为 O(nlogn)

空间复杂度

空间复杂度计算就是计算声明的变量，或者内存变量是多少个

例:

O(1);
let i = 1;
console.log(1);

O(n);
let a = [];
for (let i = 0; i < n; i++) {
  a.push[i];
}

O(n ^ 2);

let a = [];
for (let i = 0; i < n; i++) {
  a.push([]);
  for (let j = 0; j < n; j++) {
    a[i][j].push(j);
  }
}

栈

后进先出的一种内存结构.比如 js 中的数组

let stack = [];
let item1 = stack.push(1);
let item2 = stack.pop();

栈这种数据结构出现得场景

• 十进制转二进制 在利用短除法时计算二进制,最后取的是余数从后面排到前面,采用的是栈的思想,后进先出。
• 有效的花括号，例如判断一堆括号是否是有效的闭合的就可以采用栈的形式

解决这个问题的思路就是使用栈,首先遍历字符串，然后如果元素碰到{([这种字符就往栈推送元素，否则判断元素和栈顶元素是否同时满足{} (),[]这种组合。满足则将元素推出栈。最后判断是否栈为空，为空则返回true

function isvalid(s) {
  let stack = [];
  if (stack.length % 2 === 1) {
    return false;
  }
  for (let i = 0; i < s.length; i++) {
    let c = s[i];
    if (c === "{" || c === "(" || c === "[") {
      stack.push(c);
    } else {
      let p = stack[stactk.length - 1];
      if ((p === "(" && c === ")") || (p === "{" && c === "}" && p === "[" && p === "]")) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return statck.length === 0;
}

• 函数调用,js 解析器就使用了栈

// 首先入栈func1 func2 func3 出栈先调用func3 func2 func1
const func1 = () => {
  fun2();
};
const func2 = () => {
  func3();
};

func1();

队列

先进先出

const array = [];
array.push();
array.shift();

使用场景:

• 食堂打饭
• js 异步任务队列

• 计算请求次数

计算三千毫秒以内的请求次数

输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]] 输出：[null,1,2,3,3]

时间复杂度 o(n),空间复杂度 O(队列长度)

function counter() {
  // 保证使用同一个队列
  this.q = [];
}

Function.prototype.ping = function(t) {
  // 请求时间入队
  this.q.push(t);
  // 大于三千毫秒出队
  while (this.q[0] < t - 3000) {
    this.q.shift();
  }
  return this.q.length;
};

var counter = new counter();
counter.ping(t);

链表

链表元素可以用对象进行模拟,相比与数组最大的特点就是不用移动元素位置

const a = { val: "a" };
const b = { val: "b" };
const c = { val: "c" };

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

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

// 增加
const e = { val: "e" };
a.next = e;
e.next = b;

// 删除
a.next = b;

删除某个节点

思路就是将节点换成下个节点的值，然后删除掉下个节点

var deleteNode = function(node) {
  node.val = node.next.val;
  node.next = node.next.next;
};

反转链表

首先定义双指针遍历，p1,p2 分别指向头部和 null，然后在遍历能进行的条件下将 p1 指向 p2

var reverseList = function(head) {
  let p1 = head;
  let p2 = null;
  while (p1) {
    // 保存状态
    const temp = p1.next;
    // 反转
    p1.next = p2;
    // 双指针遍历 一前一后
    p2 = p1;
    p1 = temp;
  }
  // p1最后指向null
  return p2;
};

两数之和

思路: 首先设置两个指针，新建一个链表

如果两个链表元素的值相加大于 10，就把个位数追加进新链表，十位数放到下一次再增加 每次添加的值都是: 两个链表的值再加上十位数的值

最后遍历链表。如果链表循环结束之后还有进 1 情况，就把 carry 追加到链表上面，最后返回新链表

var addTwoNumbers = function(l1, l2) {
  // 初始化链表
  const l3 = new ListNode(0);
  let p1 = l1;
  let p2 = l2;
  let p3 = l3;
  // 下一轮要加的数
  let carry = 0;
  while (p1 || p2) {
    // 取值
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;
    const v3 = v1 + v2 + carry;
    // 获取下一轮叠加数字 也就是获取十位数
    carry = Math.floor(v3 / 10);
    // 获取本轮个位上数 然后追加到链表上
    p3.next = new ListNode(v3 % 10);
    // 遍历链表
    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
    p3 = p3.next;
  }
  // 需要考率到while循环之后进1情况
  if (carry) {
    p3.next = new ListNode(carry);
  }
  return l3.next;
};

删除链表重复元素

节点值和下个节点值相同，删除

function deleteAlreadyExisted(head) {
  let p = head;
  while (p && p.next) {
    if (p.val === p.next.val) {
      p.next = p.next.next;
    }
  }
  return head;
}

判断是否是环形链表

定义两个一块一慢的指针遍历，相逢则成环

function isCircleListNode(head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      return true;
    }
  }
  return false;
}

集合

无需且唯一的数据结构，可以去重

// 去重
const arr1 = [1, 2, 3, 4, 4, 4];
const arr2 = [...new Set(arr1)];

// 判断一个值是否存在集合中
const set1 = new Set([1, 2]);
set1.has(1);

// 求交集
const set2 = new Set([1, 2, 3, 4, 5]);
const set3 = new Set([...set1].filter(item => set2.has(item) === item));

求两个数组的交集

[...new Set(nums1)].filter(item => nums2.includes(item));

字典 map

求一个字符的不重复最长子串长度

var lengthOfLongestSubstring = function(s) {
  let l = 0;
  let res = 0;
  // 记录子串位置和值
  const map = new Map();
  for (let r = 0; r < s.length; r++) {
    // 遇到重复的就把左指针移动到重复节点的下一个 并且需要保证map中保存的数据是在滑动窗口中
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1;
    }
    res = Math.max(res, r - l + 1);
    map.set(s[r], r);
  }
  return res;
};

时间: O(n) 空间: O(m) 不重复子串长度

树

深度广度优先遍历

深度优先遍历: 将他看成正常看书顺序，先封面，再从第一章开始看依次下去

口诀: 先访问根节点，再挨个深度有限遍历根节点的 children

const tree = {
  val: "a",
  children: [
    {
      val: "b",
      children: [
        {
          val: "d",
          children: []
        },
        {
          val: "e",
          children: []
        }
      ]
    },
    {
      val: "c",
      children: [
        {
          val: "f",
          children: []
        },
        {
          val: "g",
          children: []
        }
      ]
    }
  ]
};

let dfs = root => {
  // 访问根节点
  console.log(root.val);
  // 递归挨个遍历子节点
  root.children.forEach(dfs);
};
dfs(tree);

广度优先遍历: 将他看成先看封面再看目录，再去看文章

let bfs = root => {
  // 根节点入队
  let q = [root];
  while (q.length > 0) {
    // 队头出队 并访问
    const n = q.shift();
    console.log(n.val);
    // 队头children挨个入队
    n.children.forEach(child => {
      q.push(child);
    });
  }
};

先中后序遍历