function debounce<T extends (...args: any[]) => void>(
    fn: T,
    wait: number
): ((...args: Parameters<T>) => void) & { cancel: () => void } {
    let timer: ReturnType<typeof setTimeout> | null = null;

    const debounced = function (this: ThisParameterType<T>, ...args: Parameters<T>) {
        if (timer !== null) clearTimeout(timer);
        timer = setTimeout(() => {
            timer = null;
            fn.apply(this, args);
        }, wait);
    };

    debounced.cancel = () => {
        if (timer !== null) {
            clearTimeout(timer);
            timer = null;
        }
    };

    return debounced;
}

function debounceImmediate<T extends (...args: any[]) => void>(
    fn: T,
    wait: number,
    immediate = false
) {
    let timer: ReturnType<typeof setTimeout> | null = null;

    return function (this: any, ...args: Parameters<T>) {
        // 用 timer 是否存在判断「是否处于冷却」
        if (timer !== null) clearTimeout(timer);

        if (immediate) {
            const callNow = timer === null; // 首次或冷却结束
            timer = setTimeout(() => {
                timer = null; // 重新武装
            }, wait);
            if (callNow) fn.apply(this, args);
        } else {
            timer = setTimeout(() => {
                timer = null;
                fn.apply(this, args);
            }, wait);
        }
    };
}

// 用法
const onSearch = debounce((kw: string) => console.log("fetch:", kw), 300);
window.addEventListener("input", () => onSearch("abc"));
// 组件卸载 / 不再需要时：
onSearch.cancel();

type Nested = number | Nested[];

function flatten(arr: Nested[]): number[] {
    return arr.reduce<number[]>(
        (acc, cur) =>
            acc.concat(Array.isArray(cur) ? flatten(cur) : cur),
        []
    );
}

function flattenDepth(arr: Nested[], depth = 1): number[] {
    const res: number[] = [];

    const dfs = (input: Nested[], d: number) => {
        for (const item of input) {
            if (Array.isArray(item) && d > 0) {
                dfs(item, d - 1); // 下钻一层，深度预算 -1
            } else {
                res.push(item as number);
            }
        }
    };

    dfs(arr, depth);
    return res;
}

function* genFlat(arr: Nested[]): Generator<number> {
    for (const item of arr) {
        if (Array.isArray(item)) yield* genFlat(item);
        else yield item;
    }
}

const flattenGen = (arr: Nested[]): number[] => [...genFlat(arr)];

// 测试
console.log(flatten([1, [2, [3, [4]], 5]]));       // [1,2,3,4,5]
console.log(flattenDepth([1, [2, [3]]], 1));       // [1,2,[3]] -> [1,2,3 保留]
console.log(flattenDepth([1, [2, [3, [4]]], 5], Infinity)); // [1,2,3,4,5]

function quickSortSimple(nums: number[]): number[] {
    if (nums.length <= 1) return nums;

    const pivot = nums[Math.floor(nums.length / 2)];
    const left: number[] = [];
    const mid: number[] = [];
    const right: number[] = [];

    for (const x of nums) {
        if (x < pivot) left.push(x);
        else if (x === pivot) mid.push(x);
        else right.push(x);
    }

    return [...quickSortSimple(left), ...mid, ...quickSortSimple(right)];
}

function quickSort(nums: number[], lo = 0, hi = nums.length - 1): number[] {
    if (lo >= hi) return nums;

    const p = partition(nums, lo, hi);
    quickSort(nums, lo, p - 1);
    quickSort(nums, p + 1, hi);
    return nums;
}

function partition(nums: number[], lo: number, hi: number): number {
    // 随机化 pivot，避免有序数据退化
    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; // i 指向「小于区」的下一个位置

    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]]; // pivot 归位
    return i;
}

// 测试
console.log(quickSort([5, 2, 9, 1, 5, 6])); // [1,2,5,5,6,9]

function merge(intervals: number[][]): number[][] {
    if (intervals.length === 0) return [];

    // 按左端点升序
    intervals.sort((a, b) => a[0] - b[0]);

    const res: number[][] = [];

    for (const cur of intervals) {
        const last = res[res.length - 1];

        // 无结果 或 与上一个不重叠 -> 开新区间
        if (!last || cur[0] > last[1]) {
            res.push([...cur]);
        } else {
            // 重叠 -> 合并，取右端点较大者
            last[1] = Math.max(last[1], cur[1]);
        }
    }

    return res;
}

