【Leetcode 做題學演算法周刊】第一期-有解無憂

首發于微信公眾號《前端成長記》，寫于 2019.10.28

背景

本文記錄刷題程序中的整個思考程序，以供參考，主要內容涵蓋：

題目分析設想
撰寫代碼驗證
查閱他人解法
思考總結

Easy

1.兩數之和

題目地址

題目描述

給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那兩個整數，并回傳他們的陣列下標，

你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個陣列中同樣的元素，

示例：

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]

題目分析設想

這道題首先說明了每種輸入只會對應一個答案，并且不能利用陣列中同樣的元素，也就意味著一個數不能被使用兩次，即 [0,0] 這種是不合理的，

看到這個題目，我有幾個方向去嘗試作答：

暴力點，直接回圈兩次即可，預估性能最差
IndexOf ，回圈次數最多，非常不推薦
空間換時間，使用 HashMap ,減少一次回圈

撰寫代碼驗證

Ⅰ.暴力法

代碼：

// 暴力點
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        // j 從 i+1 開始，去除一些無用運算
        for(let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i,j];
            }
        }
    }
};

結果：

29/29 cases passed (124 ms)
Your runtime beats 60.13 % of javascript submissions
Your memory usage beats 66.05 % of javascript submissions (34.5 MB)
時間復雜度：O(n^2)

Ⅱ.IndexOf

性能最差，每次判斷都需要遍歷剩余陣列（極度不推薦，只是多展示一個實作方案）

代碼：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i]
        const dif = target - num
        const remainArr = nums.slice(i + 1)
        if (remainArr.indexOf(dif) !== -1) {
            return [i, remainArr.indexOf(dif) + i + 1]
        }
    }
};

結果：

29/29 cases passed (212 ms)
Your runtime beats 22.39 % of javascript submissions
Your memory usage beats 5 % of javascript submissions (49 MB)
時間復雜度： O(n^2) ，階乘的時間復雜度為 O(n)

Ⅲ.HashMap

代碼：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let hash = {}
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i]
        const dif = target - num
        if (hash[dif] !== undefined) {
            return [hash[dif], i]
        } else {
            hash[num] = i
        }
    }
};

結果：

29/29 cases passed (60 ms)
Your runtime beats 98.7 % of javascript submissions
Your memory usage beats 19.05 % of javascript submissions (35.3 MB)
時間復雜度： O(n)

對比發現，HashMap 方案較暴力法在速度上有明顯的提升，

查閱他人解法

這里看到還有兩種方式，我們一一來嘗試一下，

Ⅰ.使用陣列替換 HashMap

代碼：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let arr = []
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i]
        const dif = target - num
        if (arr[dif] !== undefined) {
            return [arr[dif], i]
        } else {
            arr[num] = i
        }
    }
};

結果：

29/29 cases passed (60 ms)
Your runtime beats 98.7 % of javascript submissions
Your memory usage beats 17.89 % of javascript submissions (35.4 MB)
時間復雜度： O(n)

跟使用 HashMap 性能差異不大，

Ⅱ.兩次遍歷 HashMap

代碼：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let res = new Map()
    for(let i = 0; i < nums.length; i++) {
        res.set(nums[i], i)
    }
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i]
        const dif = target - num
        const idx = res.get(dif)
        if (idx !== undefined && idx !== i) {
            return [i, idx]
        }
    }
};

結果：

29/29 cases passed (64 ms)
Your runtime beats 96.76 % of javascript submissions
Your memory usage beats 10.94 % of javascript submissions (35.9 MB)
時間復雜度： O(n)

思考總結

這里我做個了簡單的校驗：輸入 [2,2,2], 4 ，發現期望輸出是 [0, 2] ，而不是 [0, 1] ,所以上面有幾種解法實際上都過不了，如果是為了滿足這種輸出，我的推薦方案是 兩次遍歷 HashMap ，但是我個人是覺得 HashMap 一次遍歷是更合理的，

7.整數反轉

題目地址

題目描述

給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉，

示例:

輸入: 123
輸出: 321

輸入: -123
輸出: -321

輸入: 120
輸出: 21

注意:

假設我們的環境只能存盤得下 32 位的有符號整數，則其數值范圍為 [?2^31, 2^31 ? 1]，請根據這個假設，如果反轉后整數溢位那么就回傳 0，

題目分析設想

