JavaScript数据结构与算法(leetcode)
@ 姜波 | 星期三,八月 12 日,2020 年 | 8 分钟阅读 | 更新于 星期三,八月 12 日,2020 年

基础算法

字符串

  • 557 反转字符串中的单词 III
(str) => {
  // 字符串按空格进行分隔,保存数组,数组的元素的先后顺序就是单词的顺序
  // 对数组进行遍历,然后每个元素进行反转
  return str.split(' ').map(item => {
    return item.split('').reverse().join('')
  }).join(' ')
}

// 另一种思路
(str) => {
  return str.match(/[\w']+/g).map(item => {
    return item.split('').reverse().join('')
  }).join(' ')
}
  • 696 计数二进制子串
(str) => {
  // 建立数据结构,堆栈,保存数据
  let r = []
  // 给定任意子输入都返回第一个符合条件的子串
  let match = () => {
    let j = str.match(/^(0+|1+)/)[0]
    let o = (j[0]^1).toString().repeat(j.length)
    let reg = new RegExp(`^(${j}${o})`)
    if(reg.test(str)){
      return RegExp.$1
    }else{
      return ''
    }
  }
  // 通过for循环控制程序运行的流程
  for(let i = 0; len = str.length - 1; i < len; i++) {
    let sub = match(str.slice(i))
    if(sub){
      r.push(sub)
    }
  }
  return r
}

数组

  • 17 电话号码的字母组合(公式运算)
(str) => {
  // 建立电话号码键盘映射
  let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  // 把输入字符串按单字符分隔变成数组,234->[2,3,4]
  let num = str.split('')
  // 保存键盘映射后的字母内容,23->['abc','def']
  let code = []
  num.forEach(item => {
    if(map[item]){
      code.push(map[item])
    }
  })
  let comb = (arr) => {
		// 临时变量用来保存前两个组合的结果
    let tmp = []
    // 最外层的循环是遍历第一个元素,里层的循环是遍历第二个元素
    for(let i = 0, il = arr[0].length; i < il; i++){
      for(let j = 0, jl = arr[1].length; j < jl; j++){
        tmp.push(`${arr[0][i]}${arr[1][j]}`)
      }
    }
    arr.splice(0, 2, tmp)
    if(arr.length > 1){
      comb(arr)
    }else{
      return tmp
    }
    return arr[0]
  }
  return comb(code)
}
  • 914 卡牌分组(归类运算)
(arr) => {
  // 对这副牌进行排序,升序、降序都可以
  arr.sort((a, b) => a - b)
  let min = Number.MAX_SAFE_INTEGER
  let dst = []
  let result = true
  for(let i = 0, len = arr.length, tmp = []; i < len; i++) {
    tmp.push(arr[i])
    for(let j = i + 1; j < len - 1; j++){
      if(arr[i] === arr[j]){
        tmp.push(arr[j])
      }else{
        if(min > tmp.length){
          min = tmp.length
        }
        dst.push([].concat(tmp))
        tmp.length = 0
        i = j
        break
      }
    }
  }
  dst.every(item => {
    if(item.lenght % min != 0){
      result = false
      return false
    }
  })
  return result
}
  • 605 种花问题(筛选运算)
(arr, n) => {
  // 计数器
  let max = 0
  for(let i = 0, len = arr.length - 1; i < len; i++) {
    if(arr[i] === 0){
      if(i === 0 && arr[1] === 0){
        max++
      }else if(arr[i - 1] === 0 && arr[i + 1] === 0){
        max++
        i++
      }
    }
  }
  return max >= n
}
  • 89 格雷编码(二进制运算)
(n) => {
  // 递归函数,用来算输入为n的格雷编码序列
  let make = (n) => {
    if(n === 1){
      return ['0', '1']
    }else{
    	let prev = make(n - 1)
      let result = []
      let max = Math.pow(2, n) - 1
      for(let i = 0, len = prev.length; i < len; i++) {
        result[i] = `0${prev[i]}`
        result[max-i] = `1${prev[i]}`
      }
      return result
    }
  }
  return make(n)
}

正则

  • 459 重复的子字符串
(str) => {
  var reg = /^(\w+)\1+$/
  return reg.test(str)
}
  • 10 正则表达式匹配
