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;
}

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

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

    while (queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift()!;
            if (i === size - 1) res.push(node.val); // 本层最后一个
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return res;
}

function rightSideViewDFS(root: TreeNode | null): number[] {
    const res: number[] = [];

    const dfs = (node: TreeNode | null, depth: number) => {
        if (!node) return;
        // 该层尚未收集，则当前(最右优先)节点即右视图节点
        if (depth === res.length) res.push(node.val);
        dfs(node.right, depth + 1); // 先右
        dfs(node.left, depth + 1);  // 后左
    };

    dfs(root, 0);
    return res;
}

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];
    const used = new Array<boolean>(nums.length).fill(false);

    const backtrack = () => {
        if (path.length === nums.length) {
            res.push([...path]);   // 到达叶子才收集
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 同一条路径不能重复用同一个元素
            used[i] = true;
            path.push(nums[i]);

            backtrack();

            path.pop();
            used[i] = false;       // 撤销选择
        }
    };

    backtrack();
    return res;
}

console.log(permute([1, 2, 3]));

function permuteSwap(nums: number[]): number[][] {
    const res: number[][] = [];

    const dfs = (first: number) => {
        if (first === nums.length) {
            res.push([...nums]);
            return;
        }
        for (let i = first; i < nums.length; i++) {
            [nums[first], nums[i]] = [nums[i], nums[first]];
            dfs(first + 1);
            [nums[first], nums[i]] = [nums[i], nums[first]]; // 回溯
        }
    };

    dfs(0);
    return res;
}

function subsets(nums: number[]): number[][] {
    const res: number[][] = [];
    const path: number[] = [];

    const backtrack = (start: number) => {
        // 每个节点都是一个合法子集
        res.push([...path]);

        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);       // 选
            backtrack(i + 1);         // 只往后看，避免重复
            path.pop();               // 不选（撤销选择）
        }
    };

    backtrack(0);
    return res;
}

console.log(subsets([1, 2, 3]));
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

function subsetsIterative(nums: number[]): number[][] {
    let res: number[][] = [[]];

    for (const x of nums) {
        // 基于「本轮开始前」的子集扩张，不能边遍历边 push 同一数组
        res = [...res, ...res.map((set) => [...set, x])];
    }

    return res;
}

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

    for (let mask = 0; mask < 1 << n; mask++) {
        const subset: number[] = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push(nums[i]);
        }
        res.push(subset);
    }

    return res;
}

function maxArea(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let best = 0;

    while (l < r) {
        const h = Math.min(height[l], height[r]);
        best = Math.max(best, h * (r - l));

        // 移动较短的一边，才可能找到更大的面积
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }

    return best;
}

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

function curry(fn: Function) {
    return function curried(this: any, ...args: any[]): any {
        if (args.length >= fn.length) {
            return fn.apply(this, args);
        }
        return (...rest: any[]) => curried.apply(this, [...args, ...rest]);
    };
}

const add = (a: number, b: number, c: number) => a + b + c;
const curriedAdd = curry(add);
console.log(curriedAdd(1)(2)(3));   // 6
console.log(curriedAdd(1, 2)(3));   // 6

const _ = Symbol("placeholder");

function curryWithPlaceholder(fn: Function): any {
    const judge = (...args: any[]): any =>
        // 非占位符参数足够时执行
        args.length >= fn.length &&
        args.slice(0, fn.length).every((a) => a !== _)
            ? fn(...args.filter((a) => a !== _))
            : (arg: any, ...rest: any[]) => judge(...replace(args, arg), ...rest);

    // 用新传入的 arg 填补 args 中第一个占位符；没有则追加
    function replace(args: any[], arg: any): any[] {
        const idx = args.indexOf(_);
        if (idx !== -1 && arg !== _) {
            const copy = [...args];
            copy[idx] = arg;
            return copy;
        }
        return [...args, arg];
    }

    return judge;
}

const sum3 = (a: number, b: number, c: number) => a + b + c;
const c3 = curryWithPlaceholder(sum3);
console.log(c3(_, 2)(1)(3));   // 6
console.log(c3(1, _, 3)(2));   // 6
console.log(c3(1)(2)(3));      // 6

// 暴露占位符
curryWithPlaceholder._ = _;

