算法 - 手写 Promise.race

Posted on 2025-03-26

1. 题目

实现 promiseRace(iterables)，行为对齐原生 Promise.race：

接收一个可迭代的 Promise（或普通值）集合，返回一个新 Promise。
结果由**第一个 settle（无论 fulfilled 还是 rejected）**的成员决定：它成功就 resolve，它失败就 reject。
关键区别于 Promise.all：race 不关心成败，只关心谁先落地。
空数组：原生 Promise.race([]) 会永远 pending（没有任何成员能触发 settle），需照此实现。

示例:

1 2	promiseRace([慢成功, 快失败]) -> reject（快的那个先 settle） promiseRace([快成功, 慢失败]) -> resolve（快的那个先 settle）

2. 解题思路

一句话：给每个成员同时挂上 resolve 和 reject，谁先调用谁就赢。

因为 Promise 一旦 settle 就冻结，后续再调用 resolve/reject 都是空操作。所以完全不必自己加「是否已完成」的锁：

遍历集合，用 Promise.resolve(item) 包一层（兼容非 Promise 值，让它也进入微任务队列公平竞争）。
对每个包装后的 Promise，.then(resolve, reject)——把外层的 resolve、reject 直接透传。
第一个 settle 的成员会率先调用外层 resolve 或 reject，外层 Promise 随即定型，其余调用被忽略。

空数组直接返回一个不 settle 的 Promise（new Promise(() => {})）以匹配原生语义。
时间复杂度：O(n) 建立回调。

3. TypeScript 实现

function promiseRace<T>(
    iterables: Iterable<T | PromiseLike<T>>
): Promise<Awaited<T>> {
    return new Promise((resolve, reject) => {
        for (const item of iterables) {
            // 用 Promise.resolve 包装，普通值也异步参与竞争
            Promise.resolve(item).then(resolve, reject);
        }
        // 空集合：循环不执行，Promise 永久 pending（与原生一致）
    });
}

// 测试
const slow = (v: string, ms: number) =>
    new Promise<string>((r) => setTimeout(() => r(v), ms));
const fastFail = (ms: number) =>
    new Promise<never>((_, rej) => setTimeout(() => rej("boom"), ms));

promiseRace([slow("slow-win", 300), fastFail(100)])
    .then(console.log)
    .catch(console.log); // "boom"（先 settle）

promiseRace([slow("first", 50), slow("second", 200)])
    .then(console.log);  // "first"

4. 面试延伸

race vs any：Promise.any 只在第一个成功时定胜负，忽略失败；只有全部失败才 reject 一个 AggregateError。别把 race 的「先 settle」和 any 的「先成功」搞混。
race vs allSettled：allSettled 等所有人落地并汇总状态，永不 reject；race 恰恰相反，抢跑即定。
实战用法：请求超时控制是 race 最典型场景——Promise.race([fetchData(), timeout(5000)])，超时的那个先 reject 就达成「N 秒没返回就报错」。
能主动说出「空数组永远 pending」这个反直觉细节，是加分信号，说明你真用过而非只背签名。

难度：中等 | 手写 Promise 家族 | 超时控制基石

算法 - 手写简易 Promise

Posted on 2025-02-07

1. 题目

实现一个满足以下核心特性的迷你 MyPromise：

三种状态：pending、fulfilled、rejected，状态一经改变不再变化。
构造器接收 executor(resolve, reject)，立即执行；executor 内抛错则转为 rejected。
resolve/reject 可接收值；若 resolve 一个 Promise（thenable），要等它 settle 后再决定本 Promise 状态。
then(onFulfilled, onRejected) 支持链式调用（返回新 Promise），且回调异步在微任务里执行；支持值穿透（回调不是函数时透传）。
catch 复用 then。

2. 解题思路

四个关键点：

