字节跳动算法题
链表
面试题：反转单向链表
题目需要将一个单向链表反转。思路很简单，使用三个变量分别表示当前节点和当前节点的前后节点，虽然这题很简单，但是却是一道常考题
以下是实现该算法的代码
var reverseList = function(head) {// 判断下变量边界问题if (!head || !head.next) return head// 初始设置为空，因为第一个节点反转后就是尾部，尾部节点指向 nulllet pre = nulllet current = headlet next// 判断当前节点是否为空// 不为空就先获取当前节点的下一节点// 然后把当前节点的 next 设为上一个节点// 然后把 current 设为下一个节点，pre 设为当前节点while(current) {next = current.nextcurrent.next = prepre = currentcurrent = next}return pre};
二叉树遍历
原理: 递归function traversal(node,tempOrderTraversal) {if (node != null) {// tempOrderTraversal.push(node.value) 前序遍历if (node.left != null) {preOrderTraversal(node.left,tempOrderTraversal)}// tempOrderTraversal.push(node.value) 中序遍历if (node.right != null) {preOrderTraversal(node.right,tempOrderTraversal)}// tempOrderTraversal.push(node.value) 后序遍历}}
不能使用递归时，则使用栈就是JS的数组push、pop
// 非递归遍历var kthSmallest = function(root, k) {const tempArr = [];let result;tempArr.push(root);while (tempArr.length > 0) {result = tempArr.pop();if (result.value == k) break;if (result.left != null) tempArr.push(result.left);if (result.right != null) tempArr.push(result.right);}return result;};
按位操作
1）按位与
每一位都为 1，结果才为 1
8 & 7 // -> 0// 1000 & 0111 -> 0000 -> 0
2）按位或
其中一位为 1，结果就是 1
8 | 7 // -> 15// 1000 | 0111 -> 1111 -> 15
3）按位异或
每一位都不同，结果才为 1
8 ^ 7 // -> 158 ^ 8 // -> 0// 1000 ^ 0111 -> 1111 -> 15// 1000 ^ 1000 -> 0000 -> 0
从以上代码中可以发现按位异或就是不进位加法
面试题：两个数不使用四则运算得出和
这道题中可以按位异或，因为按位异或就是不进位加法， 8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法
function sum(a, b) {if (a == 0) return bif (b == 0) return alet newA = a ^ blet newB = (a & b) << 1return sum(newA, newB)}
堆排序
堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。
大根堆是某个节点的所有子节点的值都比他小小根堆是某个节点的所有子节点的值都比他大
堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例，某个节点的左边子节点索引是 i * 2 +1 ，右边是 i * 2 + 2 ，父节点是 (i - 1) /2 。
首先遍历数组，判断该节点的父节点是否比他小，如果小就交换位置并继续判断，直到他的父节点
比他大重新以上操作 1，直到数组首位是最大值然后将首位和末尾交换位置并将数组长度减一，表示数组末尾已是最大值，不需要再比较大小对比左右节点哪个大，然后记住大的节点的索引并且和父节点对比大小，如果子节点大就交换位置重复以上操作 3 - 4 直到整个数组都是大根堆。
以下是实现该算法的代码
function heap(array) {checkArray(array);// 将最大值交换到首位for (let i = 0; i < array.length; i++) {heapInsert(array, i);}let size = array.length;// 交换首位和末尾swap(array, 0, --size);while (size > 0) {heapify(array, 0, size);swap(array, 0, --size);}return array;}function heapInsert(array, index) {// 如果当前节点比父节点大，就交换while (array[index] > array[parseInt((index - 1) / 2)]) {swap(array, index, parseInt((index - 1) / 2));// 将索引变成父节点index = parseInt((index - 1) / 2);}}function heapify(array, index, size) {let left = index * 2 + 1;while (left < size) {// 判断左右节点大小let largest =left + 1 < size && array[left] < array[left + 1] ? left + 1 : left;// 判断子节点和父节点大小largest = array[index] < array[largest] ? largest : index;if (largest === index) break;swap(array, index, largest);index = largest;left = index * 2 + 1;}}
以上代码实现了小根堆，如果需要实现大根堆，只需要把节点对比反一下就好。
树的深度
面试题：树的最大深度
题目需要求出一颗二叉树的最大深度
以下是实现该算法的代码
var maxDepth = function(root) {if (!root) return 0return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1};
对于该递归函数可以这样理解：一旦没有找到节点就会返回 0，每弹出一次递归函数就会加一，树有三层就会得到3。
快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
以下是实现该算法的代码
function quickSort(arr, left, right) {var len = arr.length,partitionIndex,left =typeof left !='number' ? 0 : left,right =typeof right !='number' ? len - 1 : right;if (left < right) {partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);}return arr;}function partition(arr, left ,right) {// 分区操作var pivot = left, // 设定基准值（pivot）index = pivot + 1;for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;} }swap(arr, pivot, index - 1);return index-1;}function swap(arr, i, j) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
最后
篇幅有限，文章中的前端初阶笔记，学习路线图，和前端面试题都可以点击这里免费领取完整版PDF（含答案解析）。
《前端面试题精选大全》内容大纲包括HTML，CSS，JavaScript，jQuery，浏览器，HTTP，React，小程序
p;
}
#### 最后**篇幅有限，文章中的前端初阶笔记，学习路线图，和前端面试题都可以[点击这里免费领取](/vip204888/web-p7)完整版PDF（含答案解析）。**>**《前端面试题精选大全》**内容大纲包括**HTML，CSS，JavaScript，jQuery，浏览器，HTTP，React，小程序**[外链图片转存中...(img-2j5eb8tL-1627014347795)]