(str, mode) => {
  // 对模式变量进行正则筛选
  let modeArr = mode.match(/([a-z.]\*)|([a-z]+(?=([a-z.]\*)|$))/g)
  let cur = 0
  let strLen = str.length
  for(let i = 0, len = modeArr.length, m; i < len; i++) {
    // 对于模式分为三类。 .*|a*|cdef
    m = modeArr[i].split('')
    // 如果第二位是*表示是有模式的
    if(m[1] === '*'){
      if(m[0] === '.'){
        cur = strLen
        break
      }else{
        while(str[cur] === m[0]){
          cur++
        }
      }
    }else{
      for(let j = 0, jl = m.length; j < jl; j++) {
        if(m[j] !== str[cur]){
          return false
        }else{
          cur++
        }
      }
    }
  }
  return cur === strLen
}

排序

  • 冒泡排序
(arr) => {
	// 冒泡排序
  for(let i = arr.length - 1, tmp; i > 0; i--) {
    for(let j = 0; j < i; j++) {
      tmp = arr[j]
      if(tmp > arr[j+1]){
        arr[j] = arr[j+1]
        arr[j+1] = tmp
      }
    }
  }
  return arr
}
  • 选择排序
(arr) => {
  // 选择排序
  for(let i = 0, len = arr.length, min; i < len; i++) {
    min = arr[i]
    for(let j = i + 1; j < len; j++) {
      if(arr[j] < min){
        let c = min
        min = arr[j]
        arr[j] = c
      }
    }
    arr[i] = min
  }
  return arr
}
  • 922 按奇偶排序数组 II
(arr) => {
  // 进行降序排序
  arr.sort((a, b) => a - b)
  // 声明一个空数组用来存储奇偶排序后的数组
  let r = []
  // 记录奇数,偶数位下标
  let odd = 1
  let even = 0
  // 对数组进行遍历
  arr.forEach(item => {
    if(item % 2 == 1){
      r[odd] = item
      odd += 2
    }else{
      r[even] = item
      even += 2
    }
  })
  return r
}
  • 215 数组中的第K个最大元素
(arr, k) => {
  let len = arr.length - 1
  // 冒泡排序
  for(let i = len, tmp; i > len - k; i--) {
    for(let j = 0; j < i; j++) {
      tmp = arr[j]
      if(tmp > arr[j+1]){
        arr[j] = arr[j+1]
        arr[j+1] = tmp
      }
    }
  }
  return arr[len - (k - 1)]
}
  • 164 最大间距
(arr) => {
  if(arr.length < 2){
    return 0
  }
  let max = 0
  let len = arr.length - 1
  let space
	// 冒泡排序
  for(let i = len, tmp; i > 0; i--) {
    for(let j = 0; j < i; j++) {
      tmp = arr[j]
      if(tmp > arr[j+1]){
        arr[j] = arr[j+1]
        arr[j+1] = tmp
      }
    }
    if(i < len){
      space = arr[i + 1] - arr[i]
      if(space > max){
        max = space
      }
    }
  }
  return Math.max(max, arr[1] - arr[0])
}
  • 41 缺失的第一个正数
(arr) => {
  // 过滤掉非正整数
  arr = arr.filter(item => item > 0)
  // 实现选择排序,先拿到最小值,如果第一个元素不是1直接返回1
  // 如果是1,就比较相邻元素差值是否大于1
  // 是说明当前元素+1就是
  for(let i = 0, len = arr.length, min; i < len; i++) {
    min = arr[i]
    for(let j = i + 1; j < len; j++) {
      if(arr[j] < min){
        let c = min
        min = arr[j]
        arr[j] = c
      }
    }
    arr[i] = min
    if(i > 0){
      if(arr[i] - arr[i - 1] > 1){
        return arr[i - 1] + 1
      }
    }else{
      if(min !== 1){
        return 1
      }
    }
  }
  return arr.length ? arr.pop() + 1 : 1
}

递归

  • 93 复原IP地址
(str) => {
    if(str.length > 12) return []
  // 保存所有符合条件的IP地址
  let r = []
  // 分四步递归处理ip分段
  let search = (cur, sub) => {
    // 边界条件
    if (cur.length === 4 && cur.join('') === str) {
        //  过滤 001 010等情况 
        if(cur[3].length > 1 && cur[3][0] == 0){
            return false
        }
      r.push(cur.join('.'))
    } else {
      // 正常的处理过程
      for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
        tmp = sub.substr(0, i + 1)
        //  过滤 001 010等情况           
        if (tmp.length > 1 && tmp[0] == 0) {
            return false
        }
        if (tmp < 256) {
          search(cur.concat([tmp]), sub.substr(i + 1))
        }
      }
    }
  }
  search([], str)
  return r
}

数据结构

  • 682 棒球比赛
