加载笔记内容...
加载笔记内容...
该算法的核心在于逆向构建对象树，通过反向遍历分割后的数组，逐步包裹形成嵌套结构。这里巧妙利用了JS对象引用特性，每次循环都创建新的对象包裹层。
1// 时间复杂度O(n)，空间复杂度O(n)
2const strToObject = (str: string) => {
3 return str.split('.').reverse().reduce((acc, cur) => ({[cur]: acc}), null)
4};扩展思考：
采用计数排序思想优化空间复杂度，使用固定长度数组替代哈希表。注意Unicode扩展字符的处理需要调整数组长度：
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}类型柯里化的本质是递归解构参数类型。通过逐步剥离参数类型，构建嵌套的函数类型链：
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实现要点：
利用位独立原理，将问题分解到每个bit位单独计算。对于第i位，统计所有数中该位为1的个数c，则该位的总贡献为c*(n-c)：
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}复杂度分析：
经典的单状态DP问题，维护历史最低价和当前最大利润：
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}变种扩展：
水塘抽样算法的典型应用，保证每个节点被选中的概率均为1/n：
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}算法证明：
通过显式栈模拟调用栈，关键在记录节点访问状态：
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) | 严格空间限制 |
根本原因：IEEE 754双精度格式的有限精度表示导致分数转换误差
工程解决方案：
精度要求不高时：四舍五入指定小数位
1const safeAdd = (a: number, b: number) =>
2 parseFloat((a + b).toFixed(10))高精度计算：使用decimal.js库
1import Decimal from 'decimal.js'
2new Decimal(0.1).add(0.2).equals(0.3) // true大整数处理：使用BigInt类型
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└──────────────┴───────────────────────────┴───────────────────────┘通过深入理解这些核心算法和底层原理，开发者可以更好地应对复杂场景需求，写出高效可靠的代码。在实践中要注意不同解决方案的适用边界，根据具体场景选择最优解。