前端笔试面试题目——数据结构和算法篇(一）
大厂前端笔试面试题中常见的算法和数据结构题目可以总结为以下几个方面：
数据结构题目
-
数组与链表：
- 数组与链表的区别，包括元素个数、存储单元、元素的顺序关系等。
- 链表的反转、合并等操作。
- 判断链表中是否有环。
-
栈与队列：
- 栈的后进先出（LIFO）特性，以及相关的操作如入栈、出栈等。
- 队列的先进先出（FIFO）特性，以及相关的操作如入队、出队等。
-
哈希表：
- 哈希表的基本原理，以及哈希函数的设计。
- Object作为HashMap的key时的要求（如hashcode不能变）。
-
二叉树：
- 二叉树的基本概念和遍历方法（前序、中序、后序、层次遍历）。
- 在二叉树中查找特定值的路径，如和等于给定值的路径。
- 二叉搜索树的构建和查找操作。
-
堆：
- 堆的基本概念，包括最大堆和最小堆。
- 堆排序算法的实现和原理。
算法题目
-
排序算法：
- 常见的排序算法，如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。
- 各种排序算法的时间复杂度和空间复杂度分析。
-
查找算法：
- 线性查找和二分查找算法的实现和原理。
- 在特定数据结构（如二叉搜索树）中查找特定值。
-
字符串算法：
- 判断字符串是否为回文。
- 反转字符串。
- 查找字符串中的最长公共前缀。
-
动态规划：
- 动态规划的基本原理和解题步骤。
- 应用动态规划解决特定问题，如求数组中的连续子向量的最大和等。
-
回溯算法：
- 回溯算法的基本原理和解题步骤。
- 应用回溯算法解决特定问题，如找出数组中和为S的一对组合等。
-
其他算法：
- 判断一个链表是否为回文链表。
- 实现一个压缩URL的算法。
- 实现一个全局唯一且自增的ID生成算法。
综合题目
-
算法与数据结构的结合：
- 在特定数据结构（如二叉树、链表等）上应用特定算法（如排序、查找等）。
- 设计和实现特定的数据结构（如哈希表、图等）来解决实际问题。
-
算法优化：
- 分析特定算法的时间复杂度和空间复杂度，并进行优化。
- 应用特定技巧（如哈希、分治、动态规划等）来优化算法的性能。
-
代码实现：
- 根据题目要求，手写特定算法或数据结构的代码实现。
- 对代码进行调试和优化，确保其正确性和高效性。
这些题目涵盖了前端笔试面试中常见的算法和数据结构知识点，通过练习这些题目，可以加深对算法和数据结构的理解，提高编程能力和解决问题的能力。
大厂前端笔试面试题中常见的算法和数据结构题目涵盖多个方面，以下是一些典型的题目类型及示例：
算法题目
-
反转链表
- 题目描述：给定一个单链表的头节点head，反转单链表并返回新的头节点。
- 示例：输入一个链表1->2->3->4->5，输出5->4->3->2->1。
-
合并两个有序数组
- 题目描述：给定两个非递减的有序数组nums1和nums2，合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
- 示例：nums1=[1,2,3,0,0,0]，m=3；nums2=[2,5,6]，n=3，合并后nums1=[1,2,2,3,5,6]。
-
两数之和
- 题目描述：给定一个数组nums和一个目标值target，在数组中找出和为目标值的两个数，并返回它们的下标。
- 示例：nums=[2,7,11,15]，target=9，返回[0,1]（因为nums[0]+nums[1]=2+7=9）。
-
三数之和
- 题目描述：给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a、b、c，使得a+b+c=0？找出所有满足条件且不重复的三元组。
- 示例：nums=[-1,0,1,2,-1,-4]，满足条件的三元组为[[-1,-1,2],[-1,0,1]]。
-
全排列
- 题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
- 示例：输入[1,2,3]，输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]。
-
最长递增子序列
- 题目描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。
- 示例：输入[10,9,2,5,3,7,101,18]，输出最长递增子序列[2,3,7,101]，长度为4。
-
判断链表是否为回文链表
- 题目描述：给定一个单链表，判断该链表是否为回文链表。
- 示例：输入1->2->2->1，返回true；输入1->2->3，返回false。
数据结构题目
-
二叉树的中序遍历
- 题目描述：给定一个二叉树的根节点，返回该二叉树中序遍历的结果。
- 示例：输入二叉树[1,null,2,3]，输出[1,3,2]。
-
二叉树的层次遍历
- 题目描述：给定一个二叉树，返回其按层次遍历（广度优先搜索）的结果。
- 示例：输入二叉树[3,9,20,null,null,15,7]，输出[[3],[9,20],[15,7]]。
-
二叉搜索树的最近公共祖先
- 题目描述：给定一个二叉搜索树和树中的两个节点p和q，找到它们的最近公共祖先节点。
- 示例：输入二叉搜索树root=[6,2,8,0,4,7,9,null,null,3,5]，节点p=2，节点q=8，输出6（即节点2和节点8的最近公共祖先）。
-
实现一个栈
- 题目描述：实现一个栈的数据结构，支持基本的入栈（push）和出栈（pop）操作。
- 示例：栈的初始状态为空，依次执行push(1)，push(2)，pop()操作后，栈顶元素为1。
-
实现一个队列
- 题目描述：实现一个队列的数据结构，支持基本的入队（enqueue）和出队（dequeue）操作。
- 示例：队列的初始状态为空，依次执行enqueue(1)，enqueue(2)，dequeue()操作后，队列的头元素为1。
-
实现一个哈希表
- 题目描述：实现一个哈希表（散列表）的数据结构，支持基本的插入（put）和查找（get）操作。
- 示例：哈希表的初始状态为空，依次执行put(“key1”, “value1”)，put(“key2”, “value2”)，get(“key1”)操作后，返回"value1"。
这些题目不仅考察了前端开发者对算法和数据结构的理解程度，还考验了他们的编程能力和解决问题的能力。在准备面试时，建议深入理解这些题目的解法，并尝试自己编写代码实现。
当然，以下是对您列出的前端JS算法题目的解答及代码示例：
1. 删除链表中重复的元素
function deleteDuplicates(head) {
if (!head) return null;
let current = head;
while (current && current.next) {
if (current.value === current.next.value) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
注意：此代码假设链表节点有value和next属性。
2. 找到链表中的倒数第k个节点
function findKthFromEnd(head, k) {
let fast = head, slow = head;
// Move fast pointer k steps ahead
for (let i = 0; i < k; i++) {
if (!fast) return null; // If k is greater than length of list
fast = fast.next;
}
// Move both pointers until fast reaches the end
while (fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
3. 判断链表中是否有环
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
4. 合并两个有序数组
function mergeSortedArrays(arr1, arr2) {
let merged = [], i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
merged.push(arr1[i]);
i++;
} else {
merged.push(arr2[j]);
j++;
}
}
// Concatenate remaining elements
return merged.concat(arr1.slice(i)).concat(arr2.slice(j));
}
5. 合并两个有序链表
function mergeSortedLists(l1, l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1.value < l2.value) {
l1.next = mergeSortedLists(l1.next, l2);
return l1;
} else {
l2.next = mergeSortedLists(l1, l2.next);
return l2;
}
}
6. 验证回文串
function isPalindrome(str) {
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
7. 反转链表
function reverseList(head) {
let prev = null, current = head, next = null;
while (current) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
8. 判断子序列
function isSubsequence(s, t) {
let sIndex = 0, tIndex = 0;
while (sIndex < s.length && tIndex < t.length) {
if (s[sIndex] === t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex === s.length;
}
9. 删除排序数组中的重复项
function removeDuplicates(arr) {
if (!arr.length) return [];
let unique = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (arr[i] !== arr[i - 1]) {
unique.push(arr[i]);
}
}
return unique;
}
10. 寻找链表的中间节点
function findMiddleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
11. 删除链表中的节点（假设删除值为val的节点）
function deleteNode(head, val) {
if (!head) return null;
if (head.value === val) return head.next; // If head node is the one to be deleted
let current = head;
while (current.next && current.next.value !== val) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
return head;
}
12. 移动零
function moveZeroes(arr) {
let left = 0, right = 0;
while (right < arr.length) {
if (arr[right] !== 0) {
[arr[left], arr[right]] = [arr[right], arr[left]]; // Swap
left++;
}
right++;
}
// Fill remaining spaces with zeros
for (let i = left; i < arr.length; i++) {
arr[i] = 0;
}
return arr;
}
注意：以上代码示例是基于对链表和数组的基本操作，并未包含完整的链表节点定义或错误处理。在实际应用中，可能需要添加额外的代码来处理边界情况或错误输入。
当然，以下是对您列出的算法题目的解答及代码示例：
1. 两数之和
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
代码：
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
throw new Error('No two sum solution');
}
2. 冒泡排序
题目：实现冒泡排序算法。
代码：
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Swap
}
}
}
return arr;
}
3. 单次购买的最大利润
题目：给定一个整数数组，其中第 i 个元素是给定股票在第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
代码：
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let price of prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
4. 斐波那契数列
题目：实现一个函数来计算斐波那契数列的第 n 项。
代码：
function fibonacci(n) {
if (n <= 1) return n;
let a = 0, b = 1, fib;
for (let i = 2; i <= n; i++) {
fib = a + b;
a = b;
b = fib;
}
return fib;
}
或者，使用递归（但效率较低，有重叠子问题）：
function fibonacciRecursive(n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
5. 最大子序和
题目：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
代码：
function maxSubArray(nums) {
let maxSoFar = nums[0], maxEndingHere = nums[0];
for (let i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
6. 爬楼梯
题目：假设你正在爬一段楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
代码：
function climbStairs(n) {
if (n <= 2) return n;
let a = 1, b = 2, ways;
for (let i = 3; i <= n; i++) {
ways = a + b;
a = b;
b = ways;
}
return ways;
}
7. 试除法求约数
题目：实现一个函数来找出给定整数的所有约数。
代码：
function getDivisors(num) {
const divisors = [];
for (let i = 1; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
divisors.push(i);
if (i !== num / i) {
divisors.push(num / i);
}
}
}
divisors.sort((a, b) => a - b); // Optional: Sort divisors in ascending order
return divisors;
}
8. 试除法判定质数
题目：实现一个函数来判断一个整数是否为质数。
代码：
function isPrime(num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 === 0 || num % 3 === 0) return false;
for (let i = 5; i * i <= num; i += 6) {
if (num % i === 0 || num % (i + 2) === 0) return false;
}
return true;
}
以上代码示例提供了基本的算法实现，并假设输入是有效的。在实际应用中，可能需要添加额外的输入验证和错误处理代码。