這篇整理六個面試與筆試中反覆出現的經典題目,並用 JavaScript 實作。每題都附上解法原理,方便理解而非死背。
原理:定義一個物件 obj,把陣列元素當作屬性名,利用屬性名不會重複的特性來判重。
var unique = function (arr) {
let obj = {};
let newArr = [];
arr.forEach(function (x) {
if (!obj[x]) { // 物件中還沒有這個屬性
obj[x] = true;
newArr.push(x);
}
});
return newArr;
};
原理:選定一個元素作為標誌位,遍歷其餘元素,比標誌位大的放右邊、小的放左邊,再對左右兩側遞迴。
特別注意:遇到與標誌位相等的元素時,若選擇「不收集」,就順便完成了去重;若收集了,就是不去重的排序。
var quickSort = function (arr) {
if (arr.length <= 1) { return arr; }
let leftArr = [];
let rightArr = [];
let tag = arr[0]; // 標誌位
/* 寫法一:只收嚴格大於/小於,等於的被丟棄 → 排序同時去重 */
for (let i = 0; i < arr.length; i++) {
if (arr[i] < tag) { leftArr.push(arr[i]); }
if (arr[i] > tag) { rightArr.push(arr[i]); }
}
/* 寫法二:從 index 1 開始,等於的一律進右邊 → 不去重 */
for (let i = 1; i < arr.length; i++) {
if (arr[i] < tag) {
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
return [].concat(quickSort(leftArr), [tag], quickSort(rightArr));
};
原理:與陣列去重同源,同樣用一個物件當計數表;屬性不存在就設為 1,存在則加一。
var maxShowTimes = function (str) {
let obj = {};
// 空字串或只有一個字元時直接回傳
if (str.length <= 1) {
return str.length === 0 ? '字符串不能為空' : str;
}
// 用 charAt() 逐字取出
for (let i = 0; i <= str.length; i++) {
if (!obj[str.charAt(i)]) {
obj[str.charAt(i)] = 1;
} else {
obj[str.charAt(i)] += 1;
}
}
// 在物件中找出值最大的屬性
let maxChar = '';
let maxTimes = 0;
for (var k in obj) {
if (obj[k] > maxTimes) {
maxChar = k;
maxTimes = obj[k];
}
}
return maxChar;
};
原理:純數值運算的變數替換,思路巧妙,但只適用於數字。
var swap = function (a, b) {
if (a === b) { return [a, b]; }
b = b - a; // b 現在存的是原 b − 原 a
a = a + b; // a = 原a + (原b − 原a) = 原 b
b = a - b; // b = 原b − (原b − 原a) = 原 a
return [a, b];
};
原理:遍歷一次,同時記錄最大值與最小值,回傳兩者相減。
var getMaxProfit = function (arr) {
let maxNum = arr[0];
let minNum = arr[0];
for (let i = 0; i < arr.length; i++) {
if (arr[i] > maxNum) { maxNum = arr[i]; }
if (arr[i] < minNum) { minNum = arr[i]; }
}
return maxNum - minNum;
};
原理:自訂字元庫與長度 n,用 Math.random() 取索引、Math.floor() 取整,組出隨機字串。
var getRandomString = function (n) {
let str = 'qwertyuiopasdfghjklzxcvbnm1234567890'; // 字元庫
let tmp = '';
let len = str.length;
for (let i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * len));
}
return tmp;
};
補充兩點實務上的提醒:陣列去重若資料量大,用 Set 或 arr.filter((v, i, a) => a.indexOf(v) === i) 會更簡潔;而產生隨機字串若要用於 token 或密碼等安全場景,務必改用 crypto.getRandomValues(),Math.random() 不具備密碼學安全性。