LeetCode 热题 100 通用解题策略

function backtrack(choices, path, used) {
    // 终止条件：找到一个完整解
    if (path.length === choices.length) {
        result.push([...path]); 
        return;
    }
    
    // 遍历所有选择
    for (let i = 0; i < choices.length; i++) {
        if (used[i]) continue; // 剪枝：跳过已用元素
        used[i] = true;       // 做选择
        path.push(choices[i]);
        backtrack(choices, path, used); // 递归下一层
        path.pop();            // 撤销选择
        used[i] = false;
    }
}

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
};

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++; // 去重
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
};

var climbStairs = function(n) {
    if (n <= 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
};

var rob = function(nums) {
    let prev = 0, curr = 0;
    for (const num of nums) {
        [prev, curr] = [curr, Math.max(curr, prev + num)];
    }
    return curr;
};

var reverseList = function(head) {
    let prev = null, curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

var mergeTwoLists = function(l1, l2) {
    const dummy = new ListNode(-1);
    let curr = dummy;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 || l2;
    return dummy.next;
};

var maxDepth = function(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

var levelOrder = function(root) {
    if (!root) return [];
    const result = [], queue = [root];
    while (queue.length) {
        const level = [], size = queue.length;
        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);
        }
        result.push(level);
    }
    return result;
};

var permute = function(nums) {
    const result = [];
    const backtrack = (path, used) => {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push(nums[i]);
            backtrack(path, used);
            path.pop();
            used[i] = false;
        }
    };
    backtrack([], []);
    return result;
};

var combinationSum = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const backtrack = (start, path, sum) => {
        if (sum === target) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break; // 剪枝
            path.push(candidates[i]);
            backtrack(i, path, sum + candidates[i]);
            path.pop();
        }
    };
    backtrack(0, [], 0);
    return result;
};