從題干上來看，有幾個要注意的點：

溢位回傳 0
0 為首位需要去掉取自然數

這里我有兩種思路：

利用陣列反轉 reverse 來反轉再做自然數轉換
取余拿到每位上的數字再做加法和符號及溢位處理

撰寫代碼驗證

Ⅰ.陣列反轉

代碼：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    const isNegative = x < 0
    const rev = Number(Math.abs(x).toString().split('').reverse().join(''))
    if (isNegative && -rev >= -Math.pow(2, 31)) {
        return -rev
    } else if (!isNegative && rev <= Math.pow(2,31) - 1) {
        return rev
    } else {
        return 0
    }
};

結果：

1032/1032 cases passed (96 ms)
Your runtime beats 73.33 % of javascript submissions
Your memory usage beats 28.03 % of javascript submissions (35.9 MB)
時間復雜度： O(1)

Ⅱ.取余

代碼：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    const isNegative = x < 0
    let res = 0
    while(x !== 0) {
        res = res * 10 + x % 10
        x = parseInt(x / 10)
    }
    if ((isNegative && res >= -Math.pow(2, 31)) || (!isNegative && res <= Math.pow(2,31) - 1)) {
        return res
    } else {
        return 0
    }
};

結果：

1032/1032 cases passed (80 ms)
Your runtime beats 96.71 % of javascript submissions
Your memory usage beats 56.8 % of javascript submissions (35.7 MB)
時間復雜度： O(log10(n))

對比發現，使用取余的方式，性能上明顯優于陣列反轉，

查閱他人解法

思路基本上都是這兩種，未發現方向不同的解法，

思考總結

對比發現還有一些考慮不周的地方需要補全，比如說一些特殊值可直接回傳，避免運算，這里我也做了一個簡單的校驗：輸入 -0，發現期望輸出是 0 而不是 -0，所以，我這里的代碼做一些優化，如下：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    if (x === 0) return 0
    function isOverflow (num) {
        return num < -Math.pow(2, 31) || (num > Math.pow(2,31) - 1)
    }
    if (isOverflow(x)) return 0
    let res = 0
    while(x !== 0) {
        res = res * 10 + x % 10
        x = parseInt(x / 10)
    }
    return isOverflow(res) ? 0 : res
};

9.回文數

題目地址

題目描述

判斷一個整數是否是回文數，回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數，

示例：

輸入: 121
輸出: true

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 ， 從右向左讀, 為 121- ，因此它不是一個回文數，

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 ，因此它不是一個回文數，

進階:

你能不將整數轉為字串來解決這個問題嗎？

題目分析設想

這道題的第一感覺有點類似上一題整數反轉的拓展，所以我們從兩個方向入手：

整數轉字串
取余，前后逐位判斷

在寫的程序中需要考慮到去掉一些運算：把 <0 和 -0 排除，因為負數和 -0 一定不為回文數；一位正整數一定是回文數；除了 0 以外，尾數為 0 的不是回文數，

撰寫代碼驗證

Ⅰ.轉字串

代碼：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    const rev = parseInt(x.toString().split('').reverse().join(''))
    return rev === x
};

結果：

11509/11509 cases passed (252 ms)
Your runtime beats 79.41 % of javascript submissions
Your memory usage beats 52 % of javascript submissions (45.7 MB)
時間復雜度： O(1)

這里有用到 ES6 的 Object.is 來判斷是否為 -0 ，當然 ES5 你也可以這么判斷：

function (x) {
    return x === 0 && 1 / x < 0;    // -Infinity
}

可能有人會問不需要考慮數字溢位問題嗎？

輸入的數字不溢位，如果是回文數的話，那么輸出的數字一定不溢位；如果不是回文數，不管溢位與否，都是回傳 false，

Ⅱ.取余

代碼：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    let div = 1
    while (x / div >= 10) { // 用來找出位數，比如121，那么就找到100，得到整數位
        div *= 10
    }
    while(x > 0) {
        let left = parseInt(x / div); // 左側數起
        let right = x % 10; // 右側數起
        if (left !== right) return false;

        x = parseInt((x % div) / 10);   // 去掉左右各一位數

        div /= 100; // 除數去兩位
    }
    return true;
};

結果：

11509/11509 cases passed (232 ms)
Your runtime beats 86.88 % of javascript submissions
Your memory usage beats 67.99 % of javascript submissions (45.5 MB)
時間復雜度： O(log10(n))