(arr) => {
	// 用数组来实现堆栈结构,pop、push
  let result = []
  // 上一轮的数据
  let pre1
  // 上上轮的数据
  let pre2
  // 对数组进行遍历,遍历的目的是处理得分
  arr.forEach(item => {
    switch(item) {
      case 'C':
        if(result.length){
          result.pop()
        }
        break
      case 'D':
        pre1 = result.pop()
        result.push(pre1, pre1 * 2)
        break
      case '+':
        pre1 = result.pop()
        pre2 = result.pop()
        result.push(pre2, pre1, pre2 + pre1)
        break
      default:
        result.push(item * 1)
    }
  })
  return result.reduce((total, num) => { return total + num })
}
  • 85 最大矩形
(arr) => {
  let result = []
  let reg = /1{2,}/g
  // 把二维数组中相邻1提取出来
  arr.map(item => {
    let str = item.join('')
    let r = reg.exec(str)
    let rs = []
    while(r) {
      rs.push([r.index, r.index + r[0].length - 1])
      r = reg.exec(str)
    }
    return rs
  })
  // 通过递归计算相邻的矩阵
  let maxRect = (arr, result, n = 1) => {
    // 弹出第一行
    let top = arr.pop()
    // 弹出第二行
    let next = arr.pop()
    // 记录第一行的每一个起始点和截止点
    let tt
    // 记录第二行的每一个起始点和截止点
    let nn
    // 记录交叉的起始索引
    let start
    // 记录交叉的截止索引
    let end
    let width = 1
    let maxWidth = 1
    n++
    for(let i = 0, il = top.length; i < il; i++) {
      tt = top[i]
      for(let j = 0, jl = next.length; j < jl; j++) {
        nn = next[j]
        width = Math.min(tt[1], nn[1]) - Math.max(tt[0], nn[0])
        if(width > maxWidth){
          maxWidth = width
          start = Math.max(tt[0], nn[0])
          end = Math.min(tt[1], nn[1])
        }
      }
    }
    // 如果没有找到交叉点
    if(start === undefined || end === undefined){
      if(n < 3){
        return false
      }else{
        width = top[0][1] - top[0][0] + 1
        if(width > 1){
          result.push((n - 1) * width)
        }
      }
    }else{
      arr.push([[start, end]])
      maxRect(arr, result, n++)
    }
  }
  while(arr.length > 1) {
    maxRect([].concat(arr), result)
    arr.pop()
  }
  // 取最大值
  let max = 0
  let item = result.pop()
  while(item) {
    if(item > max){
      max = item
    }
    item = result.pop()
  }
  return max > 0 ? max : -1
}

队列

  • 622 设计循环队列
class MyCircularQueue {
  constructor(k) {
    // 用来保存数据长度为k的数据结构
    this.list = Array(k)
    // 队首指针
    this.front = 0
    // 队尾指针
    this.rear = 0
    // 队列长度
    this.max = k
  }
  enQueue(num) {
    if(this.isFull()){
      return false
    }else{
      this.list[this.rear] = num
      this.rear = (this.rear + 1) % this.max
      return true
    }
  }
  deQueue() {
    let v = this.list[this.front]
    this.list[this.front] = ''
    this.front = (this.front + 1) % this.max
    return v
  }
  isEmpty() {
    return this.front === this.rear && !this.list[this.front]
  }
  isFull() {
		return this.front === this.rear && !!this.list[this.front]   
  }
  Front() {
    return this.list[this.front]
  }
  Rear() {
    let rear = this.rear - 1
    return this.list[rear < 0 ? this.max - 1 : rear]
  }
}
  • 621 任务调度器
(tasks, n) => {
  // 表示最终队列执行的结果
  let q = ''
  // 对归类进行存储
  let Q = {}
  tasks.forEach(item => {
    if(Q[item]){
      Q[item]++
    }else{
      Q[item] = 1
    }
  })
  while(1) {
    // 任务清单
    let keys = Object.keys(Q)
    if(!keys[0]){
      break
    }
    // 声明一个队列用来存储1+n任务单元
    let tmp = []
    for(let i = 0; i <= n; i++) {
			let max = 0
      let key
      let pos
      keys.forEach((item, idx) => {
        if(Q[item] > max){
          max = Q[item]
          key = item
          pos = idx
        }
      })
      if(key){
        tmp.push(key)
        keys.splice(pos, 1)
        Q[key]--
        if(Q[key] < 1){
          delete Q[key]
        }
      }else{
        break
      }
    }
    q += tmp.join('').padEnd(n + 1, '-')
  }
  // 边界处理,最后不处理冷却时间
  q = q.replace(/-+$/g, '')
  return q.length
}

链表

  • 148 排序链表
