1. 概述

程序是由于数据结构和算法组成的。好的算法可以让代码化繁为简,也可以提升代码运行效率,所以目前很多公司的面试都会考虑算法。

2. 栈

栈是基础的数据结构,是一种遵从后进先出原则的有序集合。只能从栈顶添加或者移除。通过原生js实现一个栈。

class Stack {
  constructor () {
    // 存储栈的数据
    this.data = {}
    // 记录栈的数据个数(相当于数组的 length)
    this.count = 0
  }
  // push() 入栈方法
  push (item) {
    // 方式1:数组方法 push 添加,但并不好,额外引入了数组的属性
    // this.data.push(item)
    // 方式2:利用数组长度,性能比push好,但也是数组的能力
    // this.data[this.data.length] = item
    // 方式3:计数方式
    this.data[this.count] = item
    // 入栈后,count 自增
    this.count++
  }
  // pop() 出栈方法
  pop () {
    // 出栈的前提是栈中存在元素,应先行检测
    if (this.isEmpty()) {
      console.log('栈为空!')
      return
    }
    // 移除栈顶数据
    // 方式1:数组方法 pop 移除
    // return this.data.pop()
    // 方式2:计数方式
    const temp = this.data[this.count - 1]
    delete this.data[--this.count]
    return temp
  }
  // isEmpty() 检测栈是否为空
  isEmpty () {
    return this.count === 0
  }
  // top() 用于获取栈顶值
  top () {
    if (this.isEmpty()) {
      console.log('栈为空!')
      return
    }
    return this.data[this.count - 1]
  }
  // size() 获取元素个数
  size () {
    return this.count
  }
  // clear() 清空栈
  clear () {
    this.data = []
    this.count = 0
  }
}

const s = new Stack()
s.push('a')
s.push('b')
s.push('c')

这里栈的datacount应该是确保不会被修改的,一旦被修改数据就乱了,可以将属性设置为私有,让外部无法访问。

1. 包含min函数的栈

就是通过一个函数找到栈中的最小值。

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数在该栈中,调用minpushpop的时间复杂度都是O(1)。常数的时间复杂度,不会因为数据量增加而增加。

// 在存储数据的栈外,再新建一个栈,用于存储最小值
class MinStack {
  constructor () {
    // stackA 用于存储数据
    this.stackA = []
    this.countA = 0
    // stackB 用于将数据降序存储(栈顶值为最小值)
    this.stackB = []
    this.countB = 0
  }
  // 入栈
  push (item) {
    // stackA 正常入栈
    this.stackA[this.countA++] = item
    // stackB 如果没有数据,直接入栈
    // 如果 item 的值 <= stackB 的最小值,入栈
    if (this.countB === 0 || item <= this.min()) {
      this.stackB[this.countB++] = item
    }
  }
  // 最小值函数
  min () {
    return this.stackB[this.countB - 1]
  }
  // 获取栈顶值
  top () {
    return this.stackA[this.countA - 1]
  }
  // 出栈
  pop () {
    // 先进行 stackB 的检测
    // 如果 stackA 的栈顶值 === stackB 的栈顶值,stackB 出栈
    if (this.top() === this.min()) {
      delete this.stackB[--this.countB]
    }
    // stackA 出栈
    delete this.stackA[--this.countA]
  }
}

const m = new MinStack()

还可以利用内置的方法来实现,编写起来非常简单,只不过执行效率上就会有所降低。

class MinStack {
  constructor () {
    this.stack = []
  }
  // 入栈
  push (item) {
    this.stack.push(item)
  }
  // 查看栈顶值
  top () {
    return this.stack[this.stack.length - 1]
  }
  // 实现最小值功能
  min () {
    return Math.min.apply(null, this.stack)
  }
  // 出栈方法
  pop () {
    return this.stack.pop()
  }
}

const m = new MinStack()

2. 每日温度案例

根据每日气温列表,重新生成一个列表,对应位置的输出为,想要观测到更多的气温,至少需要等待的天数,如果气温在这之后都不会升高,该位置用0来代替。

例如给定一个列表[73, 74, 75, 71, 69, 72, 76, 73]输出的应该是[1, 1, 4, 2, 1, 1, 0, 0]

如果采用循环的方式会重复很多次,效率就比较低了,可以利用栈的数据结构简书数据操作次数,减少时间复杂度。

