leetcode 最常见的前端基础算法面试题汇总_leecode算法常见面试

dfs(root, ret);

return ret

};

将有序数组转化为二叉搜索树

我们先看题：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]

输出：[3,1]

解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 按 严格递增 顺序排列

思路：

• 构建一颗树包括：构建root、构建 root.left 和 root.right

• 题目要求"高度平衡" — 构建 root 时候，选择数组的中间元素作为 root 节点值，即可保持平衡。

• 递归函数可以传递数组，也可以传递指针，选择传递指针的时候：l r 分别代表参与构建BST的数组的首尾索引。

var sortedArrayToBST = function(nums) {

return toBST(nums, 0, nums.length - 1)

};

const toBST = function(nums, l, r){

if( l > r){

return null;

}

const mid = l + r >> 1;

const root = new TreeNode(nums[mid]);

root.left = toBST(nums, l, mid - 1);

root.right = toBST(nums, mid + 1, r);

return root;

}

栈

---

栈是一种先进先出的数据结构，所以涉及到你需要先进先出这个想法后，就可以使用栈。

其次我觉得栈跟递归很相似，递归是不是先压栈，然后先进来的先出去，就跟函数调用栈一样。

有效的括号

这是一道很典型的用栈解决的问题， 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([)]”

输出：false

思路：这道题有一规律：

1.右括号前面，必须是相对应的左括号，才能抵消！

2.右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

也就是说左括号我们直接放入栈中即可，发现是右括号就要对比是否跟栈顶元素相匹配，不匹配就返回false

var isValid = function(s) {

const map = { ‘{’: ‘}’, ‘(’: ‘)’, ‘[’: ‘]’ };

const stack = [];

for(let i of s){

if(map[i]){

stack.push(i);

} else {

if(map[stack[stack.length - 1]] === i){

stack.pop()

}else{

return false;

}

}

}

return stack.length === 0;

};

最小栈

先看题目：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。

• pop() —— 删除栈顶的元素。

• top() —— 获取栈顶元素。

• getMin() —— 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

我们先不写getMin方法，满足其他方法实现就非常简单，我们来看一下：

var MinStack = function() {

this.stack = [];

};

MinStack.prototype.push = function(x) {

this.stack.push(x);

};

MinStack.prototype.pop = function() {

this.stack.pop();

};

MinStack.prototype.top = function() {

return this.stack[this.stack.length - 1];

};

如何保证每次取最小呢，我们举一个例子：

如上图，我们需要一个辅助栈来记录最小值，

• 开始我们向stack push -2

• 此时辅助栈minStack，因为此时stack最小的是-2，也push -2

stack push 0

• 此时辅助站minStack 会用 0 跟 -2对比，-2更小，minstack会push -2

• stack push -3

• 此时辅助站minStack 会用 -3 跟 -2对比，-3更小，minstack会push -3

所以我们取最小的时候，总能在minStack中取到最小值，所以解法就出来了：

var MinStack = function() {

this.stack = [];

// 辅助栈

this.minStack = [];

};

MinStack.prototype.push = function(x) {

this.stack.push(x);

// 如果是第一次或者当前x比最小栈里的最小值还小才push x

if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]){

this.minStack.push(x)

} else {

this.minStack.push( this.minStack[this.minStack.length - 1])

}

};

MinStack.prototype.pop = function() {

this.stack.pop();

this.minStack.pop();

};

MinStack.prototype.top = function() {

return this.stack[this.stack.length - 1];

};

MinStack.prototype.getMin = function() {

return this.minStack[this.stack.length - 1];

};

动态规划

---

动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，我们从题目中体会一下

最大子序和

题目如下：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]

输出：1

示例 3：

输入：nums = [0]

输出：0

思路：

• 这道题可以用动态规划来解决，关键是找动态转移方程

• 我们动态转移方程中，dp表示每一个nums下标的最大自序和，所以dp[i]的意思为：包括下标i之前的最大连续子序列和为dp[i]。

确定转义方程的公示：

dp[i]只有两个方向可以推出来：

