面試常考、日常也常用的一組基礎題。這裡把每題的「為什麼可以這樣寫」講清楚,比背下來更有價值。
把陣列元素當成物件的鍵,利用鍵的唯一性完成判重。
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];
// 嚴格比較:等於 tag 者被排除,因此順便去重
for (let i = 0; i < arr.length; i++) {
if (arr[i] < tag) { leftArr.push(arr[i]); }
if (arr[i] > tag) { rightArr.push(arr[i]); }
}
// 若要保留重複值,改成從 1 開始、else 收進右邊
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;
}
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;
};
用加減法互相抵消。以 a、b 為例:先令 b = b − a,此時 b 存的是差值;再令 a = a + b,等於 a + (b − a),a 就變成了原本的 b;最後 b = a − b,把 a 還原成原本的 b 減去差值,得到原本的 a。
var swap = function (a, b) {
if (a === b) { return [a, b]; }
b = b - a;
a = a + b;
b = a - b;
return [a, b];
};
這招看起來聰明,但實務上不推薦:它只能用在數字,遇到浮點數會有精度誤差,可讀性也差。ES6 的解構賦值 [a, b] = [b, a] 才是正解。
一次遍歷同時更新最大值與最小值,最後相減。
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;
};
準備一个字元池,用 Math.random() 隨機取索引、Math.floor() 取整數,重複 n 次即可。
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;
};
這六題的共同點是:核心幾乎都在「用物件當雜湊表」或「一次遍歷維護狀態」這兩個模式上。把這兩個思路吃透,同類題目基本都能自行推導出來。