状态机：用一个 status 字段 + 只允许一次变更（用 changeStatus 守卫），保证不可逆。
异步执行回调：then 的回调不能立即调用（可能在 resolve 之前就被 then），统一丢进 queueMicrotask（模拟微任务，等价 Promise.resolve().then()）。
链式 & 值穿透：then 永远返回一个新的 Promise；若传入的不是函数，用默认的 v => v（成功透传）和 err => throw err（失败下抛），从而支持 .then().then() 跳过。
resolve thenable：resolve 收到的若是带 then 方法的对象/ Promise，需递归地采用它的最终状态，不能直接 fulfilled。

状态变更 O(1)；链式每个 then O(1)。

3. TypeScript 实现

type Status = "pending" | "fulfilled" | "rejected";

class MyPromise {
    private status: Status = "pending";
    private value: any = undefined;
    private reason: any = undefined;

    constructor(executor: (resolve: (v?: any) => void, reject: (r?: any) => void) => void) {
        try {
            executor(this.resolve.bind(this), this.reject.bind(this));
        } catch (e) {
            this.reject(e);
        }
    }

    private resolve(value: any): void {
        if (this.status !== "pending") return; // 只允许一次
        // resolve 了一个 thenable -> 采用其状态
        if (value && (typeof value === "object" || typeof value === "function")
            && typeof value.then === "function") {
            value.then(this.resolve.bind(this), this.reject.bind(this));
            return;
        }
        this.status = "fulfilled";
        this.value = value;
    }

    private reject(reason: any): void {
        if (this.status !== "pending") return;
        this.status = "rejected";
        this.reason = reason;
    }

    then(onFulfilled?: any, onRejected?: any): MyPromise {
        // 值穿透：非函数用默认处理器
        onFulfilled = typeof onFulfilled === "function" ? onFulfilled : (v: any) => v;
        onRejected = typeof onRejected === "function" ? onRejected : (e: any) => { throw e; };

        return new MyPromise((resolve, reject) => {
            const runFulfilled = () =>
                queueMicrotask(() => {
                    try { resolve(onFulfilled(this.value)); }
                    catch (e) { reject(e); }
                });
            const runRejected = () =>
                queueMicrotask(() => {
                    try { resolve(onRejected(this.reason)); }
                    catch (e) { reject(e); }
                });

            if (this.status === "fulfilled") {
                runFulfilled();
            } else if (this.status === "rejected") {
                runRejected();
            }
            // 注意：简易版未处理 pending 时回调的收集；
            // 完整版应把 runFulfilled/runRejected 存入回调数组，resolve/reject 时再依次触发。
        });
    }

    catch(onRejected: any): MyPromise {
        return this.then(undefined, onRejected);
    }

    static resolve(v: any): MyPromise {
        if (v instanceof MyPromise) return v;
        return new MyPromise((resolve) => resolve(v));
    }
}

// 测试：链式 + 值穿透
new MyPromise<number>((resolve) => setTimeout(() => resolve(1), 50))
    .then((v) => { console.log(v); return v + 1; }) // 1
    .then(null)                                    // 值穿透
    .then((v) => console.log(v));                  // 2

说明：为了讲解聚焦，上面 then 省略了「pending 状态下回调收集」的实现。完整版本必须在 Promise 尚未 settle 时把回调 push 进 onFulfilledCbs[] / onRejectedCbs[]，并在 resolve/reject 里遍历触发——这是异步 executor 场景正确性的关键。

4. 面试延伸

为什么用微任务而不是 setTimeout：Promise 回调属微任务，在同步代码之后、下一轮事件循环前统一执行；setTimeout 是宏任务，时序不同。能讲清宏/微任务队列即是加分。
then 返回新 Promise 且 resolve 回调返回值：正是这个「返回值再交给新 Promise 的 resolve」实现了链式传递和 thenable 展开。
resolve(new MyPromise(...)) 不会立刻定状态：因为 thenable 递归采用逻辑，能答出这点说明真懂。
进阶补全：加上 pending 回调队列、静态 all/race/any/allSettled（见 [Promise.all]、[Promise.race] 两篇），即接近 A+ 规范。
异常处理：回调内 throw 会被新 Promise reject 捕获，向下游 catch 冒泡，与原生一致。