• 1、如果dp[i - 1] < 0，也就是当前遍历到nums的i，之前的最大子序和是负数，那么我们就没必要继续加它了，因为dp[i] = dp[i - 1] + nums[i] 会比nums[i]更小，所以此时还不如dp[i] = nums[i]，就是目前遍历到i的最大子序和呢

• 2、同理dp[i - 1] > 0，说明nums[i]值得去加dp[i - 1]，此时回避nums[i]更大

这样代码就出来了，其实更多的就是求dp，遍历nums每一个下标都会产生最大子序和，我们记录下来即可

var maxSubArray = function(nums) {

let res = nums[0];

const dp = [nums[0]];

for(let i=1;i < nums.length;i++){

if(dp[i-1]>0){

dp[i]=nums[i]+dp[i-1]

}else{

dp[i]=nums[i]

}

res=Math.max(dp[i],res)

}

return res

};

爬楼梯

先看题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

涉及到动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，

这道题我们假设dp[10]表示爬到是你爬到10阶就到达楼顶的方法数，

那么，dp[10] 是不是就是你爬到8阶，然后再走2步就到了，还有你走到9阶，再走1步就到了，

所以 dp[10] 是不是等于 dp[9]+dp[8]

延伸一下 dp[n] 是不是等于 dp[n - 1] + dp[n - 2]

代码如下：

var climbStairs = function(n) {

const dp = {};

dp[1] = 1;

dp[2] = 2;

for(let i = 3; i <= n; i++){

dp[i] = dp[i-1] + dp[i-2]

}

return dp[n]

};

数学问题

---

加一

题目如下：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]

输出：[1,2,4]

解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]

输出：[4,3,2,2]

解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]

输出：[1]

这个题的关键有两点：

• 需要有一个进位的变量carry记录到底进位是几

• 还需要一个每次迭代都重置和的变量sum来帮我们算是否进位，以及进位后的数字

记住这个题，这是两数字相加的套路，这次是+1，其实就是两数相加的题（腾讯面试遇到过两数相加）

var plusOne = function(digits) {

let carry = 1; // 进位（因为我们确定+1，初始化进位就是1）

for(let i = digits.length - 1; i >= 0; i–){

let sum = 0; // 这个变量是用来每次循环计算进位和digits[i]的值的

sum = digits[i] + carry;

digits[i] = sum % 10; // 模运算取个位数

carry = (sum / 10) | 0; // 除以10是取百位数，并且｜0表示舍弃小数位

}

if(digits[0] === 0) digits.unshift(carry);

return digits

};

x的平方根

题目如下：实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842…,

由于返回类型是整数，小数部分将被舍去。

这道题是典型的二分法解题，所以我们需要熟悉二分法的通用模板，我们出一个题：

在 [1, 2, 3, 4, 5, 6] 中找到 4，若存在则返回下标，不存在返回-1

const arr = [1, 2, 3, 4, 5, 6];

function getIndex1(arr, key) {

let low = 0;

const high = arr.length - 1;

while (low <= high) {

const mid = Math.floor((low + high) / 2);

if (key === arr[mid]) {

return mid;

}

if (key > arr[mid]) {

low = mid + 1;

} else {

height = mid - 1;

}

}

return -1;

}

console.log(getIndex1(arr, 5)); // 4

所以这道题的意思就是，我们找一个数平方跟x最相近的数，二分法的用法中也有找相近数的功能

所以代码如下：

var mySqrt = function(x) {

let [l , r] = [0, x];

let ans = -1;

while(l <= r) {

const mid = (l + r) >> 1;

if(mid * mid > x){

r = mid - 1

} else if(mid * mid < x){

ans = mid; // 防止越界

l = mid + 1;

} else {

ans = mid;

return ans;

}

}

return ans;

};

};

Excel表序列号

这个题比较重要，也比较基础，简而言之就是进制转换，必须牢牢掌握

题目如下：

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1

B -> 2

C -> 3

…

Z -> 26

AA -> 27

AB -> 28

…

示例 1：

