前端常考的算法题：列表转树、版本号比较、大数相加怎么写？

function listToTree(items, rootParentId = null) {
  const childrenOf = new Map() // id -> 子节点数组
  // 取 id 的子节点数组，没有就新建（Map 的 set 返回 Map 本身，可以接着 get）
  const getChildren = (id) => childrenOf.get(id) ?? childrenOf.set(id, []).get(id)
  const roots = []
  for (const item of items) {
    const node = { ...item, children: getChildren(item.id) } // 拷贝一份，不修改入参
    if (item.parentId === rootParentId) roots.push(node)
    else getChildren(item.parentId).push(node)
  }
  return roots
}

function treeToList(tree) {
  const result = []
  const stack = [...tree].reverse() // 反转后入栈，出栈顺序才和原顺序一致
  while (stack.length) {
    const { children = [], ...rest } = stack.pop()
    result.push(rest) // 去掉 children 字段
    for (let i = children.length - 1; i >= 0; i--) stack.push(children[i])
  }
  return result
}

const tree = listToTree([{ id: 3, parentId: 1 }, { id: 1, parentId: null }, { id: 2, parentId: null }])
console.log(JSON.stringify(tree)) // '[{"id":1,"parentId":null,"children":[{"id":3,"parentId":1,"children":[]}]},{"id":2,"parentId":null,"children":[]}]'
console.log(treeToList(tree).map((item) => item.id)) // [1, 3, 2]

function compareVersion(a, b) {
  const partsA = a.split('.')
  const partsB = b.split('.')
  for (let i = 0; i < Math.max(partsA.length, partsB.length); i++) {
    const x = Number(partsA[i] ?? 0) // 缺的段补 0，'01' 转成 1
    const y = Number(partsB[i] ?? 0)
    if (x !== y) return x > y ? 1 : -1
  }
  return 0
}
console.log(compareVersion('1.10.0', '1.9'), compareVersion('1.0', '1.0.0')) // 1 0
console.log(['1.10', '1.2', '1.9.1'].sort(compareVersion)) // ['1.2', '1.9.1', '1.10']

function addStrings(a, b) {
  let i = a.length - 1
  let j = b.length - 1
  let carry = 0
  const digits = []
  while (i >= 0 || j >= 0 || carry > 0) {
    const sum = (i >= 0 ? Number(a[i--]) : 0) + (j >= 0 ? Number(b[j--]) : 0) + carry // 位用完了就当 0
    digits.push(sum % 10)
    carry = Math.floor(sum / 10)
  }
  return digits.reverse().join('') // 低位先放进数组，最后反转
}
console.log(addStrings('9007199254740993', '1')) // '9007199254740994'
console.log(addStrings('999', '1')) // '1000'

function formatThousands(num) {
  const [intPart, decimalPart] = String(num).split('.')
  const formatted = intPart.replace(/\B(?=(\d{3})+$)/g, ',')
  return decimalPart === undefined ? formatted : `${formatted}.${decimalPart}`
}
console.log(formatThousands(1234567.891)) // '1,234,567.891'
console.log(formatThousands(-1234.5)) // '-1,234.5'

function flatten(arr, depth = Infinity, result = []) {
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) flatten(item, depth - 1, result)
    else result.push(item)
  }
  return result
}
console.log(flatten([1, [2, [3, [4]]]], 1)) // [1, 2, [3, [4]]]