难度：困难 | 手写 Promise 核心 | 异步机制试金石

算法 - KMP 字符串匹配

Posted on 2025-01-19

1. 题目

给定字符串 haystack 和 needle，返回 needle 在 haystack 中第一次出现的下标，若不存在返回 -1。要求优于暴力的 O(m×n)。

示例:

输入: haystack = "sadbutsad", needle = "sad"
输出: 0

输入: haystack = "leetcode", needle = "leeto"
输出: -1

2. 解题思路

暴力匹配在文本串上每失配一次就把模式串整体后移一位、指针回到开头，产生大量重复比较。KMP 的核心：利用「模式串自身的重叠信息」，失配时主串指针不回退，模式串指针跳到最长可用位置。

2.1 前缀函数（next / lps 数组）

定义 lps[i] = 子串 needle[0..i] 的最长相等真前后缀长度（proper prefix 同时是 suffix）。

例如 needle = "abab"：

lps = [0, 0, 1, 2]
"abab" 前 4 个字符分别的最长相等前后缀："a"->0、"ab"->0、"aba"->"a"=1、"abab"->"ab"=2。

2.2 构建 lps（也是双指针）

len 表示当前已匹配的前缀长度：

needle[i] === needle[len] → lps[i] = ++len; i++。
不等且 len > 0 → len = lps[len-1]（回溯到次长前后缀，i 不动）。
不等且 len === 0 → lps[i] = 0; i++。

2.3 匹配

主串 j、模式串 i 双指针，失配时 i = lps[i-1]（不回退 j），直到 i === needle.length 命中。

时间复杂度：O(m + n)；空间复杂度：O(n)（lps 数组）。

3. TypeScript 实现

