【面试】盘点10个高频的前端算法题，你全都会了吗？

落日映苍穹つ 2024-04-22 12:28 28阅读 0赞

**前言**

> ? 大家好，我是南木元元，热爱技术和分享，欢迎大家交流，一起学习进步！
> 
> ? **个人主页：[南木元元][Link 1]**

现在前端的面试中，算法出现的频率越来越高了，大厂更是必考算法 。本文就来分享一下10个常见的前端算法题，重要的地方已添加注释，如有不正确的地方，欢迎多多指正。

--------------------

**目录**

1.合并两个有序数组

2.两数之和

3.三数之和

4.反转链表

5.全排列

6.有效的括号

7.二叉树的中序遍历

8.翻转二叉树

9.K个一组翻转链表

10.最长递增子序列

结语

--------------------

## 1.合并两个有序数组 ##

**题目**：给定两个非递减的有序数组nums1和nums2，合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。

**示例：**

![7ada9954004847389de08ac038b8af9f.png][]

来源：[LeetCode第88题][LeetCode_88]

**代码实现：**

//方法1：将nums2放到nums1的尾部，然后直接对整个数组进行排序
    var merge = function (nums1, m, nums2, n) {
      nums1.splice(m, n, ...nums2);
      nums1.sort((a, b) => a - b);
    };
    
    //方法2：逆向双指针，从后往前遍历
    var merge = function (nums1, m, nums2, n) {
      let i = m - 1,
        j = n - 1,
        k = m + n - 1;
      while (i >= 0 || j >= 0) {
        if (i < 0) {
          nums1[k--] = nums2[j--];
        } else if (j < 0) {
          nums1[k--] = nums1[i--];
        } else if (nums1[i] <= nums2[j]) {
          nums1[k--] = nums2[j--];
        } else {
          nums1[k--] = nums1[i--];
        }
      }
      return nums1;
    };

## 2.两数之和 ##

**题目：**给定一个数组nums和一个目标值target，在数组中找出和为目标值的两个数，并返回下标。

**示例：**

![2b8774ca7ba24a28ba9bc35cff7dd59a.png][]

来源：[LeetCode第1题][LeetCode_1]

**代码实现：**

// 哈希法，利用map
    var twoSum = function (nums, target) {
      let map = new Map();
      // 遍历当前元素，并在map中寻找是否有匹配的key
      for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
          return [i, map.get(target - nums[i])];
        } else {
          // 没找到与当前匹配的元素，就把当前元素及对应下标加入map
          map.set(nums[i], i);
        }
      }
    };

## 3.三数之和 ##

**题目：**给你一个包含 n 个整数的数组 nums，判断nums中是否存在三个元素a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

**示例：**

![4c50d7d9ee114597b4552ef592b2f2b3.png][]

来源：[LeetCode第15题][LeetCode_15]

**代码实现：**

// 双指针法
    var threeSum = function (nums) {
      let res = [];
      //排序
      nums.sort((a, b) => a - b);
      for (let i = 0; i < nums.length; i++) {
        //如果当前第一个数大于0直接返回res
        if (nums[i] > 0) {
          return res;
        }
        //对第一个元素去重
        if (i > 0 && nums[i] === nums[i - 1]) {
          continue;
        }
        let l = i + 1;
        let r = nums.length - 1;
        while (l < r) {
          if (nums[i] + nums[l] + nums[r] > 0) {
            r--;
          } else if (nums[i] + nums[l] + nums[r] < 0) {
            l++;
          } else {
            res.push([nums[i], nums[l], nums[r]]);
            // 对第2、3个元素去重
            while (l < r && nums[l] === nums[l + 1]) {
              l++;
            }
            while (l < r && nums[r] === nums[r - 1]) {
              r--;
            }
            l++;
            r--;
          }
        }
      }
      return res;
    };

## 4.反转链表 ##

**题目：**给你一个单链表的头节点head，反转单链表。

**示例：**

![bec58c5aa99b4413ae9274005d0d02e7.png][]

来源：[LeetCode第206题][LeetCode_206]

**代码实现：**

// 1.双指针法，只需要改变链表的next指针的指向
    var reverseList = function(head) {
        let p = null;
        let q = head;
        let tmp = null; //保存下一个节点
        while(q) {
            tmp = q.next;
            q.next = p;
            p = q;
            q = tmp;
        }
        return p;
    };
    
    // 2.递归法
    var reverseList = function(head) {
        var reverse = function(p, q) {
            if(q === null) {
                return p;
            }
            let tmp = q.next;
            q.next = p;
            p = q;
            return reverse(p, tmp); //注意这里必须return
        }
        return reverse(null, head);
    };

## 5.全排列 ##

**题目：**给定一个没有重复数字的序列，返回其所有可能的全排列。

**示例：**

![8d560f2c7c3a481fbe2820cc8ad8b10f.png][]

来源：[LeetCode第46题][LeetCode_46]

**实现代码：**

// 回溯
    var permute = function (nums) {
      let res = [];
      let path = [];
      var bt = function (used) {
        if (path.length === nums.length) {
          res.push([...path]);
          return;
        }
        for (let i = 0; i < nums.length; i++) {
          //used数组，记录此时path里已经选择的元素,一个排列里一个元素只能使用一次
          if (used[i] === 1) {
            continue;
          }
          path.push(nums[i]);
          used[i] = 1;
          bt(used);
          used[i] = 0;
          path.pop();
        }
      };
      bt([]);
      return res;
    };

