0


面试官问出这几道算法题,你能扛住么?

写在前面

CSDN话题挑战赛第1期

  • 活动详情地址:https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
  • 参赛话题:前端面试宝典
  • 话题描述:欢迎各位加入话题创作得小伙伴,如果我没有猜错得话,我觉得你是应该同我一样是一位前端人。如今前端在IT事业中的占比越来越重,已经成为不可缺少的部分,前端技术也是层出不穷,各种技术类、技术框架也蜂拥而出,前端面试的难度也随之增加,如果我们拥有一套前端面试宝典。如果你是应聘者:你就可以从容的solo面试官,如果你是面试官:你就可以将应聘者拷问到骨子里! 总之我们大家一起将自己的面试经验以及学习到的知识点汇聚于此,形成一套体系的前端面试宝典。让读者无论是面试还是学习都能够有非常大的收获。就让我们携手共筑前端面试宝典吧!!!

前言
现在的大厂越来越注重算法题,往往会被用来衡量你的代码能力,作为想要顺利拿到大厂offer的你,算法是必不可缺的一项技能,通过我的文章,带你刷爆剑指offer,吊打面试官,斩获大厂offer,以下的题目很多都是在字节跳动等大厂出现过的题目,大家可以学习一下!

剑指offer十题

题目一

剑指 Offer 03. 数组中重复的数字
题目链接:剑指offer03 力扣

考点

哈希表,排序

答案

哈希表是一种数据结构,也是散列表的一种,通过关键码值进行直接访问的数据结构,通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
这道题用到的就是哈希表,哈希表的结构是:number-boolean,number 就是数组中的数字,boolean 代表数字是否出现过,我们可以通过遍历数组中的数字,检查是否出现过,如果出现过,那么返回此数字。
代码如下:

/**
 * @param {number[]} nums
 * @return {number}
 */varfindRepeatNumber=function(nums){const map ={};for(const num of nums){if(!map[num]){
            map[num]=true;}else{return num;}}};

题目二

剑指 Offer 05. 替换空格
题目链接:剑指offer05 力扣

考点

双指针,字符串

答案

双指针算法 所谓双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应目的,没学过的同学可以去学习一下。
先遍历一次字符串,统计出字符串中空格的总数,可以计算出替换之后的字符串的总长度,每替换一个空格,长度加2,替换以后字符串的长度等于原来的长度加上2*空格数
从后向前把字符串中的空格替换成%20。

/**
 * @param {string} s
 * @return {string}
 */varreplaceSpace=function(s){if(s ==null||!s.length){return"";}
  s = s.split("");let kongge =0;let i =0;while(i < s.length){if(s[i]==" "){
      kongge++;}
    i++;}let newLength = s.length -1+ kongge *2;let indexOfOrigin = s.length -1;let indexOfNew = newLength;while(indexOfOrigin >=0&& indexOfNew > indexOfOrigin){if(s[indexOfOrigin]==" "){
      s[indexOfNew--]="0";
      s[indexOfNew--]="2";
      s[indexOfNew--]="%";}else{
      s[indexOfNew--]= s[indexOfOrigin];}
    indexOfOrigin--;}return s.join("");};

题目三

剑指 Offer 10- I. 斐波那契数列
题目链接:斐波那契数列 力扣

考点

动态规划,递推

答案

这道题是很经典的动态规划问题,是用动态规划来解决,不懂的小伙伴呢可以去学习一下这种解题思路。
我们通过计算可以推出状态转移方程dp[i] = dp[i - 1] + dp[i - 2]
dp[i]含义:斐波那契数列的第i个数为dp[i]
dp数组初始化:题目已经给出:分别是0和1
记得每次取模哦

constfib= n =>{const dp =[0,1];for(let i =2; i <= n; i++){
        dp[i]=(dp[i -1]+ dp[i -2])%1000000007;}return dp[n];};

题目四

剑指 Offer 10- II. 青蛙跳台阶问题
题目链接:力扣 跳台阶

考点

动态规划

答案

也是一道非常经典的动态规划问题,和斐波那契那题差不多,推一下状态转移方程
dp[i] = dp[i - 1] + dp[i - 2]
dp[i]含义:dp[i]是到第i层楼梯有多少跳法
dp数组初始化:两个1
在第 n - 2 层时,一次性跨两层(只有这一种爬法)
在第 n - 1 层时,一次性跨一层(只有这一种爬法)

/**
 * @param {number} n
 * @return {number}
 */varnumWays=function(n){if(!n || n ===1){return1;}let dp =[1,1];for(let i =2; i <= n; i++){
        dp[i]=(dp[i -1]+ dp[i -2])%1000000007;}return dp[n];};

题目五

剑指 Offer 22. 链表中倒数第k个节点
题目链接:力扣力扣

考点

链表,双指针

答案

