首發於微信公眾號《前端成長記》,寫於 2019.10.28 背景 本文記錄刷題過程中的整個思考過程,以供參考。主要內容涵蓋: 題目分析設想 編寫代碼驗證 查閱他人解法 思考總結 目錄 "1.兩數之和" "7.整數反轉" "9.迴文數" "13.羅馬數字轉整數" "14.最長公共首碼" Easy 1. ...
首發於微信公眾號《前端成長記》,寫於 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)