// 声明链表的节点
class Node {
  constructor(value) {
    this.val = value
    this.next = undefined
  }
}
// 声明链表的数据结构
class NodeList {
  constructor(arr) {
    // 声明链表的头部节点
    let head = new Node(arr.shift())
    let next = head
    arr.forEach(item => {
      next.next = new Node(item)
      next = next.next
    })
    return head
  }
}
// 交换两个节点的值
let swap = (p, q) => {
  let val = p.val
  p.val = q.val
  q.val = val
}
// 寻找基准元素的节点
let partion = (begin, end) => {
  let val = begin.val
  let p = begin
  let q = begin.next
  while(q !== end) {
    if(q.val < val){
      p = p.next
      swap(p, q)
    }
    q = q.next
  }
  // 将基准元素换到中间
  swap(p, begin)
  return p
}

function sort(begin, end) {
  if(begin !== end){
    let part = partion(begin, end)
    sort(begin, part)
    sort(part.next, end)
  }
}
  • 141 环形链表
(head) => {
    let fast = head;
    let slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}

矩阵

  • 54 螺旋矩阵
(arr) => {
  // 处理每一圈的数据遍历过程
  let map = (arr, r = []) => {
    for(let i = 0; len = arr.length; i < len; i++) {
      if(i === 0){
        r = r.concat(arr[i])
      }else if(i === len -1){
        r = r.concat(arr[i].reverse())
      }else{
        r.push(arr[i].pop())
      }
    }
    arr.shift()
    arr.pop()
    for(let i = arr.length - 1; i >= 0; i--) {
      r.push(arr[i].shift())
    }
    if(arr.length){
      return map(arr, r)
    }else{
      return r
    }
  }
  return map(arr, [])
}
  • 48 旋转图像
(arr) => {
  // 获取n的维度
  let vecor = arr.length
  // 垂直旋转
  for(let i = 0, len = vecor / 2; i < len; i++) {
		for(let j = 0, tmp; j < vecor; j++) {
      tmp = arr[i][j]
      arr[i][j] = arr[vecor - i - 1][j]
      arr[vecor - i - 1][j] = tmp
    }
  }
  // 对角线翻转
  for(let i = 0; i < vecor; i++) {
    for(let j = 0, tmp; j < i; j++) {
      tmp = arr[i][j]
      arr[i][j] = arr[j][i]
      arr[j][i] = tmp
    }
  }
  return arr
}

二叉树

  • 101 对称二叉树
// 二叉树的节点
class Node {
  constructor(val) {
    this.val = val
    this.left = this.right = undefined
  }
}
class Tree {
  constructor(data) {
    // 临时存储所有节点,方便寻找父子节点
    let nodeList = []
    let root
    for(let i = 0; len = data.length; i < len; i++) {
      let node = new Node(data[i])
      nodeList.push(node)
      if(i > 0){
        // 计算当前节点属于哪一层
        let n = Math.floor(Math.sqrt(i + 1))
        // 记录当前层的起始点
        let q = Math.pow(2, n) - 1
        // 记录上一层的起始点
        let p = Math.pow(2, n - 1) -1
        // 找到当前节点的父节点
        let parent = nodeList[p + Math.floor((i - q) / 2)]
        // 将当前节点和上一层的父节点做关联
        if(parent.left){
          parent.right = node
        }else{
          parent.left = node
        }
      }
    }
    root = nodeList.shift()
    nodeList.length = 0
    return root
  }
  static isSymmetry(root) {
    if(!root){
      return true
    }
    let walk = (left, right) => {
      if(!left && !right){
        return true
      }
      if((left && !right) || (!left && right) || (left.val !== right.val)){
        return false
      }
      return walk(left.left, right.right) && walk(left.right, right.left)
    }
    return walk(root.left, root.right)
  }
}
  • 98 验证二叉搜索树
class Node {
  constructor(val) {
    this.val = val
    this.left = this.right = undefined
  }
}
class Tree {
  constructor(data) {
    let root = new Node(data.shift())
    // 遍历所有的数据,逐渐插入到当前搜索树中去
    data.forEach(item => {
      this.insert(root, item)
    })
    return root
  }
  insert(node, data) {
    if(node.val > data){
      if(node.left === undefined){
        node.left = new Node(data)
      }else{
        this.insert(node.left, data)
      }
    }else{
      if(node.right === undefined){
        node.right = new Node(data)
      }else{
        this.insert(node.right, data)
      }
    }
  }
  static walk(root) {
    if(!root.left && !root.right){
      return true
    }else if((root.left && root.val < root.left.val) || (root.right && root.val > root.right.val)){
      return false
    }else{
      return Tree.walk(root.left) && Tree.walk(root.right)
    }
  }
}

  • 451 根据字符出现频率排序
