算法题

题干：给定一个字符串 s，找出其中不含重复字符的最长子串，返回该子串。

• 来源：科锐特好未来
• 口述：双指针 i/j 维护不重复窗口 → Set 记录窗口内字符 → 遇到重复就从左边不断 delete 直到不重复

function longestUniqueSubstring(str) {
  if (!str) return ''
  let set = new Set()
  let i = 0, j = 1
  let maxLen = 0, maxAns = ''

  while (j < str.length) {
    let newChar = str[j - 1]
    if (set.has(newChar)) {
      // 从左边不断删，直到窗口内没有重复字符
      while (set.has(newChar)) {
        set.delete(str[i])
        i++
      }
    }
    set.add(newChar)

    let curAns = str.slice(i, j)
    if (curAns.length > maxLen) {
      maxLen = curAns.length
      maxAns = curAns
    }
    j++
  }
  return maxAns
}

longestUniqueSubstring('fdakjlkeiytabcdefghijklmnopqrstuirwhd')
// "ytabcdefghijklmnopqrs"

题干：给定版本号字符串数组 ["1.5.1", "1.45.0", "3.3.3.3", "1.5", "6"]，按版本号从小到大排序。版本号位数不固定，缺失的位视为 0。

function sortVersion(version) {
  version.sort((a, b) => {
    const arrA = a.split('.').map(Number)
    const arrB = b.split('.').map(Number)
    const len = Math.max(arrA.length, arrB.length)

    for (let i = 0; i < len; i++) {
      const itemA = arrA[i] ?? 0 // ?? 而不是 ||，因为 || 会把 0 也兜底掉
      const itemB = arrB[i] ?? 0
      if (itemA > itemB) return 1
      if (itemA < itemB) return -1
    }
    return 0
  })
  return version
}

sortVersion(["1.5.1", "1.45.0", "1.99.99", "3.3.3.3", "1.5", "6"])
// ["1.5", "1.5.1", "1.45.0", "1.99.99", "3.3.3.3", "6"]

• 用 ?? 而不是 ||，因为 || 会把 0 也兜底

题干：实现 get(obj, path)，根据路径字符串安全地访问嵌套对象属性。路径支持点号和方括号：'a.b[10][0].cd[3].e'，属性不存在时返回 undefined。

• 思路：解析路径 'a.b[10][0].cd[3].e' → ['a','b','10','0','cd','3','e']
• 然后 reduce 逐层访问

function get(object, path) {
  function parsePath(path) {
    const parts = []
    let current = ''
    for (let i = 0; i < path.length; i++) {
      const char = path[i]
      if (char === '.' || char === '[' || char === ']') {
        if (current) { parts.push(current); current = '' }
      } else {
        current += char
      }
    }
    if (current) parts.push(current)
    return parts
  }

  return parsePath(path).reduce((acc, key) => {
    return acc && acc[key] !== undefined ? acc[key] : undefined
  }, object)
}

get({ a: { b: [,,,,,,,,,,[{ cd: [,,,{ e: 42 }] }]] } }, 'a.b[10][0].cd[3].e')
// 42

function quickSort(arr) {
  if (arr.length <= 1) return arr

  let val = arr[0] // 选第一个作为基准
  let remain = arr.slice(1) // 注意要 slice(1) 去掉基准自己
  let left = remain.filter(item => item <= val)
  let right = remain.filter(item => item > val)

  // 注意要递归调用，然后展开
  return [...quickSort(left), val, ...quickSort(right)]
}

quickSort([3, 6, 8, 10, 1, 2, 1])
// [1, 1, 2, 3, 6, 8, 10]

题干：判断括号字符串是否合法。除了常规的匹配规则外，额外要求优先级：{} > [] > ()，大括号可以包中/小括号，但小括号不能包大括号。如 {[]} 合法，[{}] 非法。

function isValidParen(str) {
  const priority = { '{': 3, '[': 2, '(': 1 }
  const matching = { '}': '{', ']': '[', ')': '(' }
  const stack = []

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

    if (char === '{' || char === '[' || char === '(') {
      // 大括号能包小括号，小括号不能包大括号
      if (
        stack.length === 0 ||
        priority[stack[stack.length - 1]] >= priority[char]
      ) {
        stack.push(char)
      } else {
        return false // 外层优先级 < 内层，小包大，非法
      }
    } else if (char === '}' || char === ']' || char === ')') {
      if (stack.length === 0) return false
      if (stack[stack.length - 1] === matching[char]) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

isValidParen('[](){[]}')   // true
isValidParen('[{}]')       // false（小包大）

题干：用迭代法（不能用递归）实现二叉树的前序、中序、层序遍历。节点结构 { val, left, right }。

前序（Root → Left → Right）

function preorder(root) {
  const res = [], stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    res.push(node.val)
    // 先压 right 再压 left，因为栈是后进先出，这样 left 先弹出
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }
  return res
}

中序（Left → Root → Right）

function inorder(root) {
  const res = [], stack = []
  let cur = root
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left } // 一路向左压栈
    cur = stack.pop()     // 弹出最左节点
    res.push(cur.val)     // 访问
    cur = cur.right       // 转向右子树
  }
  return res
}

层序 BFS

function levelOrder(root) {
  const res = []
  if (!root) return res
  const q = [root]
  let i = 0
  while (i < q.length) {
    const size = q.length - i
    const level = []
    for (let k = 0; k < size; k++) {
      const node = q[i++]
      level.push(node.val)
      if (node.left) q.push(node.left)
      if (node.right) q.push(node.right)
    }
    res.push(level)
  }
  return res
}