让栈存储递减的规律,每找到一个数据就将它与栈顶值比较,如果比栈顶值小就放在栈中,形成一个递减的栈,如果这个值比栈顶的值大将栈顶值出栈,也就是找到了比他更大的温度。可以将当前的位置与栈顶位置做差,差就是升温等待的天数了。

/**
 * @param {number[]} T 每日温度数组 [73, 74, 75, 71, 69, 72, 76, 73]
 * @return {number[]} 等待天数列表 [1, 1, 4, 2, 1, 1, 0, 0]
 */
var dailyTemperatures = function(T) {
  // 创建单调栈用于记录(存储索引值,用于记录天数)
  const stack = [0]
  let count = 1

  // 创建结果数组(默认将结果数组使用 0 填充)
  const len = T.length
  const arr = new Array(len).fill(0)

  // 遍历 T
  for (let i = 1; i < len; i++) {
    let temp = T[i]
    // 使用 temp 比较栈顶值,如果栈顶值小,出栈(计算日期差,并存储),并重复操作
    //  - stack[count - 1] 代表栈顶值
    while (count && temp > T[stack[count - 1]]) {
      // 出栈
      let index = stack.pop()
      count--
      // 计算 index 与 i 的差,作为 index 位置的升温日期的天数使用 
      arr[index] = i - index
    }
    // 处理完毕,当前温度入栈(等待找到后续的更大温度)
    stack.push(i)
    count++
  }
  return arr
}

3. 队列

队列是一种遵从先进先出原则的有序集合,添加新元素的一端叫做队尾,另一端称为对首。

1. 基于数组的队列实现

出队enqueue和入队dequeue核心功能,top获取队首的值,size获取队列元素个数,clear清空队列。

delete删除的时候数据会删除掉,但是位置还是在的。

class Queue {
  constructor () {
    // 用于存储队列数据
    this.queue = []
    this.count = 0
  }
  // 入队方法
  enQueue (item) {
    this.queue[this.count++] = item
  }
  // 出队方法
  deQueue () {
    if (this.isEmpty()) {
      return
    }
    // 删除 queue 的第一个元素
    // delete this.queue[0]
    // 利用 shift() 移除数组的第一个元素
    this.count--
    return this.queue.shift()
  }
  isEmpty () {
    return this.count === 0
  }
  // 获取队首元素值
  top () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[0]
  }
  size () {
    return this.count
  }
  clear () {
    // this.queue = []
    this.length = 0
    this.count = 0
  }
}

const q = new Queue()

2. 基于对象方式实现

对象是可以实现delete删除元素的,这一点要比数组好很多。

class Queue {
  constructor () {
    this.queue = {}
    this.count = 0
    // 用于记录队首的键
    this.head = 0
  }
  // 入队方法
  enQueue (item) {
    this.queue[this.count++] = item
  }
  // 出队方法
  deQueue () {
    if (this.isEmpty()) {
      return
    }
    const headData = this.queue[this.head]
    delete this.queue[this.head]
    this.head++
    this.count--
    return headData
  }
  isEmpty () {
    return this.count === 0
  }
  clear () {
    this.queue = {}
    this.count = 0
    this.head = 0
  }
}

const q = new Queue()

3. 双端队列

双端队列允许同时从队尾和队首两端进行存储操作的队列,操作更加灵活。首尾都可以添加和删除。

双端队列与js中的数组操作十分类似,只是不允许在数组中间位置进行存取,只能操作两端。

class Deque {
  constructor () {
    this.queue = {}
    this.count = 0
    this.head = 0
  }
  // 队首添加
  addFront (item) {
    this.queue[--this.head] = item
  }
  // 队尾添加
  addBack (item) {
    this.queue[this.count++] = item
  }
  // 队首删除
  removeFront () {
    if (this.isEmpty()) {
      return
    }
    const headData = this.queue[this.head]
    delete this.queue[this.head++]
    return headData
  }
  // 队尾删除
  removeBack () {
    if (this.isEmpty()) {
      return
    }
    const backData = this.queue[this.count - 1]
    delete this.queue[--this.count]
    // this.count-- 与 上一步 this.count - 1 合并
    return backData
  }
  // 获取队首值
  frontTop () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[this.head]
  }
  // 获取队尾值
  backTop () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[this.count - 1]
  }
  isEmpty () {
    return this.size() === 0
  }
  size () {
    return this.count - this.head
  }
}

const deq = new Deque()

4. 队列的最大值

