function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    dp[0][0] = grid[0][0];
    for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])); // 7

function minPathSumOpt(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(n).fill(0);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) dp[j] = grid[0][0];
            else if (i === 0) dp[j] = dp[j - 1] + grid[i][j];       // 第一行
            else if (j === 0) dp[j] = dp[j] + grid[i][j];           // 第一列，dp[j] 仍是上一行值
            else dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1];
}

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

function isValidBST(root: TreeNode | null): boolean {
    const check = (node: TreeNode | null, min: number, max: number): boolean => {
        if (!node) return true;
        if (node.val <= min || node.val >= max) return false;
        return (
            check(node.left, min, node.val) &&
            check(node.right, node.val, max)
        );
    };

    return check(root, -Infinity, Infinity);
}

function isValidBSTInorder(root: TreeNode | null): boolean {
    const stack: TreeNode[] = [];
    let cur = root;
    let prev = -Infinity;

    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;         // 一路向左
        }
        cur = stack.pop()!;
        if (cur.val <= prev) return false; // 非严格递增
        prev = cur.val;
        cur = cur.right;
    }

    return true;
}

function decodeString(s: string): string {
    const numStack: number[] = [];
    const strStack: string[] = [];
    let curStr = "";
    let num = 0;

    for (const ch of s) {
        if (ch >= "0" && ch <= "9") {
            num = num * 10 + Number(ch);      // 多位数字
        } else if (ch === "[") {
            numStack.push(num);               // 保存本层重复次数
            strStack.push(curStr);            // 保存进入括号前的字符串
            curStr = "";
            num = 0;
        } else if (ch === "]") {
            const k = numStack.pop()!;
            const prev = strStack.pop()!;
            curStr = prev + curStr.repeat(k); // 内层展开并拼接外层
        } else {
            curStr += ch;                      // 普通字母
        }
    }

    return curStr;
}

console.log(decodeString("3[a2[c]]")); // accaccacc

function trap(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let water = 0;

    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) {
                leftMax = height[l];       // 新的左挡板
            } else {
                water += leftMax - height[l]; // 填补凹处
            }
            l++;
        } else {
            if (height[r] >= rightMax) {
                rightMax = height[r];
            } else {
                water += rightMax - height[r];
            }
            r--;
        }
    }

    return water;
}

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6

function trapDP(height: number[]): number {
    const n = height.length;
    if (n === 0) return 0;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);

    let water = 0;
    for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];

    return water;
}

class MinStack {
    private data: number[] = [];
    private minStack: number[] = [];

    push(val: number): void {
        this.data.push(val);
        const curMin = this.minStack.length
            ? this.minStack[this.minStack.length - 1]
            : val;
        this.minStack.push(Math.min(val, curMin));
    }

    pop(): void {
        this.data.pop();
        this.minStack.pop();
    }

    top(): number {
        return this.data[this.data.length - 1];
    }

    getMin(): number {
        return this.minStack[this.minStack.length - 1];
    }
}

function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const deque: number[] = []; // 存下标，对应值单调递减
    const res: number[] = [];

    for (let i = 0; i < n; i++) {
        // 1. 队头过期（滑出窗口）
        if (deque.length && deque[0] <= i - k) deque.shift();

        // 2. 队尾所有 <= 当前值的元素失去意义，弹出
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        // 3. 当前下标入队
        deque.push(i);

        // 4. 窗口形成后收集队头最大值
        if (i >= k - 1) res.push(nums[deque[0]]);
    }

    return res;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3,3,5,5,6,7]

function addStrings(num1: string, num2: string): string {
    let i = num1.length - 1;
    let j = num2.length - 1;
    let carry = 0;
    const res: string[] = [];

    while (i >= 0 || j >= 0 || carry > 0) {
        const d1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0; // '0'.charCodeAt = 48
        const d2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0;
        const sum = d1 + d2 + carry;

        res.push(String(sum % 10));
        carry = Math.floor(sum / 10);

        i--;
        j--;
    }

    return res.reverse().join("");
}

console.log(addStrings("999", "1")); // "1000"

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        // 只要 nums[i] 在 [1,n] 且没归位，就把它换到 nums[i]-1 处
        while (
            nums[i] > 0 &&
            nums[i] <= n &&
            nums[nums[i] - 1] !== nums[i]
        ) {
            const target = nums[i] - 1;
            [nums[i], nums[target]] = [nums[target], nums[i]];
        }
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }

    return n + 1; // 1..n 全在，答案为 n+1
}

console.log(firstMissingPositive([3, 4, -1, 1])); // 2

function hammingDistance(x: number, y: number): number {
    let n = x ^ y;
    let count = 0;
    while (n) {
        n = n & (n - 1); // 抹掉最低位的 1
        count++;
    }
    return count;
}

console.log(hammingDistance(1, 4)); // 2

const hammingDistanceBitCount = (x: number, y: number): number =>
    (x ^ y).toString(2).split("0").join("").length;
// 或 (x ^ y).toString(2).match(/1/g)?.length ?? 0

function totalHammingDistance(nums: number[]): number {
    let total = 0;
    const n = nums.length;

    for (let i = 0; i < 32; i++) {
        let ones = 0;
        for (const x of nums) {
            ones += (x >>> i) & 1;
        }
        total += ones * (n - ones); // 该位 1 与 0 的两两配对数
    }

    return total;
}

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

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    const queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const size = queue.length;
        const level: number[] = [];

        for (let i = 0; i < size; 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(leftToRight ? level : level.reverse());
        leftToRight = !leftToRight; // 下一层方向翻转
    }

    return res;
}

function zigzagLevelOrderDeque(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    let queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const level: number[] = [];
        const next: TreeNode[] = [];

        for (const node of queue) {
            leftToRight ? level.push(node.val) : level.unshift(node.val);
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }

        res.push(level);
        queue = next;
        leftToRight = !leftToRight;
    }

    return res;
}