JS算法題之leetcode(11~20)

CoderDock 發布于2019-08-26 10:46 / 1730人閱讀

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

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?。

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

小結

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

GPU云服務器云服務器 js20a11視頻 js20 LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/106753.html

JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取?；匚臄殿}目描述判斷一個整數是否是回文數?；匚臄凳侵刚驈淖笙蛴液偷剐驈挠蚁蜃笞x都是一樣的整數。 JS算法題之leetcode(1~10) 前言一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0
python面試題之“該死的for循環系列”（一）

摘要：這是一道魔性面試題，難倒了無數英雄好漢上面代碼的執行順序是這樣的從上到下第一個函數就是實現了一個簡單的加法運算第二個函數是一個生成器函數，如果調用它會返回一個生成器這一行調用了生成器函數，所以此刻就是一個生成器它的本質還是迭代器然后執行循環這是一道魔性面試題，難倒了無數英雄好漢…… def add(n,i): return n+i def test(): for i...

wudengzan 2019-07-30 18:00 評論0 收藏0
數據分析面試題之Pandas中的groupby

摘要：昨天晚上，筆者有幸參加了一場面試，有一個環節就是現場編程題目如下示例數據如下，求每名學生對應的成績最高的那門科目與，用實現這個題目看上去很簡單，其實，并不簡單。 ??昨天晚上，筆者有幸參加了一場面試，有一個環節就是現場編程！題目如下：??示例數據如下，求每名學生（ID）對應的成績（score）最高的那門科目（class）與ID，用Python實現： showImg(https://se...

ThinkSNS 2019-07-30 18:32 評論0 收藏0
前端 100 問：能搞懂80%的請把簡歷給我

摘要：解析第題第題為什么的和的中不能做異步操作解析第題第題京東下面代碼中在什么情況下會打印解析第題第題介紹下及其應用。盡量減少操作次數。解析第題第題京東快手周一算法題之兩數之和給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。引言半年時間，幾千人參與，精選大廠前端面試高頻 100 題，這就是「壹題」。在 2019 年 1 月 21 日這天，「壹題」項目正式開始，在這之后每個工...

Scott 2019-08-23 18:35 評論0 收藏0

發表評論

登陸后可評論

0條評論

CoderDock

男|高級講師

我要關注我要私信

TA的文章

掃雷1.0（遞歸實現）

閱讀 598·2021-11-15 11:38
通過Python繪制九種二次曲面

閱讀 1181·2021-10-11 10:59
大開眼界！數字人民幣原來還有這些新玩法

閱讀 3495·2021-09-07 09:58
CSS 常用布局在小程序中的應用

閱讀 485·2019-08-30 15:44
CSS頁面布局筆記

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

閱讀 2604·2019-08-26 13:32
Phaser3游戲三角學應用--一只跟隨屏幕點擊位置游動的魚

閱讀 3517·2019-08-26 12:23
用原生js寫出一個彈框+遮罩層的頁面,完成彈框垂直居中頁面且點擊彈框外任何區域去掉彈框和遮罩層的功能

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

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

JS算法題之leetcode(11~20)

相關文章

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

python面試題之“該死的for循環系列”（一）

數據分析面試題之Pandas中的groupby

前端 100 問：能搞懂80%的請把簡歷給我

發表評論

0條評論

CoderDock

男|高級講師

TA的文章

掃雷1.0（遞歸實現）

通過Python繪制九種二次曲面

大開眼界！數字人民幣原來還有這些新玩法

CSS 常用布局在小程序中的應用

CSS頁面布局筆記

使用IndexedDB做前端日志持久化

Phaser3游戲三角學應用--一只跟隨屏幕點擊位置游動的魚

用原生js寫出一個彈框+遮罩層的頁面,完成彈框垂直居中頁面且點擊彈框外任何區域去掉彈框和遮罩層的功能

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

JS算法題之leetcode(11~20)

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！