链表是一种链式存储的数据结构,链表的特性,使其在某些操作上很高效。例如当进行插入和删除操作时,链表操作的时间复杂度仅为O(1)。另外,因为链表在内存中不是连续存储的,所以可以充分利用内存中的碎片空间。
这道题目依旧还是使用双指针,让快指针先走k步,然后快慢指针开始前进,当快指针走到链表末尾时,慢指针所在的位置就是倒数第k个链表节点

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */vargetKthFromEnd=function(head, k){let dummyNode =newListNode(-1);
  dummyNode.next = head;let fast = dummyNode,
    slow = dummyNode;while(fast && k){
    fast = fast.next;
    k--;}while(fast){
    fast = fast.next;
    slow = slow.next;}return slow;};

题目六

剑指 Offer 24. 反转链表
题目链接:力扣力扣

考点

链表,递归

答案

首先遍历所有的节点,然后存储下一个节点nextNode,把当前节点赋值为上一个节点,最后一个nextNode为null,就结束了。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 *//**
 * @param {ListNode} head
 * @return {ListNode}
 */varreverseList=function(head){let preNode =nulllet curNode = head
  while(curNode){const nextNode = curNode.next
    curNode.next = preNode
    preNode = curNode
    curNode = nextNode
  }return preNode
};

题目七

剑指 Offer 27. 二叉树的镜像
题目链接:二叉树

考点

搜索,二叉树

答案

二叉树:树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为节点)按分支关系组织起来的结构。二叉树(Binary Tree)是每个节点最多有两个子树的有序树。通常子树被称作"左子树"(left subtree)和"右子树"(rightsubtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树不是树的特殊情形。在图论中,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点后,每个顶点定义了唯一的根节点,和最多2个子节点。然而,没有足够的信息来区分左节点和右节点,二叉树通过链式存储来保存值,遍历方法有前序遍历,中序遍历,后序遍历,深度优先搜索,广度优先搜索。
首先我们需要递归遍历原来这棵树的左子树和右子树。然后把这棵树的左节点赋给原来的右节点(对调换),直到节点为null为止。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 *//**
 * @param {TreeNode} root
 * @return {TreeNode}
 */varmirrorTree=function(root){if(root==null){returnnull;}const l =mirrorTree(root.left);const r =mirrorTree(root.right);
    root.left = r;
    root.right = l;return root;};

题目八

剑指 Offer 31. 栈的压入、弹出序列
题目链接:力扣力扣

考点

栈,数组,模拟

答案

栈:栈是一种操作受限的线性表只允许从一端插入和删除数据。栈有两种存储方式,即线性存储和链接存储(链表)。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行,所以每次删除的元素都是最后进栈的元素,故栈也被称为后进先出表。每个栈都有一个栈顶指针,它初始值为-1,且总是指向最后一个入栈的元素,栈有两种处理方式,即进栈(push)和出栈(pop),因为在进栈只需要移动一个变量存储空间。

这题我们用辅助栈stack模拟入栈的过程,每入一个就判断一次,入栈一次判断这个栈的栈顶是否和出栈的一致,一样的话这个数据就出栈,然后指针移到下一位比较

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */varvalidateStackSequences=function(pushed, popped){let stack=[],i=0;for(let n of pushed){
        stack.push(n);while(stack.length&&stack[stack.length-1]===popped[i]){
               stack.pop();++i;}}return stack.length===0;};

题目九

剑指 Offer 53 - I. 在排序数组中查找数字 I
题目链接:力扣力扣

考点

数组,map,二分

答案

这道题可以用map,也可以用二分,看个人的理解~
我们这里使用对象存储,遍历一遍数组,当查找key有对应的value时,value+,否则就表明该数字第一次出现,将value设置为1,最终输出的结果要考虑结果是否在数组。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */varsearch=function(nums, target){let map ={}for(let item of nums){if(map[item]){
            map[item]++}else{
            map[item]=1}}let res = map[target]? map[target]:0return res
};

题目十

剑指 Offer 64. 求1+2+…+n
题目链接:力扣!

考点

位运算。

答案

求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
我们这里使用递归解决,&& 特性:如果左边为 false,不执行右边; 左边为true继续执行右边。

/**
 * @param {number} n
 * @return {number}
 */varsumNums=function(n){return n&&sumNums(n-1)+n;};

写在最后
写文不易~ 如果你觉得对你有帮助的话可以给我来个点赞收藏关注支持一下,我会继续输出优质内容,算法的学习之路是要坚持下去的,不要轻易的放弃,你也可以做到吊打面试官。

CSDN话题挑战赛第1期

标签: 算法 面试 前端

本文转载自: https://blog.csdn.net/qq_45400861/article/details/124698066
版权归原作者 cloud、泡泡 所有, 如有侵权,请联系我们删除。

“面试官问出这几道算法题,你能扛住么?”的评论:

还没有评论