查閱他人解法

這里看到一個更為巧妙的方式，只需要翻轉一半即可，比如說 1221 ，只需要翻轉后兩位 21 即可，

Ⅰ.翻轉一半

代碼：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    let rev = 0;    // 翻轉的數字

    while(x > rev) {
        rev = rev * 10 + x % 10
        x = parseInt(x / 10)
    }

    return x === rev || x === parseInt(rev / 10);   // 奇數的話需要去掉中間數做比較
};

結果：

11509/11509 cases passed (188 ms)
Your runtime beats 99.62 % of javascript submissions
Your memory usage beats 92.69 % of javascript submissions (44.8 MB)
時間復雜度： O(log10(n))

思考總結

綜上，最推薦翻轉一半的解法，

13.羅馬數字轉整數

題目地址

題目描述

羅馬數字包含以下七種字符: 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.

題目分析設想

這道題有個比較直觀的想法，因為特殊情況有限可列舉，所以我這里有兩個方向：

列舉所有特殊組合，然后進行字串遍歷
直接字串遍歷，判斷當前位和后一位的大小

撰寫代碼驗證

Ⅰ.列舉特殊組合

代碼：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'IV': 4,
        'V': 5,
        'IX': 9,
        'X': 10,
        'XL': 40,
        'L': 50,
        'XC': 90,
        'C': 100,
        'CD': 400,
        'D': 500,
        'CM': 900,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length;) {
        if (i < s.length - 1 && hash[s.substring(i, i + 2)]) { // 在 hash 表中，說明是特殊組合
            res += hash[s.substring(i, i + 2)]
            i += 2
        } else {
            res += hash[s.charAt(i)]
            i += 1
        }
    }
    return res
};

結果:

3999/3999 cases passed (176 ms)
Your runtime beats 77.06 % of javascript submissions
Your memory usage beats 80.86 % of javascript submissions (39.8 MB)
時間復雜度： O(n)

Ⅱ.直接遍歷

代碼：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length; i++) {
        if (i === s.length - 1) {
            res += hash[s.charAt(i)]
        } else {
            if (hash[s.charAt(i)] >= hash[s.charAt(i + 1)]) {
                res += hash[s.charAt(i)]
            } else {
                res -= hash[s.charAt(i)]
            }
        }
    }
    return res
};

結果：

3999/3999 cases passed (176 ms)
Your runtime beats 84.42 % of javascript submissions
Your memory usage beats 90.55 % of javascript submissions (39.6 MB)
時間復雜度： O(n)

查閱他人解法

這里還看到一種方式，全部先按加法算，如果有前一位小于后一位的情況，直接減正負差值 2/20/200 ，來看看代碼：

Ⅰ.差值運算

代碼：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length; i++) {
        res += hash[s.charAt(i)]
        if (i < s.length - 1 && hash[s.charAt(i)] < hash[s.charAt(i + 1)]) {
            res -= 2 * hash[s.charAt(i)]
        }
    }
    return res
};

結果：

3999/3999 cases passed (232 ms)
Your runtime beats 53.57 % of javascript submissions
Your memory usage beats 80.05 % of javascript submissions (39.8 MB)
時間復雜度： O(n)

換湯不換藥，只是做了個加法運算而已，沒有太大的本質區別，

思考總結

綜上，暫時沒有看到一些方向上不一致的解法，我這里推薦字串直接遍歷的解法，性能最佳，

14.最長公共前綴

題目地址

題目描述

撰寫一個函式來查找字串陣列中的最長公共前綴，

如果不存在公共前綴，回傳空字串 ""，

示例：

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

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

說明:

所有輸入只包含小寫字母 a-z ，

題目分析設想

這道題一看覺得肯定是需要遍歷的題，無非是演算法上的優劣罷了，我有三個方向來嘗試解題：

遍歷每列，取出陣列第一項，逐個取字串的每一位去遍歷陣列
遍歷每項，取出陣列第一項，逐步從后截取，判斷是否匹配陣列中的每一項
分治，將陣列遞回不斷細成倆部分，分別求最大匹配后，再匯總求最大匹配

撰寫代碼驗證

Ⅰ.遍歷每列

