14 算法实战

Huy大约 2 分钟

总述算法的一些常见考题。

判断一个字符串是否括号匹配

一个字符串 s 可能包含 {}()[] 三种括号;
判断 s 是否是括号匹配的;
如(a{b}c)匹配，而{a(b或{a(b}c)就不匹配。

/**
 * @description 括号匹配
 * @param str str
 */
function matchBracket(str: string): boolean {
  const length = str.length
  if (length === 0) return true

  const stack = []

  const leftSymbols = '{[('
  const rightSymbols = '}])'

  for (let i = 0; i < length; i++) {
    const s = str[i]

    if (leftSymbols.includes(s)) {
      // 左括号, 压栈
      stack.push(s)
    } else if (rightSymbols.includes(s)) {
      // 左括号, 判断栈顶(是否出栈)
      const top = stack.pop()
      if (!isMatch(top, s)) return false
    }
  }

  return stack.length === 0
}

function isMatch(left: any, right: any): boolean {
  if (left === '(' && right === ')') return true
  if (left === '[' && right === ']') return true
  if (left === '{' && right === '}') return true
  return false
}

console.log(matchBracket('(a)'))

定义一个 JS 函数，反转单向链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
  // 节点少于 2 个
  if (head == null || head.next == null) return head

  let currentList = head,
    preList = null,
    nextList = null

  while (currentList.next !== null) {
    nextList = currentList.next
    currentList.next = preList
    preList = currentList
    currentList = nextList
  }
  currentList.next = preList

  return currentList
}

实现千元分隔符

首先由于笔者正则不是很好（老是记了又忘 bushi），所以采用别的方法来实现。

// 原生方法
function formatWithCommas(num) {
  return num.toLocaleString('zh-CN') // 增加地区为确保输出分隔符为逗号
}

// 手动分割
function formatWithCommas(num) {
  const str = num.toString()
  const [integer, decimal] = str.split('.')

  // 反转整数部分，每3位加逗号，再反转回来
  const target = Array.from(integer)
    .reverse()
    .map((item, index) => {
      if (index > 0 && index % 3 === 0) {
        return item + ','
      } else {
        return item
      }
    })
    .reverse()
    .join('')

  return decimal ? target + '.' + decimal : target
}

实现一个随机抢红包算法

function randomRedPackets(total, count, min, max) {
  // 边界校验
  if (total < count * min || total > count * max) {
    throw new Error('total is invalid')
  }

  const result = []
  for (let i = 0; i < count - 1; i++) {
    const restCount = count - i // 剩余还有多少个红包待分配
    const maxAvailable = Math.min(max, total - min * (restCount - 1)) // 减去当前轮次
    const amount = Math.random() * (maxAvailable - min) + min

    // 保留 2 位小数, 向下取值, 不然会溢出
    const amountFixed = Math.floor(amount * 100) / 100
    result.push(amountFixed)
    total -= amountFixed
  }

  // 最后一个红包需要修复, 可能加不到总和
  result.push(Math.round(total * 100) / 100)

  return result
}

14 算法实战

# 判断一个字符串是否括号匹配

# 定义一个 JS 函数，反转单向链表

# 实现千元分隔符

# 实现一个随机抢红包算法

判断一个字符串是否括号匹配

定义一个 JS 函数，反转单向链表

实现千元分隔符

实现一个随机抢红包算法