JS 算法题之 leetcode(11~20)

这次的十道题目都比较容易，我们简单过一下
以下题目均来源乐扣（leetcode）

盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解答

这题作为中等难度的题目，比较容易，而且层级不深，我们直接遍历两层，比较得到结果就好

var maxFunc = (a, b) => {return a >= b ? a : b;}

var minFunc = (a, b) => {return a <= b ? a : b;}

var maxArea = function(height) {
    let max = 0;

    for(let i = 0; i < height.length - 1; i++){for(let j = i + 1; j < height.length ; j++){let temp = (j - i) * minFunc(height[i], height[j]);
            max = maxFunc(max, temp);
        }
    }

    return max;
};

整数转罗马数字

题目描述

罗马数字包含以下七种字符：I，V，X，L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II，即为两个并列的 1。12 写做 XII，即为 X + II。27 写做  XXVII, 即为 XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例

输入: 3
输出: "III"

输入: 4
输出: "IV"

输入: 9
输出: "IX"

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答

这题不难，我们只需将罗马数字从大到小逐个处理，取余取模，然后判断就好

var intToRoman = function(num) {
    let divisor = 0, remainder = 0, str = '';
    // M,1000
    divisor = Math.floor(num / 1000);
    remainder = num % 1000;
    while(divisor){
        str += 'M';
        divisor--;
    }
    if(remainder >= 900){
        str += 'CM';
        remainder -= 900;
    }
    // D,500
    divisor = Math.floor(remainder / 500);
    remainder = remainder % 500;
    while(divisor){
        str += 'D';
        divisor--;
    }
    if(remainder >= 400){
        str += 'CD';
        remainder -= 400;
    }
    // C,100
    divisor = Math.floor(remainder / 100);
    remainder = remainder % 100;
    while(divisor){
        str += 'C';
        divisor--;
    }
    if(remainder >= 90){
        str += 'XC';
        remainder -= 90;
    }
    // L,50
    divisor = Math.floor(remainder / 50);
    remainder = remainder % 50;
    while(divisor){
        str += 'L';
        divisor--;
    }
    if(remainder >= 40){
        str += 'XL';
        remainder -= 40;
    }
    // X,10
    divisor = Math.floor(remainder / 10);
    remainder = remainder % 10;
    while(divisor){
        str += 'X';
        divisor--;
    }
    if(remainder >= 9){
        str += 'IX';
        remainder -= 9;
    }
    // V,5
    divisor = Math.floor(remainder / 5);
    remainder = remainder % 5;
    while(divisor){
        str += 'V';
        divisor--;
    }
    if(remainder >= 4){
        str += 'IV';
        remainder -= 4;
    }
    // I,1
    divisor = remainder;
    while(divisor){
        str += 'I';
        divisor--;
    }

    return str;
};

罗马数字转整数

题目描述

罗马数字包含以下七种字符: I，V，X，L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II，即为两个并列的 1。12 写做 XII，即为 X + II。27 写做  XXVII, 即为 XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例

输入: "III"
输出: 3

输入: "IV"
输出: 4

输入: "IX"
输出: 9

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答

这题也不难，对字符串递归处理，若前两个字符符合 4，9，40，90，400，900，则两个一起处理，否则就处理一个，剩下的继续递归。

var romanToInt = function(s) {if(s.length == 0){return 0;}
    else if(s.lenght == 1){switch(s){
            case "I":
                return 1;
            case "V":
                return 5;
            case "X":
                return 10;
            case "L":
                return 50;
            case "C":
                return 100;
            case "D":
                return 500;
            case "M":
                return 1000;
        }
    }
    else{let str = s.substring(0, 2);
        if(str == "IV" || str == "IX" || str == "XL" || str == "XC" || str == "CD" || str == "CM"){switch(str){
                case "IV":
                    return 4 + romanToInt(s.slice(2));
                case "IX":
                    return 9 + romanToInt(s.slice(2));
                case "XL":
                    return 40 + romanToInt(s.slice(2));
                case "XC":
                    return 90 + romanToInt(s.slice(2));
                case "CD":
                    return 400 + romanToInt(s.slice(2));
                case "CM":
                    return 900 + romanToInt(s.slice(2));
            }
        }
        else{switch(s[0]){
                case "I":
                    return 1 + romanToInt(s.slice(1));
                case "V":
                    return 5 + romanToInt(s.slice(1));
                case "X":
                    return 10 + romanToInt(s.slice(1));
                case "L":
                    return 50 + romanToInt(s.slice(1));
                case "C":
                    return 100 + romanToInt(s.slice(1));
                case "D":
                    return 500 + romanToInt(s.slice(1));
                case "M":
                    return 1000 + romanToInt(s.slice(1));
            }
        }
    }
};

最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
说明:
所有输入只包含小写字母 a-z。

示例

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

解答

这题不难，我们直接遍历数组的字符串的每一个字符，相同则添加到前缀，否则返回

var longestCommonPrefix = function(strs) {if(strs.length == 0){return "";}
    if(strs.length == 1){return strs[0];
    }

    let minLen = -1, prefix = '', char ='';
    strs.forEach(ele => {if(minLen == -1){minLen = ele.length;}
        else{minLen = ele.length < minLen ? ele.length : minLen;}
    });
    if(minLen == 0){return "";}

    for(let i = 0; i < minLen; i++){char = strs[0][i];
        // 用于标记该字符是否为前缀
        let flag = true;
        for(let j = 1; j < strs.length; j++){if(strs[j][i] != char){flag = false;}
        }
        if(flag){prefix += char;}
        else{return prefix;}
    }
    return prefix;
};

三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],
  [-1, -1, 2]
]

解答

这题我们才用排序 + 双指针的思路来做，遍历排序后的数组，定义指针 l 和 r, 分别从当前遍历元素的下一个元素和数组的最后一个元素往中间靠拢，计算结果跟目标对比。

var threeSum = function(nums) {if(nums.length < 3){return [];
    }

    let res = [];
    // 排序
    nums.sort((a, b) => a - b);
    for(let i = 0; i < nums.length; i++){if(i > 0 && nums[i] == nums[i-1]){
            // 去重
            continue;
        }
        if(nums[i] > 0){
            // 若当前元素大于 0，则三元素相加之后必定大于 0
            break;
        }
        // l 为左下标，r 为右下标
        let l = i + 1; r = nums.length - 1;
        while(l<r){let sum = nums[i] + nums[l] + nums[r];
            if(sum == 0){res.push([nums[i], nums[l], nums[r]]);
                while(l < r && nums[l] == nums[l+1]){l++}
                while(l < r && nums[r] == nums[r-1]){r--;}
                l++;
                r--;
            }
            else if(sum < 0){l++;}
            else if(sum > 0){r--;}
        }
    }

    return res;
};

最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解答

这题跟上面那题思路一致，也是排序 + 双指针，不过需要多维护一个差值作比较来获取最小差距的值。

var threeSumClosest = function(nums, target) {if(nums.length == 0){return 0;}
    else if(nums.length < 4){return nums.reduce((a, b) => a + b)
    }
    else {
        let min = -1, res;
        nums.sort((a, b) => a - b);
        for(let i = 0; i < nums.length - 2; i++){if(i > 0 && nums[i] == nums[i - 1]){
                // 去重
                continue;
            }
            let l = i + 1, r = nums.length - 1;
            while(l < r){let sum = nums[i] + nums[l] + nums[r];
                if(sum == target){
                    // 差距为 0，直接出结果
                    return sum;
                }
                else if(sum > target){if(min == -1){
                        min = sum - target;
                        res = sum;
                    }
                    else if(sum - target < min){
                        min = sum - target;
                        res = sum;
                    }
                    r--;
                }
                else if(sum < target){if(min == -1){
                        min = target - sum;
                        res = sum;
                    }
                    else if(target - sum< min){
                        min = target - sum;
                        res = sum;
                    }
                    l++;
                }
            }
        }
        return res;
    }
};

电话号码的字母组合

题目描述

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

示例

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

解答

这题简单，直接遍历字符，然后数组相加就好，不用担心复杂度高，因为基数也就 3 或者 4

const numMap = {2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z']
}

var letterCombinations = function(digits) {if(digits.length == 0){return []
    }
    let res = [...numMap[digits[0]]];
    for(let i = 1; i < digits.length; i++){let temp = [];
        for(let j = 0; j < res.length; j++){for(let k = 0; k < numMap[digits[i]].length; k++){temp.push(res[j]+numMap[digits[i]][k]);
            }
        }
        res = [...temp]
    }
    return res;
};

四数之和

题目描述

给定一个包含 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]
]

解答

这题跟三数之和差不多，思路一致，不过这次是两层循环 + 两指针
var fourSum = function(nums, target) {

if(nums.length < 4){return [];
}
let res = [];
nums.sort((a, b) => a - b);
for(let i = 0; i < nums.length - 3; i++){if(i > 0 && nums[i] == nums[i-1]){continue;}
    for(let j = i + 1; j < nums.length - 2; j++){if(j > i + 1 && nums[j] == nums[j-1]){continue;}
        let l = j + 1, r = nums.length - 1;
        while(l < r){let sum = nums[i] + nums[j] + nums[l] + nums[r];
            if(sum == target){res.push([nums[i], nums[j], nums[l], nums[r]])
                while(l<r && nums[l] == nums[l+1]){l++;}
                while(l<r && nums[r] == nums[r-1]){r--;}
                l++;
                r--;
            }
            else if(sum < target){l++;}
            else if(sum > target){r--;}
        }
    }
}
return res;

};

删除链表的倒数第 N 个节点

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

说明：
给定的 n 保证是有效的。

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

解答

这题不难，可以直接遍历一次，获取链表的长度，然后再次遍历到对应的节点，直接删除
也可以遍历一次，让单向链表成为双向链表，然后直接删除也可，本文采取第二种做法

var removeNthFromEnd = function(head, n) {
    let cur = head;
    while(cur.next){
        cur.next.prev = cur;
        cur = cur.next;
    }
    if(n == 1){
        // 删除最后一个节点
        if(!cur.prev){return null;}
        else{
            cur.prev.next = null;
            return head;
        }
    }
    while(n > 0 && cur){if(n == 1){if(!cur.prev){
                // 删除第一个节点
                cur.next.prev = null;
                return cur.next
            }
            else{
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return head;
            }
        }
        cur = cur.prev;
        n--;
    }
};

有效的括号

题目描述

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

解答

这题简单，直接维护一个堆栈，遍历字符串，若是左半边就入栈，右半边就出栈，出栈的元素跟遍历的字符串能匹配则继续，否则 return false

var isValid = function(s) {if(s.length == 0){return true;}
    let stack = [];
    for(let i = 0; i < s.length; i++){if(s[i] == "(" || s[i] == "{"  || s[i] == "["){
            // 左括号，入栈
            stack.push(s[i]);
        }
        else if(s[i] == ")" || s[i] == "}" || s[i] == "]"){let char = stack.pop();
            if((char == "(" && s[i] == ")") || (char == "{" && s[i] == "}") || (char == "[" && s[i] == "]")){continue}
            else{return false}
        }
    }
    if(stack.length == 0){return true}
    else{return false;}
};

小结

弟弟才疏学浅，有不正确或者更好的做法，希望各位大神纠正和建议，我会持续更新。