面试前的准备，笔试练手感
现在出去面试，很多时候都会让你先做一份笔试题，而题目一般是中等偏下的水平，不会很难。
在面试前需要练练手感，以免在解题时没有思路。
练手感可以自己准备一些笔试题目，可根据自己的情况选择合适的题目，而解法可以写一种或多种。
还搜集了一些笔试算法总结，例如《一句话算法》、《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); // 将右子树的根节点入队 } } } }
