DIV CSS 佈局教程網

JavaScript 面試常見的六個經典演算法題
編輯:關於JavaScript     

這篇整理六個面試與筆試中反覆出現的經典題目,並用 JavaScript 實作。每題都附上解法原理,方便理解而非死背。

(1)陣列去重

原理:定義一個物件 obj,把陣列元素當作屬性名,利用屬性名不會重複的特性來判重。

var unique = function (arr) {
  let obj = {};
  let newArr = [];
  arr.forEach(function (x) {
    if (!obj[x]) {        // 物件中還沒有這個屬性
      obj[x] = true;
      newArr.push(x);
    }
  });
  return newArr;
};

(2)快速排序

原理:選定一個元素作為標誌位,遍歷其餘元素,比標誌位大的放右邊、小的放左邊,再對左右兩側遞迴。

特別注意:遇到與標誌位相等的元素時,若選擇「不收集」,就順便完成了去重;若收集了,就是不去重的排序。

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));
};

(3)找出出現次數最多的字元

原理:與陣列去重同源,同樣用一個物件當計數表;屬性不存在就設為 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;
};

(4)不使用第三個變數交換兩值

原理:純數值運算的變數替換,思路巧妙,但只適用於數字。

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];
};

(5)求陣列的最大差值

原理:遍歷一次,同時記錄最大值與最小值,回傳兩者相減。

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;
};

(6)產生任意長度的隨機字串

原理:自訂字元庫與長度 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() 不具備密碼學安全性。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved