JS算法題之leetcode(11~20)

CoderDock 發(fā)布于2019-08-26 10:46 / 1734人閱讀

摘要：給定一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。字符數(shù)值例如，羅馬數(shù)字寫(xiě)做，即為兩個(gè)并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。注意空字符串可被認(rèn)為是有效字符串。

JS算法題之leetcode(11~20)

這次的十道題目都比較容易，我們簡(jiǎn)單過(guò)一下
以下題目均來(lái)源樂(lè)扣（leetcode）

盛最多水的容器 題目描述

給定 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)?(i,?ai) 。在坐標(biāo)內(nèi)畫(huà) n 條垂直線(xiàn)，垂直線(xiàn) i?的兩個(gè)端點(diǎn)分別為?(i,?ai) 和 (i, 0)。找出其中的兩條線(xiàn)，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。

說(shuō)明：你不能傾斜容器，且?n?的值至少為 2。

圖中垂直線(xiàn)代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為?49。

示例

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

解答

這題作為中等難度的題目，比較容易，而且層級(jí)不深，我們直接遍歷兩層，比較得到結(jié)果就好

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

整數(shù)轉(zhuǎn)羅馬數(shù)字 題目描述

羅馬數(shù)字包含以下七種字符：?I，?V，?X，?L，C，D?和?M。

字符          數(shù)值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，羅馬數(shù)字 2 寫(xiě)做?II?，即為兩個(gè)并列的 1。12 寫(xiě)做?XII?，即為?X?+?II?。 27 寫(xiě)做??XXVII, 即為?XX?+?V?+?II?。

通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫(xiě)做?IIII，而是?IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為?IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：

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

給定一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。輸入確保在 1?到 3999 的范圍內(nèi)。

示例

輸入: 3
輸出: "III"

輸入: 4
輸出: "IV"

輸入: 9
輸出: "IX"

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

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

解答

這題不難，我們只需將羅馬數(shù)字從大到小逐個(gè)處理，取余取模，然后判斷就好

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

羅馬數(shù)字轉(zhuǎn)整數(shù) 題目描述

羅馬數(shù)字包含以下七種字符:?I，?V，?X，?L，C，D?和?M。

字符          數(shù)值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，羅馬數(shù)字 2 寫(xiě)做?II?，即為兩個(gè)并列的 1。12 寫(xiě)做?XII?，即為?X?+?II?。 27 寫(xiě)做??XXVII, 即為?XX?+?V?+?II?。

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

給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1?到 3999 的范圍內(nèi)。

示例

輸入: "III"
輸出: 3

輸入: "IV"
輸出: 4

輸入: "IX"
輸出: 9

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

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

解答

這題也不難，對(duì)字符串遞歸處理，若前兩個(gè)字符符合4，9，40，90，400，900，則兩個(gè)一起處理，否則就處理一個(gè)，剩下的繼續(xù)遞歸。

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

最長(zhǎng)公共前綴 題目描述

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。
說(shuō)明:
所有輸入只包含小寫(xiě)字母 a-z 。

示例

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

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

解答

這題不難，我們直接遍歷數(shù)組的字符串的每一個(gè)字符，相同則添加到前綴，否則返回

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];
        // 用于標(biāo)記該字符是否為前綴
        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;
};

三數(shù)之和 題目描述

給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組?nums，判斷?nums?中是否存在三個(gè)元素 a，b，c ，使得?a + b + c = 0 ？找出所有滿(mǎn)足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿(mǎn)足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

這題我們才用排序+雙指針的思路來(lái)做，遍歷排序后的數(shù)組，定義指針l和r,分別從當(dāng)前遍歷元素的下一個(gè)元素和數(shù)組的最后一個(gè)元素往中間靠攏，計(jì)算結(jié)果跟目標(biāo)對(duì)比。

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){
            // 若當(dāng)前元素大于0，則三元素相加之后必定大于0
            break;
        }
        // l為左下標(biāo)，r為右下標(biāo)
        let l = i + 1; r = nums.length - 1;
        while(l 0){
                r--;
            }
        }
    }

    return res;
};

最接近的三數(shù)之和 題目描述

給定一個(gè)包括?n 個(gè)整數(shù)的數(shù)組?nums?和一個(gè)目標(biāo)值?target。找出?nums?中的三個(gè)整數(shù)，使得它們的和與?target?最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。

例如，給定數(shù)組 nums = [-1，2，1，-4], 和 target = 1.

與 target 最接近的三個(gè)數(shù)的和為 2. (-1 + 2 + 1 = 2).

解答

這題跟上面那題思路一致，也是排序+雙指針，不過(guò)需要多維護(hù)一個(gè)差值作比較來(lái)獲取最小差距的值。

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，直接出結(jié)果
                    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;
    }
};

電話(huà)號(hào)碼的字母組合 題目描述

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話(huà)按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

示例

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

解答

這題簡(jiǎn)單，直接遍歷字符，然后數(shù)組相加就好，不用擔(dān)心復(fù)雜度高，因?yàn)榛鶖?shù)也就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;
};

四數(shù)之和 題目描述

給定一個(gè)包含?n 個(gè)整數(shù)的數(shù)組?nums?和一個(gè)目標(biāo)值?target，判斷?nums?中是否存在四個(gè)元素 a，b，c?和 d?，使得?a + b + c + d?的值與?target?相等？找出所有滿(mǎn)足條件且不重復(fù)的四元組。

注意：
答案中不可以包含重復(fù)的四元組。

示例

給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

滿(mǎn)足要求的四元組集合為：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解答

這題跟三數(shù)之和差不多，思路一致，不過(guò)這次是兩層循環(huán)+兩指針
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 target){
                r--;
            }
        }
    }
}
return res;

};

刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn) 題目描述

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

說(shuō)明：
給定的 n 保證是有效的。

示例

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.

當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.

解答

這題不難，可以直接遍歷一次，獲取鏈表的長(zhǎng)度，然后再次遍歷到對(duì)應(yīng)的節(jié)點(diǎn)，直接刪除
也可以遍歷一次，讓單向鏈表成為雙向鏈表，然后直接刪除也可，本文采取第二種做法

var removeNthFromEnd = function(head, n) {
    let cur = head;
    while(cur.next){
        cur.next.prev = cur;
        cur = cur.next;
    }
    if(n == 1){
        // 刪除最后一個(gè)節(jié)點(diǎn)
        if(!cur.prev){
            return null;
        }
        else{
            cur.prev.next = null;
            return head;
        }
    }
    while(n > 0 && cur){
        if(n == 1){
            if(!cur.prev){
                // 刪除第一個(gè)節(jié)點(diǎn)
                cur.next.prev = null;
                return cur.next
            }
            else{
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return head;
            }
        }
        cur = cur.prev;
        n--;
    }
};

有效的括號(hào) 題目描述

給定一個(gè)只包括 "("，")"，"{"，"}"，"["，"]"?的字符串，判斷字符串是否有效。

有效字符串需滿(mǎn)足：
左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。

示例

輸入: "()"
輸出: true

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

輸入: "(]"
輸出: false

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

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

解答

這題簡(jiǎn)單，直接維護(hù)一個(gè)堆棧，遍歷字符串，若是左半邊就入棧，右半邊就出棧，出棧的元素跟遍歷的字符串能匹配則繼續(xù)，否則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] == "["){
            // 左括號(hào)，入棧
            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;
    }
};

小結(jié)

弟弟才疏學(xué)淺，有不正確或者更好的做法，希望各位大神糾正和建議，我會(huì)持續(xù)更新。

GPU云服務(wù)器云服務(wù)器 js20a11視頻 js20 LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106753.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

CoderDock

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

掃雷1.0（遞歸實(shí)現(xiàn)）

閱讀 604·2021-11-15 11:38
通過(guò)Python繪制九種二次曲面

閱讀 1194·2021-10-11 10:59
大開(kāi)眼界！數(shù)字人民幣原來(lái)還有這些新玩法

閱讀 3503·2021-09-07 09:58
CSS 常用布局在小程序中的應(yīng)用

閱讀 491·2019-08-30 15:44
CSS頁(yè)面布局筆記

閱讀 3531·2019-08-28 18:14
使用IndexedDB做前端日志持久化

閱讀 2609·2019-08-26 13:32
Phaser3游戲三角學(xué)應(yīng)用--一只跟隨屏幕點(diǎn)擊位置游動(dòng)的魚(yú)

閱讀 3522·2019-08-26 12:23
用原生js寫(xiě)出一個(gè)彈框+遮罩層的頁(yè)面,完成彈框垂直居中頁(yè)面且點(diǎn)擊彈框外任何區(qū)域去掉彈框和遮罩層的功能

閱讀 2422·2019-08-26 10:59

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

JS算法題之leetcode(11~20)

相關(guān)文章

**JS算法題之leetcode(1~10)**

python面試題之“該死的for循環(huán)系列”（一）

數(shù)據(jù)分析面試題之Pandas中的groupby

前端 100 問(wèn)：能搞懂80%的請(qǐng)把簡(jiǎn)歷給我

發(fā)表評(píng)論

0條評(píng)論

CoderDock

男|高級(jí)講師

TA的文章

掃雷1.0（遞歸實(shí)現(xiàn)）

通過(guò)Python繪制九種二次曲面

大開(kāi)眼界！數(shù)字人民幣原來(lái)還有這些新玩法

CSS 常用布局在小程序中的應(yīng)用

CSS頁(yè)面布局筆記

使用IndexedDB做前端日志持久化

Phaser3游戲三角學(xué)應(yīng)用--一只跟隨屏幕點(diǎn)擊位置游動(dòng)的魚(yú)

用原生js寫(xiě)出一個(gè)彈框+遮罩層的頁(yè)面,完成彈框垂直居中頁(yè)面且點(diǎn)擊彈框外任何區(qū)域去掉彈框和遮罩層的功能

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

JS算法題之leetcode(11~20)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！