如何通过66道前端面试题查漏补缺？

本部分主要是 CavsZhouyou 在练习《剑指 Offer》时所做的笔记，主要涉及算法相关知识和一些相关面试题时所做的笔记，分享这份总结给大家，帮助大家对算法的可以来一次全方位的检漏和排查。 附笔记链接，如果对你有帮助请给我点赞鼓励哦：https://github.com/Wscats/articles 1. 二维数组中的查找 题目： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的 一个二维数组和一个整数，判断数组中是否含有该整数。 思路： （1）第一种方式是使用两层循环依次遍历，判断是否含有该整数。这一种方式最坏情况下的时间复杂度为 O(n^2)。 （2）第二种方式是利用递增序列的特点，我们可以从二维数组的右上角开始遍历。如果当前数值比所求的数要小，则将位置向下移动 ，再进行判断。如果当前数值比所求的数要大，则将位置向左移动，再进行判断。这一种方式最坏情况下的时间复杂度为 O(n)。 2. 替换空格 题目： 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20 Are%20Happy 思路： 使用正则表达式，结合字符串的 replace 方法将空格替换为 “%20” str.replace(/\s/g,"%20") 3. 从尾到头打印链表 题目： 输入一个链表，从尾到头打印链表每个节点的值。 思路： 利用栈来实现，首先根据头结点以此遍历链表节点，将节点加入到栈中。当遍历完成后，再将栈中元素弹出并打印，以此来实现。栈的 实现可以利用 Array 的 push 和 pop 方法来模拟。 4. 重建二叉树 题目： 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输 入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路： 利用递归的思想来求解，首先先序序列中的第一个元素一定是根元素。然后我们去中序遍历中寻找到该元素的位置，找到后该元素的左 边部分就是根节点的左子树，右边部分就是根节点的右子树。因此我们可以分别截取对应的部分进行子树的递归构建。使用这种方式的 时间复杂度为 O(n)，空间复杂度为 O(logn)。 5. 用两个栈实现队列 题目： 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 思路： 队列的一个基本特点是，元素先进先出。通过两个栈来模拟时，首先我们将两个栈分为栈 1 和栈 2。当执行队列的 push 操作时，直接 将元素 push 进栈 1 中。当队列执行 pop 操作时，首先判断栈 2 是否为空，如果不为空则直接 pop 元素。如果栈 2 为空，则将栈 1 中 的所有元素 pop 然后 push 到栈 2 中，然后再执行栈 2 的 pop 操作。 扩展： 当使用两个长度不同的栈来模拟队列时，队列的最大长度为较短栈的长度的两倍。 6. 旋转数组的最小数字 题目： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的 最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。 NOTE：给出的所有元素都大于 0，若数组大 小为 0，请返回 0。 思路： （1）我们输入的是一个非递减排序的数组的一个旋转，因此原始数组的值递增或者有重复。旋转之后原始数组的值一定和一个值相 邻，并且不满足递增关系。因此我们就可以进行遍历，找到不满足递增关系的一对值，后一个值就是旋转数组的最小数字。 （2）二分法 相关资料可以参考： 《旋转数组的最小数字》 7. 斐波那契数列 题目： 大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项。 n<=39 思路： 斐波那契数列的规律是，第一项为 0，第二项为 1，第三项以后的值都等于前面两项的和，因此我们可以通过循环的方式，不断通过叠 加来实现第 n 项值的构建。通过循环而不是递归的方式来实现，时间复杂度降为了 O(n)，空间复杂度为 O(1)。 8. 跳台阶 题目： 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。