HBee's Repo

Appearance

栈和队列的应用 ​

数制的转换 ​

当一个十进制整数 N 转换为八进制时，在计算过程中，把 N 与 8 求余得到的八进制数的各位依次进栈，计算完毕后将栈中的八进制数依次出栈输出，输出结果就是待求得的八进制数。

算法如下：

ts
export function conversion(n: number) {
  const stack: number[] = []

  while (n) {
    stack.push(n % 8)
    n = Math.trunc(n / 8)
  }

  return stack.reverse().join('')
}

时间复杂度和空间复杂度均为 O(log8⁡n)。

括号匹配的检验 ​

检验算法使用一个栈，每当读入一个左括号，则直接入栈，等待相匹配的同类右括号；读入一个右括号，若与当前栈顶的左括号类型相同，则二者匹配，将栈顶的左括号出栈，直到表达式扫描完毕。

算法如下：

ts
const bracketsMap: Record<string, string> = {
  ')': '(',
  ']': '[',
  '}': '{',
}

export function matching(str: string) {
  const stack: string[] = []

  for (let i = 0; i < str.length; i++) {
    const char = str[i]
    const bracket = bracketsMap[char]

    if (!bracket) {
      stack.push(char)
    } else {
      const rear = stack.pop()
      if (rear !== bracket) return false
    }
  }

  return !stack.length
}

时间复杂度和空间复杂度均为 O(n)。

表达式求值 ​

任何一个表达式都是由操作数（operand）、运算符（operator）和分隔符（delimiter）组成的。在此我们仅讨论简单算术表达式的求值问题，这种表达式只有加、减、乘、除 4 种运算符。

算术四则运算遵循以下 3 条规则：

  • 先乘除，后加减
  • 从左算到右
  • 先算括号内，后算括号外

根据上述规则，我们可以得出任意两个相继出现的运算符或分隔符 θ1、θ2 之间的优先级关系，如下表，行头为 θ1，列头为 θ2。

+-*/();
+>><<<>>
->><<<>>
*>>>><>>
/>>>><>>
(<<<<<=
)>>>>>>

算法如下：

ts
const operators = ['+', '-', '*', '/', '(', ')', ';']

export function precede(operator1: string, operator2: string) {
  switch (operator1) {
    case '+':
    case '-':
      return operators.slice(2, 5).includes(operator2) ? '<' : '>'
    case '*':
    case '/':
      return operator2 === '(' ? '<' : '>'
    case '(':
      return operator2 === ')' ? '=' : operator2 === ';' ? '' : '<'
    case ')':
      return operator2 === '(' ? '' : '>'
  }
}

export function arithmetic(expression: string) {
  const opnd: number[] = [] // 操作数栈
  const optr: string[] = [] // 运算符栈
  let tmp = ''

  for (let i = 0; i < expression.length; i++) {
    const char = expression[i]
    if (!operators.includes(char)) {
      // opnd.push(+char)
      tmp += char
      continue
    }

    if (tmp) {
      opnd.push(+tmp)
      tmp = ''
    }

    if (!optr.length) {
      optr.push(char)
      continue
    }

    let operator = ''
    let opnd1 = 0
    let opnd2 = 0

    switch (precede(optr.at(-1)!, char)) {
      case '<':
        optr.push(char)
        break
      case '>':
        operator = optr.pop()!
        opnd1 = +opnd.pop()!
        opnd2 = +opnd.pop()!
        opnd.push(eval(`${opnd2}${operator}${opnd1}`))
        if (optr.length) {
          i-- // 不要读取下一个字符
        }
        break
      case '=':
        optr.pop()
        break

      default:
        return NaN
    }
  }

  return opnd.at(-1)
}

时间复杂度和空间复杂度均为 O(n)。

舞伴问题 ​

假设有一个舞会，男士和女士进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那队中未配对者等待下轮舞曲。现要求写一算法模拟上述舞伴配对问题。

先入队的男士或女士先出队配成舞伴，因此设置两个队列分别存放男士和女士入队者。假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的元素，根据性别来决定进入哪个队列。当这两个队列构造完成之后，依次将两队当前队头元素出队配成舞伴，直至某队列为空。此时，若某队列仍有等待配对者，则输出此队列队头姓名。

算法如下：

ts
import { SexType } from '@faker-js/faker'

interface People {
  name: string
  sex: SexType
}

export function dance(peoples: People[]): People | undefined {
  const males: People[] = []
  const females: People[] = []

  for (let i = 0; i < peoples.length; i++) {
    if (peoples[i].sex === 'female') {
      females.push(peoples[i])
    } else {
      males.push(peoples[i])
    }
  }

  while (males.length && females.length) {
    females.shift()
    males.shift()
  }

  return females.length ? females[0] : males[0]
}

时间复杂度和空间复杂度均为 O(n)。

Copyright © 2022-present HBee