class Heap {
  constructor(str) {
    let map = new Map()
    str.split('').forEach(item => {
      if(map.has(item)){
        map.set(item, map.get(item) + 1)
      }else{
        map.set(item, 1)
      }
    })
    this.map = map
    this.data = Array.from(map.values())
  }
  sort() {
    let iArr = this.data
    let n = iArr.length
    if(n <= 1){
      return iArr
    }else{
      for(let i = Math.floor(n / 2); i >= 0; i--) {
        Heap.maxHeapify(iArr, i, n)
      }
      for(let j = 0; j < n; j++) {
        Heap.swap(iArr, 0, n - 1 -j)
        Heap.maxHeapify(iArr, 0, n - 1 - j - 1)
      }
      return iArr
    }
  }
  toString() {
    let arr = this.sort()
    let str = []
    while(arr.length) {
      let top = arr.pop()
      for(let [k,v] of this.map) {
        if(v === top){
          str.push(k.repeat(v))
          this.map.delete(k)
          break
        }
      }
    }
    return str.join('')
  }
  // 交换两个元素
  static swap(arr, a, b) {
    if(a === b){
      return ''
    }
    let c = arr[a]
    arr[a] = arr[b]
    arr[b] = c
  }
  // 构建最大堆
  static maxHeapify(Arr, i, size) {
    // 左节点
    let l = i * 2 + 1
    // 右节点
    let r = i * 2 + 2
    let largest = i
    // 父节点i和左节点l做比较取最大
    if(l <= size && Arr[l] > Arr[largest]){
      largest = l
    }
    // 右节点和最大值比较
    if(r <= size && Arr[r] > Arr[largest]){
      largest = r
    }
    if(largest !== i){
      Heap.swap(Arr, i, largest)
      Heap.maxHeapify(Arr, largest, size)
    }
  }
}

进阶算法

贪心算法

  • 122 买卖股票的最佳时机 II
(prices) => {
  // 用来保存利润
	let count = 0
  for(let i = 0; len = prices.length; i < len; i++) {
    for(let j = i; j < len - 1; j++) {
      if(prices[j + 1] > prices[j]){
        count += prices[j + 1] - prices[j]
        i = j
      }else{
        i = j
        break
      }
    }
  }
  return count
}
  • 860 柠檬水找零
(input) => {
  // 用于存储零钱
  let hand = []
  // 判断是否有顾客还在
  while(input.length) {
    // 取出当前排在最前面的钱
    let money = input.shift()
    // 无需找零
    if(money === 5){
      hand.push(money)
    }else{
      // 降序排列
      hand.sort((a, b) => b - a)
      // 需找零
      let change = money - 5
      for(let i = 0, len = hand.length; i < len; i++) {
        if(hand[i] <= change){
          change -= hand[i]
          hand.splice(i, 1)
          i--
        }
        if(change === 0){
          break
        }
      }
      // 零钱不够
      if(change !== 0){
        return false
      }else{
        hand.push(money)
      }
    }
  }
  return true
}

动态规划

  • 63 不同路径 II
(arr, m, n) => {
  let dp = (m, n) => {
    if(m === 2 && n === 2){
      return (arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2) ? 0 : (arr[1][0] === 1 || arr[0][1] === 1) ? 1 : 2
    }else if(m < 2 || n < 2){
      if(m < 2){
        // 单行
        return arr[m - 1].includes(1) ? 0 : 1
      }else{
        // 单列
        for(let i = 0; i < m; i++) {
          if(arr[i][0] === 1){
            return 0
          }
        }
        return 1
      }
    }else{
      return dp(m - 1, n) + dp(m, n - 1)
    }   
  }
  return dp(m, n)
}
  • 787 K站中转内最便宜的航班
(src, dst, k) => {
  let fights = [
    [0, 1, 100],
    [1, 2, 100],
    [0, 2, 500]
  ]
  let cheap = (src, dst, k) => {
    // 找到dst的前一站
    let prev = 	fights.filter(item => item[1] === dst)
    let min = Math.min.apply(null, prev.map(item => {
      // 从dst往前找,找到了起始城市
      if(item[0] === src && k > -1){
        return item[2]
      }else if(k === 0 && item[0] !== src){
        return Number.MAX_SAFE_INTEGER
      }else{
        return item[2] + cheap(src, item[0], k - 1)
      }
    }))
    return min
  }
  return cheap(src, dst, k) || -1
}

公众号

Image text

QQ

Image text

微信

Image text

微信打赏

Image text

社交链接