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

发布时间：2023-05-06 文章分类：WEB开发, 电脑百科 投稿人：赵颖 字号： 默认 | 大 | 超大 打印

写在前面

CSDN话题挑战赛第1期

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

剑指offer十题

  • 题目一
    • 考点
    • 答案
  • 题目二
    • 考点
    • 答案
  • 题目三
    • 考点
    • 答案
  • 题目四
    • 考点
    • 答案
  • 题目五
    • 考点
    • 答案
  • 题目六
    • 考点
    • 答案
  • 题目七
    • 考点
    • 答案
  • 题目八
    • 考点
    • 答案
  • 题目九
    • 考点
    • 答案
  • 题目十
    • 考点
    • 答案

题目一

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

考点

哈希表，排序

答案

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = 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}
 */
var replaceSpace = 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
记得每次取模哦

const fib = 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}
 */
var numWays = function(n) {
    if(!n || n === 1)
    {
    	return 1;
    }
    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}
 */
var getKthFromEnd = function (head, k)
{
  let dummyNode = new ListNode(-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}
 */
var reverseList = function(head)
{
  let preNode = null
  let 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}
 */
var mirrorTree = function(root)
{
    if (root==null)
    {
        return null;
    }
    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}
 */
var validateStackSequences = 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}
 */
var search = 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] : 0
    return 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}
 */
var sumNums = function(n)
{
	return n&&sumNums(n-1)+n;
};

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

CSDN话题挑战赛第1期

标签 , ,