function buildLPS(pattern: string): number[] {
    const n = pattern.length;
    const lps = new Array(n).fill(0);
    let len = 0; // 前一个最长前后缀长度
    let i = 1;

    while (i < n) {
        if (pattern[i] === pattern[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1]; // 回溯，i 不前进
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    if (n === 0) return 0;

    const lps = buildLPS(needle);
    let i = 0; // haystack 指针（永不回退）
    let j = 0; // needle 指针

    while (i < m) {
        if (haystack[i] === needle[j]) {
            i++;
            j++;
            if (j === n) return i - j; // 完全匹配
        } else if (j > 0) {
            j = lps[j - 1]; // 部分匹配，跳回
        } else {
            i++; // j=0 直接前移
        }
    }
    return -1;
}

console.log(strStr("sadbutsad", "sad"));       // 0
console.log(strStr("ababcababc", "abc"));       // 2
console.log(strStr("leetcode", "leeto"));       // -1
console.log(buildLPS("abab"));                  // [0,0,1,2]

4. 面试延伸

理解 j = lps[j-1] 的精髓：它把「已经匹配过的前缀」当作可复用的后缀，让 i 全程不回退，这是 KMP 达到线性的根本。
最小覆盖子串 / 重复子串（459）：用 n - lps[n-1] 判断字符串是否由某最短单元重复构成。
Rabin-Karp（滚动哈希）：多模式匹配 / 查重更友好，平均线性但要处理哈希冲突。
BM 算法：编辑器/grep 的实战主力（坏字符 + 好后缀规则，实际常常比 KMP 快），面试聊到工程落地可提。
手推 lps 时一定举例 "aabaaab" 之类复杂串验证，别只说结论。

难度：中等 | LeetCode 28 题 | 前缀函数 / 双指针

算法 - 数组第 K 大元素 / TopK 问题

Posted on 2024-12-05

1. 题目

给定整数数组 nums 和整数 k，返回数组中第 k 大的元素（排序后第 k 个位置的值，不是第 k 个不同元素）。

示例:

输入: nums = [3,2,1,5,6,4], k = 2
输出: 5

输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

2. 解题思路

「第 K 大 / Top K」是超高频题型，有三种主流套路，各有适用场景。

2.1 排序法 O(n log n)

直接排序后取 nums[n - k]。简单，但不是最优，面试可作为保底并说明「有更快的」。

2.2 大小为 K 的最小堆 O(n log k) —— 求 TopK 首选

维护一个只装 k 个元素的最小堆：

遍历数组，堆大小 < k 就入堆。
否则若当前值 > 堆顶（堆里最小的），弹出堆顶、压入当前值。
遍历结束，堆顶就是第 k 大（堆里 k 个数中最小的那个，恰为整体第 k 大）。

优势：天然适合数据流 / 海量数据，内存只需 O(k)，不必一次性拿到全部数据，这也是「TopK」在工程里（如热点搜索词）的常见解法。

2.3 快速选择（Quickselect）平均 O(n)

复用快排的 partition：每趟把基准放到最终位置 p，若 p === n-k 直接返回；否则只递归目标所在的那一半，平均线性、最坏 O(n²)（随机化 pivot 可高概率避免）。

时间复杂度：平均 O(n)；空间 O(1)（原地）。

3. TypeScript 实现

// 2.3 快速选择（原地，平均 O(n)）
function findKthLargest(nums: number[], k: number): number {
    const target = nums.length - k; // 转成升序下标

    function partition(lo: number, hi: number): number {
        // 随机化，避免有序退化
        const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
        [nums[rand], nums[hi]] = [nums[hi], nums[rand]];
        const pivot = nums[hi];
        let i = lo;
        for (let j = lo; j < hi; j++) {
            if (nums[j] < pivot) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        [nums[i], nums[hi]] = [nums[hi], nums[i]];
        return i;
    }

    let lo = 0;
    let hi = nums.length - 1;
    while (true) {
        const p = partition(lo, hi);
        if (p === target) return nums[p];
        if (p < target) lo = p + 1;
        else hi = p - 1;
    }
}

// 2.2 最小堆版（适合数据流 / 海量 TopK）
// 借助一个数值小顶堆：这里用极简实现演示思路
class MinHeap {
    private h: number[] = [];
    get size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v: number) {
        const h = this.h;
        h.push(v);
        let i = h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (h[p] <= h[i]) break;
            [h[p], h[i]] = [h[i], h[p]];
            i = p;
        }
    }
    pop() {
        const h = this.h;
        const top = h[0];
        const last = h.pop()!;
        if (h.length) {
            h[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1;
                const r = 2 * i + 2;
                let s = i;
                if (l < h.length && h[l] < h[s]) s = l;
                if (r < h.length && h[r] < h[s]) s = r;
                if (s === i) break;
                [h[s], h[i]] = [h[i], h[s]];
                i = s;
            }
        }
        return top;
    }
}

function topKKthLargest(nums: number[], k: number): number {
    const heap = new MinHeap();
    for (const x of nums) {
        if (heap.size < k) heap.push(x);
        else if (x > heap.peek()) {
            heap.pop();
            heap.push(x);
        }
    }
    return heap.peek();
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));     // 5
console.log(topKKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

4. 面试延伸

前 K 个高频元素（347）：先哈希统计频次，再对频次跑「大小 k 的小顶堆」或快速选择，是 TopK + 堆的经典组合。
海量数据（如 10 亿数取前 100）：绝不可能全放内存，答案就是大小为 k 的小顶堆分块处理，凸显堆相对于快选的优势。
第 K 小的元素 / 有序矩阵第 K 小（378）：可加一条「二分答案」解法——在值域二分，用 O(n) 统计 <= mid 的个数，O(n log(range))。
一定要区分：快速选择平均 O(n) 但会打乱原数组；堆法保证 O(n log k) 且能处理流式数据。选型看是否可修改原数组、是否一次性数据。

难度：中等 | LeetCode 215 题 | 堆 / 分治双高频

算法 - 岛屿数量 (Number of Islands)

Posted on 2024-11-14

1. 题目

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接形成，且四周都被水包围。

示例:

输入:
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]
输出: 3

2. 解题思路

典型的洪水填充（Flood Fill）/ 连通块计数。

遍历每个格子：

遇到 '1'，说明发现一座还没统计过的岛屿，count++。
立刻从该点做一次 DFS/BFS，把与它四连通的所有 '1' 全部「淹掉」（标记为 '0' 或写入 visited），这样同一座岛不会重复计数。
继续扫描，直到所有格子处理完。

「淹掉」即去重：一座岛只需在遇到它的第一个陆地格时计一次，之后整片都变 '0' 就不会再触发计数。

时间复杂度：O(m × n)，每个格子最多访问常数次。
空间复杂度：O(m × n) 最坏（递归栈或队列，全陆地时）。

3. TypeScript 实现

function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;
    const m = grid.length;
    const n = grid[0].length;

    // DFS 淹没整座岛
    function sink(r: number, c: number): void {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== "1") {
            return;
        }
        grid[r][c] = "0"; // 标记已访问（淹掉）
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    }

    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === "1") {
                count++;
                sink(r, c);
            }
        }
    }
    return count;
}

// BFS 版（防止超深网格递归爆栈）
function numIslandsBFS(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [
        [1, 0], [-1, 0], [0, 1], [0, -1],
    ];
    let count = 0;

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] !== "1") continue;
            count++;
            grid[r][c] = "0";
            const queue: [number, number][] = [[r, c]];
            while (queue.length) {
                const [x, y] = queue.shift()!;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === "1") {
                        grid[nx][ny] = "0";
                        queue.push([nx, ny]);
                    }
                }
            }
        }
    }
    return count;
}

4. 面试延伸

DFS 爆栈风险：超大网格（如 1000×1000 全陆地）递归深度可达百万级，BFS 或显式栈更稳，这是全栈工程意识的加分点。
不允许修改原网格？ 用 visited 布尔矩阵替代「淹成 0」，逻辑不变。
岛屿最大面积（695）/ 岛屿周长（463）：DFS 时顺带累加面积 / 统计临海面数。
封闭岛屿、地图分析（多源 BFS 求离陆地最远的海） 都是 Flood Fill 家族的变体。
并查集解法：把相邻陆地 union，最后数连通分量，能顺带动态加陆地，体现数据结构选型能力。
四连通 vs 八连通（含对角）只需增减 dirs，注意题意。

难度：中等 | LeetCode 200 题 | DFS/BFS 网格模板

算法 - 最长回文子串（中心扩散法）

Posted on 2024-10-29

1. 题目

给你一个字符串 s，找到其中最长的回文子串。回文指正读反读都一样。

示例:

输入: s = "babad"
输出: "bab"（"aba" 同样是合法答案）

输入: s = "cbbd"
输出: "bb"

2. 解题思路

2.1 中心扩散（推荐，直观且高效）

回文串一定围绕某个「中心」对称展开。长度为 n 的字符串共有 2n - 1 个中心：

n 个单字符中心（产生奇数长度回文，如 “aba”）。
n - 1 个双字符间隙中心（产生偶数长度回文，如 “abba”）。

枚举每个中心，向两边同时扩展直到不再相等，记录最长的一段。每个中心调用一次扩散函数，分别以 i（奇）和 i, i+1（偶）为初始左右指针。

时间复杂度：O(n²)；空间复杂度：O(1)。

2.2 动态规划 O(n²) 空间

dp[i][j] 表示 s[i..j] 是否回文：dp[i][j] = (s[i]===s[j]) && dp[i+1][j-1]。按长度从小到大填表。空间更大，思路清晰可作为对照。

存在 O(n) 的 Manacher 算法，面试一般不要求手写，能提名字并说明它是「利用已知回文的对称性避免重复扩展」即为加分。

3. TypeScript 实现

function longestPalindrome(s: string): string {
    if (s.length < 2) return s;

    let start = 0;
    let maxLen = 1;

    // 从 (left, right) 向两边扩散，返回回文长度
    function expand(left: number, right: number): number {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // 注意循环退出时各多走了一步
    }

    for (let i = 0; i < s.length; i++) {
        const oddLen = expand(i, i);     // 奇数中心
        const evenLen = expand(i, i + 1); // 偶数中心
        const len = Math.max(oddLen, evenLen);

        if (len > maxLen) {
            maxLen = len;
            // 由中心反推起点：奇偶统一用这个式子
            start = i - Math.floor((len - 1) / 2);
        }
    }

    return s.slice(start, start + maxLen);
}

