【Leetcode 做題學算法周刊】第一期
- 2019 年 10 月 28 日
- 筆記
首發於微信公眾號《前端成長記》，寫於 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)