// 测试
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1,6],[8,10],[15,18]]
console.log(merge([[1, 4], [4, 5]])); // [[1,5]]
console.log(merge([[1, 10], [2, 3]])); // [[1,10]]

function levelOrder(root: TreeNode | null): number[][] {
    if (root === null) return [];

    const res: number[][] = [];
    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const level: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        res.push(level);
    }

    return res;
}

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}

// DFS 递归
function maxDepth(root: TreeNode | null): number {
    if (root === null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS 层序
function maxDepthBFS(root: TreeNode | null): number {
    if (root === null) return 0;

    const queue: TreeNode[] = [root];
    let depth = 0;

    while (queue.length > 0) {
        const levelSize = queue.length; // 锁定当前层节点数
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        depth++; // 完成一层
    }

    return depth;
}

function isValid(s: string): boolean {
    const pairs: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    const stack: string[] = [];

    for (const ch of s) {
        // 右括号：栈顶必须是对应的左括号
        if (ch in pairs) {
            const top = stack.pop(); // 空数组 pop 返回 undefined，天然处理空栈
            if (top !== pairs[ch]) return false;
        } else {
            // 左括号：入栈
            stack.push(ch);
        }
    }

    return stack.length === 0;
}

// 测试
console.log(isValid("{[]}")); // true
console.log(isValid("([)]")); // false
console.log(isValid("("));    // false

class LRUCache {
    private map = new Map<number, number>();
    constructor(private capacity: number) {}

    get(key: number): number {
        if (!this.map.has(key)) return -1;
        const value = this.map.get(key)!;
        // 删除后重新插入 = 移动到最新（Map 尾部为最近使用）
        this.map.delete(key);
        this.map.set(key, value);
        return value;
    }

    put(key: number, value: number): void {
        if (this.map.has(key)) {
            this.map.delete(key);
        } else if (this.map.size >= this.capacity) {
            // 删除第一个 key，即最久未使用（队首）
            const oldest = this.map.keys().next().value!;
            this.map.delete(oldest);
        }
        this.map.set(key, value);
    }
}

interface DLinkedNode {
    key: number;
    value: number;
    prev: DLinkedNode | null;
    next: DLinkedNode | null;
}

class LRUCacheAdvanced {
    private map = new Map<number, DLinkedNode>();
    private size = 0;
    // 哨兵节点，避免大量 null 判断
    private head: DLinkedNode = { key: 0, value: 0, prev: null, next: null };
    private tail: DLinkedNode = { key: 0, value: 0, prev: null, next: null };

    constructor(private capacity: number) {
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    get(key: number): number {
        const node = this.map.get(key);
        if (!node) return -1;
        this.moveToHead(node); // 命中即刷新为最新
        return node.value;
    }

    put(key: number, value: number): void {
        const node = this.map.get(key);
        if (node) {
            node.value = value;
            this.moveToHead(node);
            return;
        }

        const newNode: DLinkedNode = { key, value, prev: null, next: null };
        this.map.set(key, newNode);
        this.addToHead(newNode);
        this.size++;

        if (this.size > this.capacity) {
            const removed = this.removeTail(); // 淘汰最旧
            this.map.delete(removed.key);
            this.size--;
        }
    }

    private addToHead(node: DLinkedNode): void {
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next!.prev = node;
        this.head.next = node;
    }

    private removeNode(node: DLinkedNode): void {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }

    private moveToHead(node: DLinkedNode): void {
        this.removeNode(node);
        this.addToHead(node);
    }

    private removeTail(): DLinkedNode {
        const node = this.tail.prev!;
        this.removeNode(node);
        return node;
    }
}

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function mergeTwoLists(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const dummy = new ListNode(-1);
    let curr = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    // 接上剩余部分（最多一条链表还有货）
    curr.next = l1 !== null ? l1 : l2;

    return dummy.next;
}

// 递归写法（更短，栈空间 O(m+n)）
function mergeTwoListsRecursive(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    if (l1 === null) return l2;
    if (l2 === null) return l1;

    if (l1.val <= l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

// 迭代
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;

    while (curr !== null) {
        const nextTemp = curr.next; // 1. 暂存后继
        curr.next = prev;           // 2. 反转指针
        prev = curr;                // 3. prev 前进
        curr = nextTemp;            // 4. curr 前进
    }

    return prev;
}

// 递归
function reverseListRecursive(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;

    const newHead = reverseListRecursive(head.next);
    head.next.next = head; // 让后继指回自己
    head.next = null;      // 断开原指针，避免环
    return newHead;
}