面試前的準備，筆試練手感
現在出去面試，很多時候都會讓你先做一份筆試題，而題目一般是中等偏下的水平，不會很難。
在面試前需要練練手感，以免在解題時沒有思路。
練手感可以自己準備一些筆試題目，可根據自己的情況選擇合適的題目，而解法可以寫一種或多種。
還搜集了一些筆試演算法總結，例如《一句話演算法》、《LeetCode》相關的內容。
一、數組
1）輸入多個”A”到”Z”、”a”到”z”、”0″到”9″字元，按ASCII碼值從小到大
採用數組內置的sort()排序方法，接收一個比較函數，包含兩個參數：a和b。
1. 當返回值大於0時，a會被移到b的後面。
2. 當返回值等於0時，a和b的位置不改變。
3. 當回返回值小於0時，a會被移到b的前面。
str.split('').sort().join('');
2）將一個整數逆序輸出
採用數組內置的reverse()逆序方法。
str.split('').reverse().join('');
3）混淆方法比較
1. slice()，開始位置（start）和結束位置（end），由提取元素組成的新數組，不包括結束位置的元素。
2. splice()，開始位置（start）、要刪除的元素個數（deleteCount）和要插入的一個或多個值（value1，value2，…），由刪除元素組成的新數組
二、數學
1）求最小公倍數
最小公倍數 = 兩整數的乘積 ÷ 最大公約數。
求最大公約數的輾轉相除法：
（1）a%b得餘數c。
（2）若c=0，則b即為兩數的最大公約數。
（4）若c≠0，則a=b，b=c，再回去執行（1）。
const divisor = gcd(left, right); function gcd(left, right) { if (right == 0) return left; return gcd(right, parseInt(left % right)); }
2）求一個數字對應的二進位數字中1的最大連續數，例如3的二進位為00000011，最大連續2個1
利用toString()將數字轉換成二進位，然後將0替換成空格。
str = parseInt(str).toString(2); const arr = str.replace(/0+/g, " ").split(" "), lens = arr.map((value) => value.length); const max = Math.max.apply(this, lens);
3）斐波那契數列
function fib(n) { const digits = [1, 1]; if (n == 1 || n == 2) { return 1; } for (let i = 2; i < n; i++) { digits[i] = digits[i - 1] + digits[i - 2]; } console.log(digits[n - 1]); }
三、排序
排序有冒泡、選擇、快速、歸併、堆等。此處我就記錄了快速排序的解法。
function quickSort(arr) { const length = arr.length; if(length <= 1) { return arr; } let left = [], right = [], base = arr[0]; for(let i=1; i<length; i++) { base > arr[i] ? (left.push(arr[i])) : (right.push(arr[i])); } left = quickSort(left); right = quickSort(right); return left.concat([base], right); }
1. 冒泡排序：對於給定的n個記錄，從第一個記錄開始依次對相鄰的兩個記錄進行比較，當前面的記錄大於後面的記錄時，交換其位置，進行一輪比較和換位後，n個記錄中的最大記錄將位於第n位。
2. 插入排序：對於給定的一組記錄，初始時假設第一個記錄自成一個有序序列，其餘的記錄為無序序列。接著從第二個記錄開始，按照記錄的大小依次將當前處理的記錄插入到其之前的有序序列中，直至最後一個記錄插入到有序序列中為止。
3. 歸併排序：利用遞歸與分治技術將數據序列劃分成越來越小的半子表，再對半子表排序，最後用遞歸方法將排好序的半子表合併成為越來越大的有序序列。
4. 快速排序：採用「分而治之」的思想，把大的拆分為小的，小的再拆分為更小的。將原序列分為兩部分，其中前一部分的所有記錄均比後一部分的所有記錄小，然後再依次對前後兩部分的記錄進行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。
5. 選擇排序：經過第一輪比較後得到最小的記錄，然後將該記錄與第一個記錄的位置進行交換；接著對不包括第一個記錄以外的其它記錄進行第二輪比較，得到最小的記錄並與第二個記錄進行位置交換；重複該過程，直到進行比較的記錄只有一個時為止。
6. 希爾排序：首先將待排序的數組元素分成多個子序列，使得每個子序列的元素個數相對較少，然後對各個子序列分別進行直接插入排序，等整個待排序列「基本有序」後，最終再對所有元素進行一次直接插入排序。
7. 堆排序：把這些記錄看做一棵順序存儲的二叉樹，然後將其調整為一個大頂堆，再將堆的最後一個元素與堆頂元素（即二叉樹的根結點）進行交換後，堆的最後一個元素即為最大記錄。
四、字元串
1）統計大寫字母的個數
利用數組的filter()方法過濾不符合條件的字母。
str.split('').filter(value => value >= 'A' && value <= 'Z').length;
2）找出字元串中第一個只出現一次的字元
利用indexOf()和lastIndexOf()方法，如果兩者相同，就說明只出現了一次。
function first(str) { for (let letter of str) { if (str.indexOf(letter) == str.lastIndexOf(letter)) { console.log(letter); return; } } console.log(-1); }
3）輸入一行字元，分別統計出包含英文字母、空格、數字和其它字元的個數
利用正則統計出各類字元的個數。
let matches = str.match(/[a-zA-Z]/g); const num1 = matches && matches.length; matches = str.match(/\s/g); const num2 = matches && matches.length; matches = str.match(/\d/g); const num3 = matches && matches.length; matches = str.match(/[^a-zA-Z0-9\s]/g); const num4 = matches && matches.length;
4）混淆方法比較
1. 字元串的原型方法charCodeAt()可以讀取到BMP中的字元的碼位。
2. String對象的靜態方法fromCharCode()可將碼位轉換成字元。
1. substring()，開始位置（start），結束位置（end）
2. substr()，開始位置（start），提取的字元數（length）
五、遞歸
1）迴文
function palindrome(str) { if (str.length <= 1) return true; //首字元和末字元做匹配 if (str[0] != str[str.length - 1]) return false; //將去除首尾字元的字元串傳入函數自身中 return palindrome(str.substr(1, str.length - 2)); }
六、鏈表
創建Node類和List類，addLink()方法用於插入節點。
class Node { constructor(key) { this.next = null; this.key = key; } } class List { constructor(key) { this.header = new Node(key); } addLink(node) { var current = this.header; while (current.next != null) { current = current.next; } current.next = node; } getLinkList() { var current = this.header; while (current) { console.log(current.key); current = current.next; } } }
七、二叉樹
創建Node類和Tree類，insert()方法用於插入節點，根據數值的大小放置合適位置，preOrder、midOrder、backOrder和levelOrder分別是前序、中序、後序和層次遍歷。
class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } class Tree { constructor(datas) { this.root = null; datas.forEach((value) => { const node = new Node(value); if (this.root == null) { this.root = node; return; } this.insert(this.root, node); }); } insert(parent, child) { if (parent.data > child.data) { parent.left === null ? (parent.left = child) : this.insert(parent.left, child); return; } parent.right === null ? (parent.right = child) : this.insert(parent.right, child); } preOrder(root) { if (!root) { return; } console.log(root.data); this.preOrder(root.left); this.preOrder(root.right); } midOrder(root) { if (!root) { return; } this.midOrder(root.left); console.log(root.data); this.midOrder(root.right); } backOrder(root) { if (!root) { return; } this.backOrder(root.left); this.backOrder(root.right); console.log(root.data); } levelOrder(node = this.root) { let queue = []; queue.push(node); // 根節點入隊 while (queue.length) { node = queue.shift(); // 出隊 console.log(node.data); // 訪問該節點 if (node.left) { // 如果它的右子樹不為空 queue.push(node.left); // 將左子樹的根節點入隊 } if (node.right) { // 如果它的右子樹不為空 queue.push(node.right); // 將右子樹的根節點入隊 } } } }