定义一个队列并实现函数max_value得到队列里的最大值,要求函数max_value、push_back和pop_front的时间复杂度都是O(1)。时间复杂度是一个常数,而遍历是会跟长度相关的是O(n)所以不能通过这样的方式。

队列为空时返回值-1即可。

主要难点就是O1复杂度,可以通过双端队列进行数据存储,每次取到数据就去判断队列是否有值,如果没值就添加到队列中,否则就判断新值和之前值的关系,如果当前的值比队列最后的值小就存储,如果比队尾的值大,就将队尾的值出队,重复这种操作维持队列单调递减。这样队首就是最大值,队尾是最小值。

var MaxQueue = function() {
  // 存储队列数据
  this.queue = {}
  // 双端队列维护最大值(每个阶段的最大值)
  this.deque = {}
  // 准备队列相关的数据
  this.countQ = this.countD = this.headQ = this.headD = 0
};

/** 队尾入队
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
  // 数据在 queue 入队
  this.queue[this.countQ++] = value
  // 检测是否可以将数据添加到双端队列
  //   - 队列不能为空
  //   - value 大于队尾值
  while (!this.isEmptyDeque() && value > this.deque[this.countD - 1]) {
    // 删除当前队尾值
    delete this.deque[--this.countD]
  }
  // 将 value 入队
  this.deque[this.countD++] = value
};

/** 队首出队
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
  if (this.isEmptyQueue()) {
    return - 1
  }
  // 比较 deque 与 queue 的队首值,如果相同,deque 出队,否则 deque 不操作
  if (this.queue[this.headQ] === this.deque[this.headD]) {
    delete this.deque[this.headD++]
  }
  // 给 queue 出队,并返回
  const frontData = this.queue[this.headQ]
  delete this.queue[this.headQ++]
  return frontData
};

/** 获取队列最大值
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
  if (this.isEmptyDeque()) {
    return -1
  }
  // 返回 deque 队首值即可
  return this.deque[this.headD]
};

/** 检测队列 deque 是否为空
 * 
 */
MaxQueue.prototype.isEmptyDeque = function () {
  return !(this.countD - this.headD)
};

/** 检测队列 Queue 是否为空
 * 
 */
MaxQueue.prototype.isEmptyQueue = function () {
  return !(this.countQ - this.headQ)
};

5. 滑动窗口最大值

给你一个整数数组,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧,你只可以看到在滑动窗口内的k个数字,滑动窗口每次向右移动一位,返回滑动窗口中的最大值。

/**
 * @param {number[]} nums 传入数组
 * @param {number} k 滑动窗口宽度
 * @return {number[]} 
 */
var maxSlidingWindow = function(nums, k) {
  if (k <= 1) {
    return nums
  }
  const result = []
  const deque = []
  // 1 将窗口第一个位置的数据添加到 deque 中,保持递减
  deque.push(nums[0])
  let i = 1
  for (; i < k; i++) {
    // - 存在数据
    // - 当前数据大于队尾值
    //   - 出队,再重复比较
    while (deque.length && nums[i] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[i])
  }
  // 将第一个位置的最大值添加到 result
  result.push(deque[0])

  // 2 遍历后续的数据
  const len = nums.length
  for (; i < len; i++) {
    // 同上进行比较
    while (deque.length && nums[i] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[i])
    // 检测当前最大值是否位于窗口外
    if (deque[0] === nums[i - k]) {
      deque.shift()
    }
    // 添加最大值到 result
    result.push(deque[0])
  }

  return result
};

4. 链表

链表是有序的数据结构,类似链条,链表可以在首位以及中间任意位置进行操作,灵活度更高。链表中的元素在内存中不必是连续的。删除和添加不会其余元素位移。同时也无法根据索引快速定位。

数组在内存中需要占据一段连续的空间,同时数组在做添加,移除会导致后续元素位移,性能开销比较大。

获取修改元素时,数组效率高,添加删除时链表效率高。

1. 实现链表

要实现节点功能,value存储当前节点属性,next存储下一个节点的指针,这样就形成了关联。

可以通过addAtTail在尾部添加节点,addAthead在头部添加节点,addAtIndex在指定位置添加节点。get获取节点,removeAtIndex删
除指定节点。

要先定义节点类,然后基于节点类实现链表类。

// 节点类
class LinkedNode {
  constructor (value) {
    this.value = value
    // 用于存储下一个节点的引用
    this.next = null
  }
}

