前端笔试面试题目——数据结构和算法篇(一)

ops/2024/12/23 20:00:39/

大厂前端笔试面试题中常见的算法和数据结构题目可以总结为以下几个方面:

数据结构题目

  1. 数组与链表

    • 数组与链表的区别,包括元素个数、存储单元、元素的顺序关系等。
    • 链表的反转、合并等操作。
    • 判断链表中是否有环。
  2. 栈与队列

    • 栈的后进先出(LIFO)特性,以及相关的操作如入栈、出栈等。
    • 队列的先进先出(FIFO)特性,以及相关的操作如入队、出队等。
  3. 哈希表

    • 哈希表的基本原理,以及哈希函数的设计。
    • Object作为HashMap的key时的要求(如hashcode不能变)。
  4. 二叉树

    • 二叉树的基本概念和遍历方法(前序、中序、后序、层次遍历)。
    • 在二叉树中查找特定值的路径,如和等于给定值的路径。
    • 二叉搜索树的构建和查找操作。
    • 堆的基本概念,包括最大堆和最小堆。
    • 堆排序算法的实现和原理。

算法题目

  1. 排序算法

    • 常见的排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。
    • 各种排序算法的时间复杂度和空间复杂度分析。
  2. 查找算法

    • 线性查找和二分查找算法的实现和原理。
    • 在特定数据结构(如二叉搜索树)中查找特定值。
  3. 字符串算法

    • 判断字符串是否为回文。
    • 反转字符串。
    • 查找字符串中的最长公共前缀。
  4. 动态规划

    • 动态规划的基本原理和解题步骤。
    • 应用动态规划解决特定问题,如求数组中的连续子向量的最大和等。
  5. 回溯算法

    • 回溯算法的基本原理和解题步骤。
    • 应用回溯算法解决特定问题,如找出数组中和为S的一对组合等。
  6. 其他算法

    • 判断一个链表是否为回文链表。
    • 实现一个压缩URL的算法。
    • 实现一个全局唯一且自增的ID生成算法。

综合题目

  1. 算法与数据结构的结合

    • 在特定数据结构(如二叉树、链表等)上应用特定算法(如排序、查找等)。
    • 设计和实现特定的数据结构(如哈希表、图等)来解决实际问题。
  2. 算法优化

    • 分析特定算法的时间复杂度和空间复杂度,并进行优化。
    • 应用特定技巧(如哈希、分治、动态规划等)来优化算法的性能。
  3. 代码实现

    • 根据题目要求,手写特定算法或数据结构的代码实现。
    • 对代码进行调试和优化,确保其正确性和高效性。

这些题目涵盖了前端笔试面试中常见的算法和数据结构知识点,通过练习这些题目,可以加深对算法和数据结构的理解,提高编程能力和解决问题的能力。
大厂前端笔试面试题中常见的算法和数据结构题目涵盖多个方面,以下是一些典型的题目类型及示例:

算法题目

  1. 反转链表

    • 题目描述:给定一个单链表的头节点head,反转单链表并返回新的头节点。
    • 示例:输入一个链表1->2->3->4->5,输出5->4->3->2->1。
  2. 合并两个有序数组

    • 题目描述:给定两个非递减的有序数组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]。
  3. 两数之和

    • 题目描述:给定一个数组nums和一个目标值target,在数组中找出和为目标值的两个数,并返回它们的下标。
    • 示例:nums=[2,7,11,15],target=9,返回[0,1](因为nums[0]+nums[1]=2+7=9)。
  4. 三数之和

    • 题目描述:给定一个包含n个整数的数组nums,判断nums中是否存在三个元素a、b、c,使得a+b+c=0?找出所有满足条件且不重复的三元组。
    • 示例:nums=[-1,0,1,2,-1,-4],满足条件的三元组为[[-1,-1,2],[-1,0,1]]。
  5. 全排列

    • 题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。
    • 示例:输入[1,2,3],输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]。
  6. 最长递增子序列

    • 题目描述:给定一个无序的整数数组,找到其中最长递增子序列的长度。
    • 示例:输入[10,9,2,5,3,7,101,18],输出最长递增子序列[2,3,7,101],长度为4。
  7. 判断链表是否为回文链表

    • 题目描述:给定一个单链表,判断该链表是否为回文链表。
    • 示例:输入1->2->2->1,返回true;输入1->2->3,返回false。