输入：columnNumber = 1

输出：“A”

示例 2：

输入：columnNumber = 28

输出：“AB”

示例 3：

输入：columnNumber = 701

输出：“ZY”

示例 4：

输入：columnNumber = 2147483647

输出：“FXSHRXW”

说白了，这就是一道26进制的问题，以前我们知道10进制转2进制就是不停的除2，把余数加起来，26进制也是一样，不停的除26

思路：

• 初始化结果 ans = 0，遍历时将每个字母与 A 做减法，因为 A 表示 1，所以减法后需要每个数加 1，计算其代表的数值 num = 字母 - ‘A’ + 1

• 因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位

• 所以每遍历一位则ans = ans * 26 + num

• 以 ZY 为例，Z 的值为 26，Y 的值为 25，则结果为 26 * 26 + 25=701

var titleToNumber = function(columnTitle) {

let ans = 0;

for(let i = 0; i < columnTitle.length; i++){

ans = ans * 26 + (columnTitle[i].charCodeAt() - ‘A’.charCodeAt() + 1)

}

return ans;

};

阶乘中的零

题目：

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3

输出: 0

解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5

输出: 1

解释: 5! = 120, 尾数中有 1 个零.

这道题很简单，有多少个5就有多少个0，为什么这么说呢，我们分析一下题目

比如说 5!，

• 也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现只有1个0，怎么产生的呢，主要造成者就是 2 * 5 构造了一个0

• 再看看10!

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 其中，除了10 = 2 * 5和本身有一对2 * 5，所以有两个0，这样这道题的规律就出来了，我们再精进一步

如上图，每四个数字都会出现一个或者多个2的因子，但是只有每 5 个数字才能找到一个或多个5的因子。所以总体上看来，2的因子是远远多于5的因子的，所以我们只需要找5的倍数就可以了。

我们再进一步，按照上面的说法，我们需要计算比如10的阶乘有多少个0，要把10的阶乘算出来，其实我们只需要算10有几个5就好了，为什么呢

我们再进一步，按照上面的说法，我们需要计算比如10的阶乘有多少个0，要把10的阶乘算出来，其实我们只需要算10有几个5就好了，为什么呢

我们发现只有5的倍数的阶乘，才会产生5, 所以我们需要看看阶层数有多少个5，代码如下：

var trailingZeroes = function (n) {

let r = 0;

while (n > 1) {

n = Math.floor(n / 5);

r += n;

}

return r;

};

颠倒二进制位

题目如下：

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入: 00000010100101000001111010011100

输出: 00111001011110000010100101000000

解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，

因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：11111111111111111111111111111101

输出：10111111111111111111111111111111

解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，

因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

这类题，就是翻转字符串，我们可以把其转为字符串，再转成数组，再reverse一下，这里我们选用数学的方式去解答，不用这种转字符串的方式。

解答这道题之前，我们需要了解的前置知识：

1.与预算 &

1 & 1 // 1的2进制最后一位是1，得到1

2 & 0 // 2的2进制最后一位是0，得到0

3 & 1 // 3的2进制最后一位是1，得到1

4 & 0 // 4的2进制最后一位是0，得到0

所以我们知道了怎么取10进制最后1位的2进制是几。

2.JavaScript 使用 32 位按位运算数(意思是我们的按位运算都会转成32位，你的数字不能超过32位，会出问题)

• JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行。

• 在执行位运算之前，JavaScript 将数字转换为 32 位有符号整数。

• 执行按位操作后，结果将转换回 64 位 JavaScript 数。

3.’<< 1’ 运算

这个运算实际上就是把10进制乘以2，这个乘2在2进制上表现出右边填了一个0，我们距举例来说，

• 2的2进制是 10，2 << 1 得到4， 4的2进制是100，所以比10多了个0

• 3的2进制是 11，3 << 1 得到6。6的2进制是110，所以比11多了个0

以上就是规律

思路：循环取最后一位拼接起来即可