// 链表类
class LinkedList {
  constructor () {
    this.count = 0
    this.head = null
  }
  // 添加节点 (尾)
  addAtTail (value) {
    // 创建新节点
    const node = new LinkedNode(value)
    // 检测链表是否存在数据
    if (this.count === 0) {
      this.head = node
    } else {
      // 找到链表尾部节点,将最后一个节点的 next 设置为 node
      let cur = this.head
      while (cur.next != null) {
        cur = cur.next
      }
      cur.next = node
    }
    this.count++
  }
  // 添加节点(首)
  addAtHead (value) {
    const node = new LinkedNode(value)
    if (this.count === 0) {
      this.head = node
    } else {
      // 将 node 添加到 head 的前面
      node.next = this.head
      this.head = node
    }
    this.count++
  }
  // 获取节点(根据索引)
  get (index) {
    if (this.count === 0 || index < 0 || index >= this.count) {
      return
    }
    // 迭代链表,找到对应节点
    let current = this.head
    for (let i = 0; i < index; i++) {
      current = current.next
    }
    return current
  }
  // 添加节点(根据索引)
  addAtIndex (value, index) {
    if (this.count === 0 || index >= this.count) {
      return
    }
    // 如果 index <= 0,都添加到头部即可
    if (index <= 0) {
      return this.addAtHead(value)
    }
    // 后面为正常区间处理
    const prev = this.get(index - 1)
    const next = prev.next

    const node = new LinkedNode(value)
    prev.next = node
    node.next = next

    this.count++
  }
  // 删除(根据索引)
  removeAtIndex (index) {
    if (this.count === 0 || index < 0 || index >= this.count) {
      return
    }
    if (index === 0) {
      this.head = this.head.next
    } else {
      const prev = this.get(index - 1)
      prev.next = prev.next.next
    }
    this.count--
  }
}

// 测试代码
const l = new LinkedList()
l.addAtTail('a')
l.addAtTail('b')
l.addAtTail('c')

2. 双向链表

双向链表是在普通链表的基础上,增加一个用于记录上一个节点的属性的prev,可进行双向访问。这样每个节点就有三个属性,可以进行双向访问了。

3. 循环链表

循环链表又称为环形链表,指的是链表的最后一个节点的next指向第一个节点,形成首位相连的环形结构。

在实际使用中,环的结束点可以为链表的任意节点。

4. 反转链表

迭代方式

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  // 声明变量记录 prev、cur
  let prev = null
  let cur = head
  // 当 cur 是节点时,进行迭代
  while (cur) {
    // 先保存当前节点的下一个节点
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};

递归方式

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  if (head === null || head.next === null) {
    return head
  }
  const newHead = reverseList(head.next)
  // 能够第一次执行这里的节点为 倒数第二个 节点
  head.next.next = head
  // head 的 next 需要在下一次递归执行时设置。当前设置为 null 不影响
  //   - 可以让最后一次(1)的 next 设置为 null
  head.next = null
  return newHead
};

5. 环路检测

给定一个链表,如果是有环链表,返回环路的开头节点,如果链表中有某个节点,可以通过李先耐心追踪next指针再次到达,则链表中存在环,为了表示给定链表中的环,使用证书pos来表示链表尾链接到表中的位置。

如果pos是-1,则在该链表中没有环,pos不作为参数传递,仅仅是标识链表是实际情况。

其实就是环形链表,首先要判断是不是环形链表,

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if (head === null || head.next === null) {
      return null
    }
    // 声明快慢指针
    let slow = head
    let fast = head

    while (fast !== null) {
      // 慢每次指针移动一位
      slow = slow.next
      // 如果满足条件,说明 fast 为尾部结点,不存在环
      if (fast.next === null) {
        return null
      }
      // 快指针每次移动两位
      fast = fast.next.next

      // 检测是否有环
      if (fast === slow) {
        // 找到环的起点位置
        let ptr = head
        while (ptr !== slow) {
          ptr = ptr.next
          slow = slow.next
        }
        // ptr 和 slow 的交点就是环的起始节点
        return ptr
      }
    }
    // while 结束,说明 fast 为 null,说明链表没有环
    return null
};

5. 树与二叉树

树存在多个节点,每个节点又存在多个节点,树形结构存在层次关系,

树型结构是一种非线性的数据结构,树中的每个部分称为节点,节点间存在分支结构和层次关系。

