本文共 4736 字,大约阅读时间需要 15 分钟。
前几天博主刚去面试字节跳动,面试官问了一些算法题。已经记录下来整理成文档了。去面试之前就听说字节跳动面试非常喜欢考算法题,基本每轮技术面都会有算法题,而且很难。
即将要去大厂面试的小伙伴可以采纳一波。
趁着年轻生猛,我要再和生活死磕几年。要么我就毁灭,要么我就铸就辉煌。如果有一天,你发现我在平庸面前低了头,那么请向我开炮。 – 《在路上》
面试题:反转单向链表
题目需要将一个单向链表反转。思路很简单,使用三个变量分别表示当前节点和当前节点的前后节点,虽然这题很简单,但是却是一道常考题
以下是实现该算法的代码
var reverseList = function(head) { // 判断下变量边界问题 if (!head || !head.next) return head // 初始设置为空,因为第一个节点反转后就是尾部,尾部节点指向 null let pre = null let current = head let next // 判断当前节点是否为空 // 不为空就先获取当前节点的下一节点 // 然后把当前节点的 next 设为上一个节点 // 然后把 current 设为下一个节点,pre 设为当前节点 while(current) { next = current.next current.next = pre pre = current current = 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,结果才为 18 & 7 // -> 0// 1000 & 0111 -> 0000 -> 0
2)按位或
其中一位为 1,结果就是 18 | 7 // -> 15// 1000 | 0111 -> 1111 -> 15
3)按位异或
每一位都不同,结果才为 18 ^ 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 b if (b == 0) return a let newA = a ^ b let newB = (a & b) << 1 return sum(newA, newB)}
堆排序利用了二叉堆的特性来做,二叉堆通常用数组表示,并且二叉堆是一颗完全二叉树(所有叶节点(最底层的节点)都是从左往右顺序排序,并且其他层的节点都是满的)。二叉堆又分为大根堆与小根堆。
堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例,某个节点的左边子节点索引是 i * 2 +1 ,右边是 i * 2 + 2 ,父节点是 (i - 1) /2 。
以下是实现该算法的代码
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 0 return 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;}
✨
即可免费获取web前端面试宝典、知识点、字节跳动真题文档(含解析)
转载地址:http://uoik.baihongyu.com/