## 6.有效的括号 ##

**题目：**给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。

**示例：**

![d0a97eab53e24d4ca0f8cc5d5ae33b1e.png][]

来源：[LeetCode第20题][LeetCode_20]

**实现代码：**

## 7.二叉树的中序遍历 ##

**题目：**给定一个二叉树的根节点root，返回它的中序遍历。

**示例：**

![ce827916a533418e8130e827f881a688.png][]

来源：[LeetCode第94题][LeetCode_94]

**代码实现：**

// 1.递归
    法var preorderTraversal = function (root) {
      let res = [];
      var dfs = function (root) {
        if (!root) {
          return;
        }
        dfs(root.left); //左
        res.push(root.val); //中
        dfs(root.right); //右
      };
      dfs(root);
      return res;
    };
    
    // 2.迭代法（重点）
    var inorderTraversal = function (root) {
      if (!root) {
        return [];
      }
      let res = [];
      let stack = [];
      //定义一个指针，指向当前遍历节点
      let cur = root; 
      while (cur || stack.length) {
        if (cur) {
          //一直遍历到左下
          stack.push(cur);
          cur = cur.left;
        } else {
          cur = stack.pop();
          res.push(cur.val);
          cur = cur.right;
        }
      }
      return res;
    };

## 8.翻转二叉树 ##

**题目：**给你一棵二叉树的根节点root，翻转这棵树，并返回其根节点。

**示例：**

![e7622821a30b4a9d9fd58638c7281bc5.png][]

来源：[LeetCode第102题][LeetCode_102]

**代码实现：**

// 1.递归，先交换根节点左右子树，再分别对左右子树进行处理
    var invertTree = function (root) {
      if (!root) {
        return root;
      }
      let tmp = root.left;
      root.left = root.right;
      root.right = tmp;
      invertTree(root.left);
      invertTree(root.right);
      return root;
    };
    
    // 2.迭代
    var invertTree = function(root) {
        let stack = [];
        if(root == null) {
            return root;
        }
        stack.push(root);
        while(stack.length != 0) {
            let node = stack.pop();
            if(node != null) {
                if(node.right) {
                    stack.push(node.right); 
                }
                if(node.left) {
                    stack.push(node.left);  
                }
                stack.push(node);   
                stack.push(null);
            } else {
                let cur = stack.pop();  
                //每遍历一个节点，就交换它的左右子树
                [cur.left, cur.right] = [cur.right, cur.left];  
            }
        }
        return root;
    };

## 9.K个一组翻转链表 ##

**题目：**给你一个链表的头节点head，每k个节点一组进行翻转，返回修改后的链表。

**示例：**

![808f8bdd569f4e149c822c57e3e32c62.png][]

来源：[LeetCode第25题][LeetCode_25]

**代码实现：**

## 10.最长递增子序列 ##

**题目：**给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

**示例：**

![d802d6e7cc784a0584651f173d2a174d.png][]

来源：[LeetCode第300题][LeetCode_300]

代码实现：

**题目扩展：**给你一个整数数组 nums ，找出其最长严格递增子序列。

**示例：**

![cd0e74f65fe94b7f8235794a3a54309b.png][]

**实现代码：**

## 结语 ##

?如果此文对你有帮助的话，欢迎?**关注**、?**点赞**、⭐**收藏**、✍️**评论**，支持一下博主~

[Link 1]: https://blog.csdn.net/weixin_43288600
[7ada9954004847389de08ac038b8af9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/a84391e3a1b542579f64738c799b16a4.png
[LeetCode_88]: https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150
[2b8774ca7ba24a28ba9bc35cff7dd59a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/41256d59baef46a3817ddee6c3ba35dc.png
[LeetCode_1]: https://leetcode.cn/problems/two-sum/description/
[4c50d7d9ee114597b4552ef592b2f2b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/ab4d39446370439099f7cbb1b4efec1c.png
[LeetCode_15]: https://leetcode.cn/problems/3sum/description/
[bec58c5aa99b4413ae9274005d0d02e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/7b61de0309a74e3a88bfde946e39dde3.png
[LeetCode_206]: https://leetcode.cn/problems/reverse-linked-list/description/
[8d560f2c7c3a481fbe2820cc8ad8b10f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/dcc01166a0df41439090f01f2992499c.png
[LeetCode_46]: https://leetcode.cn/problems/permutations/description/
[d0a97eab53e24d4ca0f8cc5d5ae33b1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/fe22805387ab4fd78ab44655e750d5e7.png
[LeetCode_20]: https://leetcode.cn/problems/valid-parentheses/description/
[ce827916a533418e8130e827f881a688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/1ff75dc882e7400e86ea30b93b064f33.png
[LeetCode_94]: https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
[e7622821a30b4a9d9fd58638c7281bc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/de5d34d84cff4d5e982122ed5db06d26.png
[LeetCode_102]: https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
[808f8bdd569f4e149c822c57e3e32c62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/3f4f544f2c4149a094514cc10b8616d0.png
[LeetCode_25]: https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
[d802d6e7cc784a0584651f173d2a174d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/33e4e3ff800a4cf4a49fdb9a69ce0328.png
[LeetCode_300]: https://leetcode.cn/problems/longest-increasing-subsequence/description/
[cd0e74f65fe94b7f8235794a3a54309b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/eae9392b22634d77904182961b944fc7.png