代碼：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return ''
    if (strs.length === 1) return strs[0] || ''
    const str = strs.shift()
    for(let i = 0; i < str.length; i++) {
        const char = str.charAt(i)
        for(let j = 0; j < strs.length; j++) {
            if (i === strs[j].length || strs[j].charAt(i) !== char) {
                return str.substring(0, i)
            }
        }
    }
    return str
};

結果：

118/118 cases passed (68 ms)
Your runtime beats 89.17 % of javascript submissions
Your memory usage beats 57.83 % of javascript submissions (34.8 MB)
時間復雜度： O(n)

Ⅱ.遍歷每項

代碼：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return ''
    if (strs.length === 1) return strs[0] || ''
    let str = strs.shift()
    for(let i = 0; i < strs.length; i++) {
        while (strs[i].indexOf(str) !== 0) {
            str = str.substring(0, str.length - 1);
            if (!str) return ''
        }
    }
    return str
};

結果：

118/118 cases passed (64 ms)
Your runtime beats 94.63 % of javascript submissions
Your memory usage beats 96.69 % of javascript submissions (33.5 MB)
時間復雜度： O(n)

Ⅲ.分治

代碼：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return ''
    if (strs.length === 1) return strs[0] || ''
    function arrayToString (arr, start, end) {
        if (start === end) {    // 說明陣列中只剩一項了
            return arr[start]
        } else {
            const mid = parseInt((start + end) / 2)
            const leftStr = arrayToString(arr, start, mid)
            const rightStr = arrayToString(arr, mid + 1, end)
            return getCommonPrefix(leftStr, rightStr)
        }
    }
    // 兩個字串取最長前綴
    function getCommonPrefix(left, right) {
        const min = Math.min(left.length, right.length)
        for(let i = 0; i < min; i++) {
            if (left.charAt(i) !== right.charAt(i)) {
                return left.substring(0, i)
            }
        }
        return left.substring(0, min)
    }
    return arrayToString(strs, 0, strs.length - 1)
};

結果：

118/118 cases passed (60 ms)
Your runtime beats 98.09 % of javascript submissions
Your memory usage beats 34.54 % of javascript submissions (35.1 MB)
時間復雜度： O(n)

查閱他人解法

這里還看見使用二分法，跟分治還是略有差異，是每次丟棄不包含答案的區間來減少運算量，

Ⅰ.二分法

代碼：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return ''
    if (strs.length === 1) return strs[0] || ''
    // 找到最短字串長度
    let minLen = 0
    for(let i = 0; i < strs.length; i++) {
        minLen = minLen === 0 ? strs[i].length : Math.min(minLen, strs[i].length)
    }

    function isCommonPrefix (arr, pos) {
        const str = arr[0].substring(0, pos)    // 取第一項的前一半
        for(let i = 0 ; i < arr.length; i++) {
            if (arr[i].indexOf(str) !== 0) {
                return false
            }
        }
        return true
    }

    let low = 1
    let high = minLen   // 截取最大數量

    while (low <= high) {
        const mid = parseInt((low + high) / 2)
        if (isCommonPrefix(strs, mid)) {    // 如果前半段是
            low = mid + 1   // 繼續判斷后半段
        } else {
            high = mid - 1  // 前半段繼續對半分繼續判斷
        }
    }

    return strs[0].substring(0, (low + high) / 2)
};

結果：

118/118 cases passed (64 ms)
Your runtime beats 94.63 % of javascript submissions
Your memory usage beats 93.96 % of javascript submissions (33.5 MB)
時間復雜度： O(log(n))

思考總結

具體情況具體分析，比如分治的演算法也可以應用在快速排序中，個人比較推薦分治法和二分法求解這道題，

（完）

本文為原創文章，可能會更新知識點及修正錯誤，因此轉載請保留原出處，方便溯源，避免陳舊錯誤知識的誤導，同時有更好的閱讀體驗
如果能給您帶去些許幫助，歡迎 ??star 或 ?? fork
(轉載請注明出處：https://chenjiahao.xyz)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/179050.html

標籤：JavaScript

上一篇：vue與webpack開發環境搭建：從無到有

下一篇：layui 學習筆記一：layui table 查詢、新增、編輯、洗掉

【Leetcode 做題學演算法周刊】第一期

背景

目錄

Easy

1.兩數之和

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

7.整數反轉

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

9.回文數

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

13.羅馬數字轉整數

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

14.最長公共前綴

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結