1、数据结构与算法类题

1、括号匹配

https://leetcode.cn/problems/valid-parenthese

/**
 * 括号匹配
 */
function isMatch(left, right) {
  if (left === '(' && right === ')') return true
  if (left === '{' && right === '}') return true
  if (left === '[' && right === ']') return true
  return false
}
function matchBraket(str) {
  const len = str.length
  if (len === 0) return true
  const leftSymbol = '({['
  const rightSymbol = ']})'
  const stack = []
  for (let i = 0; i < len; i++) {
    const s = str[i]
    if (leftSymbol.includes(s)) {
      // 包含左括号，进栈
      stack.push(s)
    } else if (rightSymbol.includes(s)) {
      // 包含右括号，拿出栈顶元素和当前元素匹配对比，如果为true则出栈
      const top = stack[stack.length - 1]
      if (isMatch(top, s)) {
        stack.pop()
      }
    }
  }
  return stack.length === 0
}
console.log(matchBraket("{[()]}"))

2、两个栈实现一个队列

https://leetcode.cn/problems/implement-queue-using-stacks/

class MyQueue {
  constructor() {
    this.stack1 = []
    this.stack2 = []
  }
  /**
   * 入队
   */
  add(n) {
    this.stack1.push(n)
  }
  /**
   * 出队
   */
  delete() {
    // 1、讲stack1中的所有数据移动到stack中
    while (this.stack1.length) {
      const n = this.stack1.pop()
      if (n) {
        this.stack2.push(n)
      }
    }
    // 2、stack2.pop
    const res = this.stack2.pop()
    return res
  }
  length() {
    return this.stack2.length
  }
}
const res = new MyQueue()
res.add(1)
res.add(2)
res.add(3)
console.log(res.delete())
console.log(res.delete())

3、反转单向链表

/**
 * 创建链表
 * @param {*} arr 
 * @returns 
 */
function createLinkList(arr) {
  const len = arr.length
  if (!len) throw new Error('arr is empty')
  let curNode = {
    value: arr[len - 1]
  }
  if (len === 1) {
    return curNode
  }
  for (let i = len - 2; i >= 0; i--) {
    curNode = {
      value: arr[i],
      next: curNode
    }
  }
  return curNode
}
/**
 * 反转
 * @param {*} listNode 
 */
function reverseLinkList(listNode) {
  // 定义指针
  let prevNode = undefined
  let curNode = undefined
  let nextNode = listNode
  // 以nextNode为主，遍历链表
  while (nextNode) {
    // 第一个元素,删掉next,防止循环引用
    if (curNode && !prevNode) {
      delete curNode.next
    }
    // 反转指针
    if (curNode && prevNode) {
      curNode.next = prevNode
    }
    // 整体向后移动指针
    prevNode = curNode
    curNode = nextNode
    nextNode = nextNode?.next
  }
  // 当nextNode为空时，此时curNode尚未设置next
  curNode.next = prevNode
  return curNode
}
const arr = [100, 200, 300, 400, 500]
const list = createLinkList(arr)
console.log('list', list)
const list1 = reverseLinkList(list)
console.log('list1', list1)