console.log(longestPalindrome("babad")); // "bab" 或 "aba"
console.log(longestPalindrome("cbbd"));  // "bb"
console.log(longestPalindrome("a"));     // "a"

4. 面试延伸

起点公式 i - (len-1)/2 是易错点：奇偶都适用，因为 (len-1)/2 向下取整正好覆盖两种中心的偏移差异。
最长回文子序列（516）：子序列可不连续，转成「s 与 reverse(s) 的 LCS」或区间 DP dp[i][j]，别和本题混淆。
Manacher：把 O(n²) 优化到 O(n)，核心是维护「右边界最大的回文」及其对称中心，复用已知信息。
字符串匹配类（回文、子串、子序列）先问自己：中心？双指针？区间 DP？——建立这三选一的直觉。

难度：中等 | LeetCode 5 题 | 中心扩散模板

算法 - 反转字符串中的单词

Posted on 2024-09-11

1. 题目

给你一个字符串 s，反转其中单词的顺序并返回。单词是由非空格字符组成的最大子串，单词间由一个或多个空格分隔。返回的字符串中单词之间只用单个空格分隔，且不含前导或尾随空格。

示例:

输入: "the sky is blue"
输出: "blue is sky the"

输入: "  hello   world  "
输出: "world hello"

输入: "a good   example"
输出: "example good a"

2. 解题思路

要求处理多余空格，思路分两种：

2.1 内建 API 版（快速）

trim() 去首尾空格。
split(/\s+/) 按「一个或多个空白」切成单词数组（首尾已 trim，不会有空串）。
reverse() 反转数组。
join(" ") 用单空格连接。

优点：一行思路、代码短、面试先写它保底。缺点：依赖高级 API，没有体现手写能力。

2.2 双指针手写版（加分）

从右向左扫描：跳过空格 → 定位一个单词的右端与左端 → 截取单词追加到结果，单词间补一个空格。天然实现「逆序 + 单空格」。

时间复杂度：O(n)。
空间复杂度：O(n)（存放结果；若原地翻转则为 O(1)）。

若题目要求原地（C 风格字符数组），经典三步：整体反转 → 逐个单词再反转 → 压缩多余空格，做到 O(1) 额外空间。

3. TypeScript 实现

// 2.1 API 版
function reverseWords(s: string): string {
    return s.trim().split(/\s+/).reverse().join(" ");
}

// 2.2 双指针手写版（从右往左）
function reverseWordsTwoPointer(s: string): string {
    const res: string[] = [];
    let i = s.length - 1;

    while (i >= 0) {
        // 跳过空格
        if (s[i] === " ") {
            i--;
            continue;
        }
        // 定位单词左端
        let j = i;
        while (j >= 0 && s[j] !== " ") j--;
        // j+1 .. i 是一个单词
        res.push(s.slice(j + 1, i + 1));
        i = j; // 继续向左
    }

    return res.join(" ");
}

console.log(reverseWords("  hello   world  ")); // "world hello"
console.log(reverseWordsTwoPointer("a good   example")); // "example good a"

4. 面试延伸

正则 /\s+/ 的坑：若不用 trim 直接 split，首尾会产生空字符串元素，需 .filter(Boolean)。
原地版（186 题，字符数组）：整串 reverse + 每词 reverse + 移除多余空格，O(1) 空间，最能区分候选人。
关联：左旋转字符串（剑指 Offer 58-II） = 反转整体 + 反转各段，考察同一套「翻转」思想。
JS 里 String.prototype.reverse 不存在，别忘了 split("") 或数组中转，容易口误。
能顺手讨论「多个空格 / 首尾空格 / 空串」这些边界，是字符串题的基本素养。

难度：中等 | LeetCode 151 题 | 字符串与双指针

算法 - 螺旋矩阵 (Spiral Matrix)

