前言
现在的大厂越来越注重算法题，往往会被用来衡量你的代码能力，作为想要顺利拿到大厂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; };
