数据结构与算法

链表

数组与链表

数组是连续的存储空间，链表是通过 next 指针连接，内存空间不连续。

数组：查找快 o(1)，修改慢 o(n)，增删非收尾元素需要移动元素

链表：查找慢 o(n)，修改快 o(1)，增删非首尾元素，只需要更改 next 的指向即可

使用 Object 模拟链表

将一个数组旋转 k 步

function rotate(arr: number[], step: number): number[] {
  let cut = arr.splice(-step)
  console.log(arr)
  return cut.concat(arr)
}

用 JS 实现快速排序，并说明时间复杂度

判断字符串是否括号匹配

function isValid(s) {
  // 如果为奇数，直接返回false
  if (s.length & 1 === 1) return false
  const stack = []
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    if ('({['.includes(c)) {
      stack.push(c)
    } else {
      const t = stack[stack.length - 1]
      if (c === ')' && t === '(' || c === ']' && t === '[' || c === '}' && t === '{') {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

反转单向链表

interface ILinkListNode {
  value: number
  next?: ILinkListNode
}

function createLinkList(arr: number[]): ILinkListNode {
  const length = arr.length
  if (length == 0) throw new Error('arr is empty')
  let curNode: ILinkListNode = {
    value: arr[arr.length - 1],
  }
  if (length === 1) return curNode

  for (let i = length - 2; i >= 0; i--) {
    curNode = {
      value: arr[i],
      next: curNode,
    }
  }
  return curNode
}
function reverseList(list: ILinkListNode): ILinkListNode {
  let p1 = null
  let p2: any = list
  while (p2) {
    const next = p2.next
    p2.next = p1
    p1 = p2
    p2 = next
  }
  return p1
}
const arr = [1, 2, 3, 4, 6]
console.log(reverseList(createLinkList(arr)))

链表和数组，那个实现队列更快？

队列：逻辑结构
数组：连续存储，push很快，shift很慢
链表：非连续存储，add和delete很快，查找很慢
结论：链表实现队列更快

链表实现队列
1.单向链表，但要同时记录head和tail
2.要从tail入队，从head出队
3.实时记录length，不可遍历链表获取

class quene {
  len = 0
  tail = null
  head = null

  add(item) {
    const newNode = {
      value: item,
      next: null
    }
    if (!this.head) {
      this.head = newNode
    }

    const tailNode = this.tail
    if (tailNode) {
      tailNode.next = newNode
    }
    this.tail = newNode
    this.len++
  }

  delete() {
    const headNode = this.head
    if (!headNode) return
    if (this.len <= 0) return
    headNode = headNode.next
    this.len--
  }

  get length() {
    return this.len
  }
}

用 js 实现二分查找，并说明时间复杂度

思路：递归
非递归：性能好
O(logn)

function binarySearch1(arr, target) {
  const length = arr.length
  if (arr.length === 0) return -1
  let startIndex = 0
  let endIndex = length - 1

  while (startIndex <= endIndex) {
    // const midIndex = Math.floor(startIndex + endIndex / 2)
    let midIndex = (startIndex + endIndex) >>> 1
    let midValue = arr[midIndex]
    if (target < midValue) {
      endIndex = midIndex - 1
    } else if (target > midValue) {
      startIndex = midIndex + 1
    } else {
      return midIndex
    }
  }
  return -1
}

给一个数组，找出其中和为 n 的两个元素

function getElement(arr, target) {
  const bucket = new Map()
  for (let i = 0; i < arr.length; i++) {
    const res = target - arr[i]
    if (res >= target) return -1
    if (bucket.has(res)) {
      return [bucket.get(res), i]
    } else {
      bucket.set(arr[i], i)
    }
  }
}

求一个二叉搜索树的第 k 小值

二叉树的遍历
前序遍历：root left right
中序遍历：left root right
后序遍历：left right root
BST
left (包括其后代)value <= root value
right(包括其后代)value >= root value

为什么二叉树如此重要，而不是三叉树、四叉树？

二分
二叉树 查找快 增删快
BST如果不平衡，就变成链表 O(logn) => O(n)
所以少尽量平衡 平衡二叉搜索树BBST 增删改查都是O(logn) 大概等于数的高度
红黑树 一种自平衡二叉树 分为红黑两种颜色，通过颜色转换来维持树的平衡

堆栈模型

JS执行时 值类型变量存储在栈 引用类型变量存储在堆

堆：完全二叉树
最大堆：父节点>=子节点
最小堆：父节点<=子节点 (满足其一即可)
逻辑结构vs物理结构
堆，逻辑上是一棵二叉树，物理结构是一个数组(连续空间，节省空间)
堆 VS BST
查询比BST慢
删除比BST快，维持平衡更快 总体上都是O(logn) 树的高度

青蛙跳台阶

一只青蛙，一次可跳1级，也可以跳2级
问：青蛙跳到n级台阶，总共有多少种方式
斐波那契
function fib(n) {
  if (n <= 0) return 0
  if (n === 1) return 1
  let n1 = 1 // 记录n-1的结果
  let n2 = 0 // 记录n-2的结果
  let res = 0

  for (let i = 0; i <= n; i++) {
    res = n1 + n2
    n2 = n1
    n1 = res
  }
  return res
}

将一个数组中的 0 移动到末尾

在原数组进行操作
function toTail(arr) {
  const length = arr.length
  if (length === 0) return
  // p1 指向第一个0， p2指向p1后第一个非0
  let p1 = -1
  let p2
  for (let i = 0; i < length; i++) {
    if (arr[i] === 0) {
      if (p1 < 0) {
        p1 = i
      }
    }
    if (arr[i] !== 0 && p1 >= 0) {
      p2 = i
      arr[p1] ^= arr[p2]
      arr[p2] ^= arr[p1]
      arr[p1] ^= arr[p2]
      p1++
    }
    if (p2 === length) return
  }

  return arr
}

求字符串中连续最多的字符，以及次数

function queryStr(str) {
  const res = {
    char: '',
    length: 0
  }
  if (str.length === 0) return res
  const length = str.length
  let compLength = 0
  for (let i = 0; i < length; i++) {
    compLength = 0

    for (let j = i; j < length; j++) {
      if (str[i] === str[j]) {
        compLength++
      }
      if (str[i] !== str[j] || j === length - 1) {
        if (compLength > res.length) {
          res.char = str[i]
          res.length = compLength
        }
        // 跳步
        if (i < length - 1) {
          i = j - 1
        }
        break
      }
    }
  }
  return res
}