Posted on 2024-08-22

1. 题目

给你一个 m × n 的矩阵 matrix，按照螺旋顺序返回矩阵中的所有元素（从外层到内层，顺时针）。

示例:

输入: [[1,2,3],
       [4,5,6],
       [7,8,9]]
输出: [1,2,3,6,9,8,7,4,5]

输入: [[1,2,3,4],
       [5,6,7,8],
       [9,10,11,12]]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

2. 解题思路

螺旋就是「右 → 下 → 左 → 上」四条边循环遍历，每走完一条边就把这条边界向内收缩一格。

维护四个边界：top、bottom、left、right。循环执行：

向左到右遍历第 top 行，然后 top++（这一行用完）。
从上到下遍历第 right 列，然后 right--。
若 top <= bottom，从右到左遍历第 bottom 行，然后 bottom--。
若 left <= right，从下到上遍历第 left 列，然后 left++。

关键：第 3、4 步在收缩后要再判断边界是否仍合法，否则单行/单列矩阵会重复遍历回去。

时间复杂度：O(m × n)，每个元素访问一次。
空间复杂度：O(1)（不计输出）。

3. TypeScript 实现

function spiralOrder(matrix: number[][]): number[] {
    const res: number[] = [];
    if (matrix.length === 0) return res;

    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // → 顶行
        for (let col = left; col <= right; col++) res.push(matrix[top][col]);
        top++;

        // ↓ 右列
        for (let row = top; row <= bottom; row++) res.push(matrix[row][right]);
        right--;

        // ← 底行（确保还有一行）
        if (top <= bottom) {
            for (let col = right; col >= left; col--) res.push(matrix[bottom][col]);
            bottom--;
        }

        // ↑ 左列（确保还有一列）
        if (left <= right) {
            for (let row = bottom; row >= top; row--) res.push(matrix[row][left]);
            left++;
        }
    }

    return res;
}

console.log(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));
// [1,2,3,6,9,8,7,4,5]

4. 面试延伸

生成螺旋矩阵 II（59 题）：反向操作，按螺旋顺序往空矩阵里填 1..n²，边界收缩逻辑复用。
方向数组写法：用 dirs = [[0,1],[1,0],[0,-1],[-1,0]] + 记录已访问 + 撞墙/撞已访问就转向，是更通用的「螺旋/蛇形」模板，扩展性强但需 O(mn) 的 visited。
模拟类题目没有算法难度，考的是边界严谨性和代码条理性，务必手推 1×n、n×1、1×1 三种退化用例。
相似题：旋转图像（48）、矩阵置零（73） 都在训练你在二维坐标下干净地操作边界。

难度：中等 | LeetCode 54 题 | 边界模拟

算法 - 二分查找（含左右边界版本）

Posted on 2024-07-03

1. 题目

给定一个升序整数数组 nums 和目标值 target：

基础版：若存在 target 返回其下标，否则返回 -1。
边界版：找出 target 在数组中的起始和结束位置（存在重复时）；不存在返回 [-1, -1]。要求 O(log n)。

示例:

nums = [5,7,7,8,8,10], target = 8
基础版: 返回 3（任一 8 的下标）
边界版: 返回 [3, 4]

nums = [5,7,7,8,8,10], target = 6
返回 [-1, -1]

2. 解题思路

二分最坑的是边界与死循环。用「左闭右闭 [left, right]」这一套统一写法最省心。

2.1 基础版

while (left <= right) {        // 区间非空的条件
    mid = left + ((right-left) >> 1)  // 防两数相加溢出
    if (nums[mid] === target) return mid
    else if (nums[mid] < target) left = mid + 1
    else right = mid - 1
}
return -1

2.2 边界版 = 两次「找第一个 >= / 第一个 >」

关键抽象成两个函数：

lowerBound(target)：第一个 >= target 的下标（左边界）。
upperBound(target)：第一个 > target 的下标（右边界的下一位）。

则 target 的区间是 [lowerBound, upperBound - 1]；若两者相等说明 target 不存在。