var reverseBits = function (n) {

let result = 0

for (let i = 0; i < 32; i++) {

result = (result << 1) + (n & 1)

n = n >> 1

}

// 为什么要 >>> 0 呢，一位javascript没有无符号整数，全是有符号的

// 不>>>0的话，得出来的值是负数，但是无符号整数是没有符号的

// javascript 有符号转化为无符号的方法就是>>>0

return result >>> 0

}

丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶：

你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

示例 1：

输入：nums = [3,0,1]

输出：2

解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]

输出：2

解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

这题很简单，就是用0-n的总和减去数组总和

• 0 - n 的总和用等差数列:（首数+尾数）* 项数 / 2 来求

var missingNumber = function(nums) {

const len = nums.length

let sum = ((1 + len) * len) / 2

for (let i = 0; i < len; i++) {

sum -= nums[i]

}

return sum

}

的幂

---

题目如下：

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3的x次方

示例 1：

输入：n = 27

输出：true

示例 2：

输入：n = 0

输出：false

示例 3：

输入：n = 9

输出：true

思路

• 我们拿27来说：27 = 3 * 3 * 3，所以27是3的幂次方

• 我们拿29来说：29 = 3 * 3 * 3点几

也就是说，如果是3的幂次方，一直除以3，除到最后就等于1比如27/3/3/3等于1 如果不是3的幂次方，除到最后就是3点几/3 等于1点几

代码就出来了判断是不是等于1即可

var isPowerOfThree = function(n) {

while(n >= 3){

n /= 3;

}

return n === 1;

};

Fizz Buzz

这个题没啥好说的，就按照题目说的写代码就行，先看题目：

写一个程序，输出从 1 到 n 数字的字符串表示。

1.如果 n 是3的倍数，输出“Fizz”；

2.如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:

[

“1”,

“2”,

“Fizz”,

“4”,

“Buzz”,

“Fizz”,

“7”,

“8”,

“Fizz”,

“Buzz”,

“11”,

“Fizz”,

“13”,

“14”,

“FizzBuzz”

]

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注：前端）

结尾

学习html5、css、javascript这些基础知识，学习的渠道很多，就不多说了，例如，一些其他的优秀博客。但是本人觉得看书也很必要，可以节省很多时间，常见的javascript的书，例如：javascript的高级程序设计，是每位前端工程师必不可少的一本书，边看边用，了解js的一些基本知识，基本上很全面了，如果有时间可以读一些，js性能相关的书籍，以及设计者模式，在实践中都会用的到。

资料领取方式：戳这里获取

29 = 3 * 3 * 3点几

也就是说，如果是3的幂次方，一直除以3，除到最后就等于1比如27/3/3/3等于1 如果不是3的幂次方，除到最后就是3点几/3 等于1点几

代码就出来了判断是不是等于1即可

var isPowerOfThree = function(n) {

while(n >= 3){

n /= 3;

}

return n === 1;

};

Fizz Buzz

这个题没啥好说的，就按照题目说的写代码就行，先看题目：

写一个程序，输出从 1 到 n 数字的字符串表示。

1.如果 n 是3的倍数，输出“Fizz”；

2.如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:

[

“1”,

“2”,

“Fizz”,

“4”,

“Buzz”,

“Fizz”,

“7”,

“8”,

“Fizz”,

“Buzz”,

“11”,

“Fizz”,

“13”,

“14”,

“FizzBuzz”

]

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

[外链图片转存中…(img-0RCrI2KC-1712464497443)]

[外链图片转存中…(img-D9Fl5MZZ-1712464497444)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

[外链图片转存中…(img-BVaORcbC-1712464497444)]

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注：前端）

结尾

学习html5、css、javascript这些基础知识，学习的渠道很多，就不多说了，例如，一些其他的优秀博客。但是本人觉得看书也很必要，可以节省很多时间，常见的javascript的书，例如：javascript的高级程序设计，是每位前端工程师必不可少的一本书，边看边用，了解js的一些基本知识，基本上很全面了，如果有时间可以读一些，js性能相关的书籍，以及设计者模式，在实践中都会用的到。

资料领取方式：戳这里获取