LeetCode Day 9

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

/**

 * @param {string} digits

 * @return {string[]}

 */

var letterCombinations = function (digits) {

    let result = [];

    if (digits && digits.length > 0) {

        let letterMap = [

            "",//0

            "",//1

            "abc",//2

            "def",//3

            "ghi",//4

            "jkl",//5

            "mno",//6

            "pqrs",//7

            "tuv",//8

            "wxyz"//9

        ]

        for (let c of digits) {

            let digit = c - '0';

            if (digit === 0 || digit === 1) continue;

            let letter = letterMap[digit];

            if (result.length === 0) result = letter.split('');

            else {

                let arr = result.concat();

                result = [];

                for (let l of letter) {

                    for (let i = 0, lens = arr.length; i < lens; i++) {

                        result.push(arr[i] + l);

                    }

                }

            }

        }

    }

    return result;

};

console.log(letterCombinations("23"));

LeetCode0018

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
例如：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

套用求三数和的思路，对于nums[0...n-3]，求出一个threeSum(nums[1...n-1], target-nums[0...n-3])的值。
剩下的写法就跟求threeSum一致了，需要注意的是每个位置的去重处理。

/**

 * @param {number[]} nums

 * @param {number} target

 * @return {number[][]}

 */

var fourSum = function (nums, target) {

    if (nums === undefined) return [];

    let lens = nums.length;

    if (lens < 4) return [];

    let first = 0, second, head, tail;

    let result = [];

    nums.sort((a, b) => a - b);

    //console.log(nums);

    while (first < lens - 3) {

        second = first + 1;

        while (second < lens - 2) {

            head = second + 1;

            tail = lens - 1;

            while (head < tail) {

                let sum = nums[first] + nums[second] + nums[head] + nums[tail];

                if (sum === target) {

                    result.push([nums[first], nums[second], nums[head], nums[tail]]);

                    while (nums[head] === nums[head + 1])++head;

                    while (nums[tail] === nums[tail - 1])--tail;

                    head++;

                    tail--;

                } else if (sum > target) {

                    tail--;

                }

                else {

                    head++;

                }

            }

            second++;

            while (nums[second] === nums[second - 1]) second++;

        }

        first++;

        while (nums[first] === nums[first - 1]) first++;

    }

    return result;

};

console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

// console.log(fourSum([-3, -2, -1, 0, 0, 1, 2, 3], 0));

// console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

巴特西

LeetCode Day 9

思路

最新文章

热门文章