function myInstanceof(left: any, right: any): boolean {
    // 原始值 / null / undefined 直接 false
    if (left === null || (typeof left !== "object" && typeof left !== "function")) {
        return false;
    }

    // 支持 Symbol.hasInstance（对齐原生优先级）
    const hasInstance = right[Symbol.hasInstance];
    if (typeof hasInstance === "function") {
        return !!hasInstance.call(right, left);
    }

    if (typeof right !== "function") {
        throw new TypeError("Right-hand side of 'instanceof' is not callable");
    }

    const proto = right.prototype; // 要找的目标
    let cursor = Object.getPrototypeOf(left);

    while (cursor !== null) {
        if (cursor === proto) return true;
        cursor = Object.getPrototypeOf(cursor); // 沿原型链上溯
    }

    return false;
}

// 测试
class Animal {}
class Dog extends Animal {}

console.log(myInstanceof(new Dog(), Dog));     // true
console.log(myInstanceof(new Dog(), Animal));  // true（继承链）
console.log(myInstanceof(new Dog(), Object));  // true
console.log(myInstanceof("str", String));      // false（原始值）
console.log(myInstanceof(new String("s"), String)); // true

// myCall
Function.prototype.myCall = function (this: Function, thisArg?: any, ...args: any[]): any {
    const ctx = thisArg == null ? globalThis : Object(thisArg);
    const key = Symbol("fn");
    (ctx as any)[key] = this; // this 即调用者函数
    const result = (ctx as any)[key](...args);
    delete (ctx as any)[key];
    return result;
};

// myApply
Function.prototype.myApply = function (this: Function, thisArg?: any, argsList?: any[]): any {
    const ctx = thisArg == null ? globalThis : Object(thisArg);
    const key = Symbol("fn");
    (ctx as any)[key] = this;
    const result = argsList
        ? (ctx as any)[key](...argsList)
        : (ctx as any)[key]();
    delete (ctx as any)[key];
    return result;
};

// myBind
Function.prototype.myBind = function (this: Function, thisArg?: any, ...boundArgs: any[]): Function {
    const original = this;

    // 用一个空函数承接原型链，保证 new bound() 能拿到 original.prototype
    const bound = function (this: any, ...callArgs: any[]): any {
        const allArgs = [...boundArgs, ...callArgs]; // 柯里化：预置参数在前
        // 被 new 调用时 this 是新建实例，忽略绑定的 thisArg
        const wasNew = new.target !== undefined;
        if (wasNew) {
            return new (original as any)(...allArgs);
        }
        return original.apply(thisArg, allArgs);
    };

    if (original.prototype) {
        bound.prototype = Object.create(original.prototype);
    }
    return bound;
};

// 测试
const obj = { name: "jack" };
function greet(this: any, a: string, b: string) {
    return `${a} ${this.name} ${b}`;
}

console.log(greet.myCall(obj, "hi", "!"));          // "hi jack !"
console.log(greet.myApply(obj, ["hello", "?"]));    // "hello jack ?"

const boundGreet = greet.myBind(obj, "hey");
console.log(boundGreet("there"));                   // "hey jack there"

function deepClone<T>(source: T, cache = new WeakMap<object, any>()): T {
    // 原始值 / null / 函数：直接返回
    if (source === null || typeof source !== "object") {
        return source;
    }

    // 命中缓存：处理循环引用的关键
    if (cache.has(source as object)) {
        return cache.get(source as object);
    }

    // Date
    if (source instanceof Date) {
        return new Date(source.getTime()) as unknown as T;
    }

    // RegExp
    if (source instanceof RegExp) {
        return new RegExp(source.source, source.flags) as unknown as T;
    }

    // Map
    if (source instanceof Map) {
        const result = new Map();
        cache.set(source as object, result);
        for (const [key, value] of source.entries()) {
            result.set(deepClone(key, cache), deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // Set
    if (source instanceof Set) {
        const result = new Set();
        cache.set(source as object, result);
        for (const value of source.values()) {
            result.add(deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // 数组
    if (Array.isArray(source)) {
        const result: any[] = [];
        cache.set(source as object, result);
        for (let i = 0; i < source.length; i++) {
            result[i] = deepClone(source[i], cache);
        }
        return result as unknown as T;
    }

    // 普通对象（含 Symbol key）
    const result = Object.create(Object.getPrototypeOf(source));
    cache.set(source as object, result); // 先建立映射再递归，才能扛住循环引用
    for (const key of Reflect.ownKeys(source)) {
        const descriptor = Object.getOwnPropertyDescriptor(source, key)!;
        if (descriptor.enumerable) {
            result[key] = deepClone((source as any)[key], cache);
        } else {
            Object.defineProperty(result, key, descriptor);
        }
    }
    return result as T;
}

// 测试
const obj: any = { name: "jack", tags: ["ts", "algo"], born: new Date(0) };
obj.self = obj;
const copy = deepClone(obj);
console.log(copy.self === copy);        // true
console.log(copy.tags !== obj.tags);    // true（独立副本）