每个树形结构都具有一个根节点,节点间具有父子兄弟关系。不含子节点的节点称为叶节点。子树是针对某个节点及该节点子孙节点的称呼。

数中最深节点的层级称为树的高度,

二叉树是树形结构中的一种,二叉树中的每个节点最多只能有两个子节点。称为左子节点和右子节点。子节点的树又称为左子树和右子树。

除叶子节点外每个节点都有两个子节点的树称为满二叉树。每层节点都达到最大值。

二叉树除最后一层,每层节点都达到最大值,且最后一层节点都位于左侧,叫做完全二叉树。

由于完全二叉树的结构连续,有迹可循,所以可以采用顺序存储方式。

普通二叉树由于结构不规则,不适合使用顺序存储,为了记录节点间的关系,可使用链式存储方式。每个节点通过value表示值,left,right表示左右子节点。

1. 二叉树遍历

根据访问顺序不同存在三种遍历形式,前序遍历,中序遍历,后序遍历。序表示根节点的访问顺序。

前序遍历: 根节点 > 左子树 -> 右子树

中序遍历: 左子树 -> 根节点 -> 右子树

后序遍历: 左子树 -> 右子树 -> 根节点

2. 前序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
/* var preorderTraversal = function(root) {
  // 用于存储遍历的结果
  const res = []
  // 设置函数用于进行递归遍历
  const preorder = (root) => {
    // 当前结点为空时,无需进行递归
    if (!root) {
      return
    }
    // 记录根节点值
    res.push(root.val)
    // 前序遍历左子树
    preorder(root.left)
    // 前序遍历右子树
    preorder(root.right)
  }
  preorder(root)
  return res
}; */

const preorderTraversal = function(root) {
  const res = []
  const stk = []
  while (root || stk.length) {
    while (root) {
      // 右子结点入栈
      stk.push(root.right)
      // 记录根节点
      res.push(root.val)
      // 下一步处理左子节点
      root = root.left
    }
    // 左子树处理完毕,将 stk 出栈,处理右子树
    root = stk.pop()
  }
  return res
}

3. 最大深度

给定一个二叉树,找出其最大深度,二叉树的深度为根节点到最远叶子节点的最长路径上的点数。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  if (!root) {
    return 0
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

4. 层序遍历

给定一个二叉树,返回层序遍历的节点值。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  const res = []
  if (!root) {
      return res
  }
  // 声明队列用于存储后续数据
  const q = []
  q.push(root)

  // 遍历队列
  while (q.length !== 0) {
      // 针对本轮操作,创建一个新的二维数组
      res.push([])
      let len = q.length
      for (let i = 0; i < len; i++) {
          // 将本次操作的结点出队
          const node = q.shift()
          res[res.length - 1].push(node.val)
          // 检测是否存在左右子结点,如果有,入队即可
          if (node.left) {
              q.push(node.left)
          }
          if (node.right) {
              q.push(node.right)
          }
      }
  }
  return res
};

5. 二叉搜索树

是一种特殊的二叉树形式,简称BST,左子树的节点小于根节点,右子树的节点大于根节点。子树也为二叉搜索树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
/* var isValidBST = function(root) {
  // 通过一个辅助函数来统一设置左右子树的比较
  return helper(root, -Infinity, Infinity);
};

const helper = (root, lower, upper) => {
  if (root === null) {
    return true
  }
    // 当前节点值超出边界,说明二叉树为非 BST
  if (root.val <= lower || root.val >= upper) {
    return false;
  }
  // 否则,递归处理左右子节点,并更新大小范围
  // 同时根据左右子节点的返回值进行返回,只有全部递归结果均为 true, 才说明二叉树为 BST
  return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
} */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  let stk = []
  // 用于记录上一次取得的节点值,BST 中这个值应小于当前节点
  // 设置默认值为 -Infinity 避免对比较结果产生干扰
  let oldNode = -Infinity

  while (root || stk.length) {
    while (root) {
      stk.push(root) 
      root = root.left
    }
    root = stk.pop()
    // 如果任意节点比上个节点值小,说明二叉树不是 BST
    if (root.val <= oldNode) {
      return false
    }
    // 通过比较,记录当前节点值
    oldNode = root.val
    root = root.right
  }
  return true
};

转载须知

如转载必须标明文章出处文章名称文章作者,格式如下:

转自:【致前端 - zhiqianduan.com】 数据结构与算法  "隐冬"
请输入评论...