核心口诀：收缩时只要 nums[mid] >= target 就 right = mid（否则 left = mid + 1），最终 left 落在第一个满足条件的位置。注意此时 while (left < right) 且 right = mid（不减一），保持「找最左」不变量。

时间复杂度：O(log n)；空间 O(1)。

3. TypeScript 实现

// 基础版：精确匹配
function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1; // 左闭右闭

    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 找第一个 >= target 的下标（可能返回 nums.length）
function lowerBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length; // 左闭右开 [left, right)
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left = mid + 1;
        else right = mid; // mid 可能是答案，保留
    }
    return left;
}

// 找第一个 > target 的下标
function upperBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length;
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

function searchRange(nums: number[], target: number): number[] {
    const lo = lowerBound(nums, target);
    // lo 越界或值不等，说明不存在
    if (lo === nums.length || nums[lo] !== target) return [-1, -1];
    return [lo, upperBound(nums, target) - 1];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]

4. 面试延伸

两套写法别混用：left<=right / right=mid-1（闭合）与 left<right / right=mid（半开）各有约定，全程保持一致，中途换风格必死循环或漏元素。
旋转数组找 target（33/153）：判断哪半边有序再决定收缩方向，是二分的最高频变体。
求平方根 / 二分答案：把「在答案空间里二分」讲出来（找第一个满足条件的 x），体现你懂二分的本质是单调性。
溢出：JS 的 number 是双精度浮点，>>1 会把值转成 32 位整数，mid 溢出风险比 C++ 小，但写 left + (right-left)/2 仍是好习惯。
记住 lowerBound === upperBound 即「target 出现次数为 0」，upperBound - lowerBound 就是频次，一行搞定计数。

难度：中等 | LeetCode 34/704 题 | 边界处理基本功

算法 - 零钱兑换 (Coin Change)

Posted on 2024-06-18

1. 题目

给你一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算凑成总金额所需的最少的硬币个数。每种硬币可以无限使用。如果无法凑出，返回 -1。

示例:

输入: coins = [1, 2, 5], amount = 11
输出: 3  （11 = 5 + 5 + 1）

输入: coins = [2], amount = 3
输出: -1 （凑不出）

输入: coins = [1], amount = 0
输出: 0

2. 解题思路

这是完全背包求最少数量的经典题。贪心（每次取最大面额）在这里不成立（如 coins=[1,3,4], amount=6 贪心得 4+1+1=3 枚，最优是 3+3=2 枚），必须用 DP。

定义 dp[i] = 凑出金额 i 所需的最少硬币数。

转移：对于金额 i，枚举最后一枚用的硬币 c（c <= i），则

1	dp[i] = min(dp[i - c]) + 1

初始化：

dp[0] = 0（凑 0 需要 0 枚）。
其余 dp[i] = amount + 1（当作正无穷，因为最多也不会超过 amount 枚），或 Infinity。

最后若 dp[amount] > amount 说明没被更新过，返回 -1。

时间复杂度：O(amount × coins数)。
空间复杂度：O(amount)。

3. TypeScript 实现

function coinChange(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(amount + 1); // 视作 +∞
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3));        // -1
console.log(coinChange([1, 3, 4], 6));  // 2

4. 面试延伸

零钱兑换 II（518，凑法总数）：把 min+1 换成 dp[i] += dp[i-c]，且外层遍历硬币、内层遍历金额以保证组合不计顺序，是完全背包计数的标准写法。
完全背包 vs 0-1 背包：内层金额遍历方向决定「可重复用」——完全背包正序（能用多次），0-1 背包逆序（每枚只用一次）。这是背包问题的核心分水岭。
要输出具体用了哪些硬币：额外记录 choice[i] 前驱，最后回溯。
常见坑：求「最少」用 min，求「方法数」用「加法」；初始化 dp[0] 的含义要和题目对齐。
若问「为什么不用贪心」，一定要举 [1,3,4] 凑 6 的反例，这是本题最重要的理解点。

难度：中等 | LeetCode 322 题 | 完全背包基石