数据结构题目

  1. 二叉树的中序遍历

    • 题目描述:给定一个二叉树的根节点,返回该二叉树中序遍历的结果。
    • 示例:输入二叉树[1,null,2,3],输出[1,3,2]。
  2. 二叉树的层次遍历

    • 题目描述:给定一个二叉树,返回其按层次遍历(广度优先搜索)的结果。
    • 示例:输入二叉树[3,9,20,null,null,15,7],输出[[3],[9,20],[15,7]]。
  3. 二叉搜索树的最近公共祖先

    • 题目描述:给定一个二叉搜索树和树中的两个节点p和q,找到它们的最近公共祖先节点。
    • 示例:输入二叉搜索树root=[6,2,8,0,4,7,9,null,null,3,5],节点p=2,节点q=8,输出6(即节点2和节点8的最近公共祖先)。
  4. 实现一个栈

    • 题目描述:实现一个栈的数据结构,支持基本的入栈(push)和出栈(pop)操作。
    • 示例:栈的初始状态为空,依次执行push(1),push(2),pop()操作后,栈顶元素为1。
  5. 实现一个队列

    • 题目描述:实现一个队列的数据结构,支持基本的入队(enqueue)和出队(dequeue)操作。
    • 示例:队列的初始状态为空,依次执行enqueue(1),enqueue(2),dequeue()操作后,队列的头元素为1。
  6. 实现一个哈希表

    • 题目描述:实现一个哈希表(散列表)的数据结构,支持基本的插入(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;
}

注意:此代码假设链表节点有valuenext属性。

2. 找到链表中的倒数第k个节点

function findKthFromEnd(head, k) {let fast = head, slow = head;// Move fast pointer k steps aheadfor (let i = 0; i < k; i++) {if (!fast) return null; // If k is greater than length of listfast = fast.next;}// Move both pointers until fast reaches the endwhile (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 elementsreturn 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 deletedlet 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]]; // Swapleft++;}right++;}// Fill remaining spaces with zerosfor (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 阶你才能到达楼顶。每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶?

代码

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 orderreturn 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;
}

以上代码示例提供了基本的算法实现,并假设输入是有效的。在实际应用中,可能需要添加额外的输入验证和错误处理代码。


http://www.ppmy.cn/ops/144380.html

相关文章

如何在Windows系统上安装和配置Maven

Maven是一个强大的构建和项目管理工具&#xff0c;广泛应用于Java项目的自动化构建、依赖管理、项目构建生命周期控制等方面。在Windows系统上安装Maven并配置环境变量&#xff0c;是开发者开始使用Maven的第一步。本文将详细介绍如何在Windows系统上安装和配置Maven&#xff0…

Linux 端口操作

安装netstat yum -y install net-tools 检测端口占用 netstat -npl | grep "端口" 安装lsof lsof yum -y install lsof 检测端口占用 lsof -i :端口号 安装nc yum -y install nc 查看对方端口是否开放 nc -vz 对方ip 对方端口 安装telnet telnet yum -y in…

BTP Integration Suite CPI Apache Camel

官网文档&#xff1a; https://help.sap.com/docs/integration-suite/sap-integration-suite/what-is-sap-integration-suite CPI 云集成(CPI)有以下几个特性&#xff1a; SAP Cloud Integration通过消息交换支持端到端流程集成。 它基于Apache软件基金会的开源框架Camel。 …

如何使用 Python 连接 PostgreSQL 数据库?

在Python开发中&#xff0c;连接PostgreSQL数据库是一个常见的需求。 我们可以使用多种库来实现这一功能&#xff0c;其中最常用的是psycopg2。 下面我将详细介绍如何使用psycopg2来连接PostgreSQL数据库&#xff0c;并提供一些实际开发中的建议和注意事项。 1. 使用 psycop…

JSX和vue模版哪个更好?

JSX和Vue模板各有优缺点&#xff0c;选择哪种取决于具体需求和个人偏好。‌ JSX的优点 ‌灵活性‌&#xff1a;JSX允许在JavaScript代码中直接插入任意表达式&#xff0c;这使得它在处理复杂逻辑时更加灵活。例如&#xff0c;条件渲染和循环渲染可以通过JavaScript的标准语法…

<代码随想录> 算法训练营-2024.12.19

今日专题&#xff1a;动态规划 完全背包&#xff08;每个物品可以选n次&#xff09; 动态规划分析的时候把状态转移图画出来 先遍历物品再遍历背包求排列数&#xff0c;先遍历背包再遍历物品求组合数 518. 零钱兑换 II class Solution:def change(self, amount: int, coins…

启动springboot项目时报错Web server failed to start. Port 8080 was already in use.

目录 一、Web server failed to start. Port 8080 was already in use. 解决方法 一、Web server failed to start. Port 8080 was already in use. 报错信息&#xff1a;Web server failed to start. Port 8080 was already in use. 使用IDEA开发Spring Boot项目&#xff0…

【Linux】AlmaLinux 9.5虚拟机安装过程记录分享

关于AlmaLinux系统感兴趣的&#xff0c;可以去我之前写的另外一篇博客里面看看&#xff1a; https://blog.csdn.net/cnskylee/article/details/143142690 语言&#xff0c;选择【简体中文&#xff08;中国&#xff09;】&#xff0c;点击【继续】&#xff0c;进入后续设置 在…