Resource Hub

创建于2025年02月17日 00:25

状态公开

前端算法与原理深度解析

一、字符串处理的艺术

1.1 路径字符串转嵌套对象

该算法的核心在于逆向构建对象树，通过反向遍历分割后的数组，逐步包裹形成嵌套结构。这里巧妙利用了JS对象引用特性，每次循环都创建新的对象包裹层。

typescript

1// 时间复杂度O(n)，空间复杂度O(n)
2const strToObject = (str: string) => {
3  return str.split('.').reverse().reduce((acc, cur) => ({[cur]: acc}), null)
4};

扩展思考：

支持数组索引转换（如'a[0].b'）
处理循环引用场景
类型安全的深度类型定义（使用TS递归类型）

1.2 有效字母异位词

采用计数排序思想优化空间复杂度，使用固定长度数组替代哈希表。注意Unicode扩展字符的处理需要调整数组长度：

typescript

1// 处理扩展ASCII（256个字符）
2const isAnagram = (s: string, t: string) => {
3  if (s.length !== t.length) return false
4  const counter = new Array(256).fill(0)
5  for (let i = 0; i < s.length; i++) {
6    counter[s.charCodeAt(i)]++
7    counter[t.charCodeAt(i)]--
8  }
9  return counter.every(v => v === 0)
10}

二、类型系统的魔法

2.1 柯里化类型体操

类型柯里化的本质是递归解构参数类型。通过逐步剥离参数类型，构建嵌套的函数类型链：

typescript

1type Curried<F> = F extends (...args: infer A) => infer R 
2  ? A extends [infer H, ...infer T] 
3    ? (arg: H) => Curried<(...args: T) => R> 
4    : R 
5  : never

实现要点：

泛型参数的类型推断
条件类型的递归展开
函数签名的逐步分解

三、位运算的妙用

3.1 汉明距离总和

利用位独立原理，将问题分解到每个bit位单独计算。对于第i位，统计所有数中该位为1的个数c，则该位的总贡献为c*(n-c)：

typescript

1function totalHammingDistance(nums: number[]): number {
2  let total = 0
3  for (let i = 0; i < 32; i++) {
4    let count = 0
5    for (const num of nums) {
6      count += (num >> i) & 1
7    }
8    total += count * (nums.length - count)
9  }
10  return total
11}

复杂度分析：

时间复杂度：O(32n) → O(n)
空间复杂度：O(1)

四、动态规划典范

4.1 股票买卖最佳时机

经典的单状态DP问题，维护历史最低价和当前最大利润：

typescript

1function maxProfit(prices: number[]): number {
2  let minPrice = Infinity
3  let maxProfit = 0
4  for (const price of prices) {
5    minPrice = Math.min(minPrice, price)
6    maxProfit = Math.max(maxProfit, price - minPrice)
7  }
8  return maxProfit
9}

变种扩展：

允许多次交易（波峰波谷法）
含冷冻期（状态机DP）
带交易手续费（分状态维护）

五、随机算法实践

5.1 链表随机节点

水塘抽样算法的典型应用，保证每个节点被选中的概率均为1/n：

typescript

1class Solution {
2  constructor(private head: ListNode) {}
3
4  getRandom(): number {
5    let scope = 1
6    let chosen = 0
7    let curr = this.head
8    while (curr) {
9      if (Math.random() < 1 / scope) {
10        chosen = curr.val
11      }
12      scope++
13      curr = curr.next
14    }
15    return chosen
16  }
17}

算法证明：

第i个节点被选中的概率 = 被选中概率 × 不被后续节点替换概率
1/i × (i/(i+1)) × ... × (n-1/n) = 1/n

六、二叉树遍历的工程实现

6.1 迭代遍历统一范式

通过显式栈模拟调用栈，关键在记录节点访问状态：

typescript

1// 后序遍历示例
2function postOrder(root: TreeNode) {
3  const stack = [[root, false]]
4  const res = []
5  
6  while (stack.length) {
7    const [node, visited] = stack.pop()
8    if (!node) continue
9    
10    if (visited) {
11      res.push(node.val)
12    } else {
13      stack.push([node, true])
14      stack.push([node.right, false])
15      stack.push([node.left, false])
16    }
17  }
18  return res
19}

性能对比：

遍历方式	时间复杂度	空间复杂度	适用场景
递归	O(n)	O(h)	树深度小时
迭代	O(n)	O(n)	避免栈溢出
Morris	O(n)	O(1)	严格空间限制

七、JavaScript核心原理

7.1 浮点数精度问题

根本原因：IEEE 754双精度格式的有限精度表示导致分数转换误差

工程解决方案：

精度要求不高时：四舍五入指定小数位

typescript

1const safeAdd = (a: number, b: number) => 
2  parseFloat((a + b).toFixed(10))

高精度计算：使用decimal.js库

typescript

1import Decimal from 'decimal.js'
2new Decimal(0.1).add(0.2).equals(0.3) // true

大整数处理：使用BigInt类型

typescript

1const maxSafe = BigInt(Number.MAX_SAFE_INTEGER)
2console.log(maxSafe + 1n === maxSafe + 2n) // false

内存布局解析：

1┌──────────────┬───────────────────────────┬───────────────────────┐
2│ Sign (1 bit) │ Exponent (11 bits)        │ Mantissa (52 bits)    │
3│ 0: positive  │ 10000000000 (adjusted 1023) │ 1.xxxxxx... implicit leading 1 │
4└──────────────┴───────────────────────────┴───────────────────────┘

八、进阶思考

类型体操的边界情况：如何处理可选参数和剩余参数？
水塘抽样的分布式扩展：如何对超大规模数据流进行分布式抽样？
浮点数精度补偿算法：Kahan求和算法原理与应用
迭代遍历的并行化可能：基于栈分割的并行遍历方案

九、参考资料

IEEE 754标准文档（2019修订版）
《算法导论》第三版 - 托马斯·科尔曼
TypeScript Deep Dive - 类型系统进阶
V8引擎浮点数实现源码分析

通过深入理解这些核心算法和底层原理，开发者可以更好地应对复杂场景需求，写出高效可靠的代码。在实践中要注意不同解决方案的适用边界，根据具体场景选择最优解。