2023前端常见的算法题都有哪些？-蒲公英云

以下是20个常见的前端算法题，每个算法题都包含代码解析。

1. 反转字符串

题目描述

将给定字符串中的字符顺序反转。

代码解析

function reverseString(str) {
  return str.split('').reverse().join('');
}

2. 阶乘

题目描述

计算一个整数的阶乘。

代码解析

function factorial(num) {
  if (num === 0) {
    return 1;
  } else {
    return num * factorial(num - 1);
  }
}

3. 斐波那契数列

题目描述

输出斐波那契数列中的前 n 项。

代码解析

function fibonacci(n) {
  if (n === 1) {
    return [0, 1];
  } else {
    var arr = fibonacci(n - 1);
    arr.push(arr[arr.length - 1] + arr[arr.length - 2]);
    return arr;
  }
}

4. 翻转二叉树

题目描述

翻转一棵二叉树。

代码解析

function invertTree(root) {
  if (root !== null) {
    var left = invertTree(root.left);
    var right = invertTree(root.right);
    root.left = right;
    root.right = left;
  }
  return root;
}

5. 数组去重

题目描述

将一个数组中重复的元素去掉。

代码解析

function uniqueArray(arr) {
  var result = [];
  for (var i = 0; i < arr.length; i++) {
    if (result.indexOf(arr[i]) === -1) {
      result.push(arr[i]);
    }
  }
  return result;
}

6. 判断回文字符串

题目描述

判断一个字符串是否是回文字符串。

代码解析

function isPalindrome(str) {
  var reversedStr = str.split('').reverse().join('');
  return str === reversedStr;
}

7. 二分查找

题目描述

在一个已排序的数组中查找一个元素。

代码解析

function binarySearch(arr, target) {
  var left = 0;
  var right = arr.length - 1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

8. 冒泡排序

题目描述

将一个数组按照从小到大的顺序排列。

代码解析

function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

9. 快速排序

题目描述

将一个数组按照从小到大的顺序排列。

代码解析

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

10. 计数排序

题目描述

将一个数组按照从小到大的顺序排列。

代码解析

function countingSort(arr) {
  var max = arr[0];
  var min = arr[0];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  var count = [];
  for (var j = min; j <= max; j++) {
    count[j] = 0;
  }
  for (var k = 0; k < arr.length; k++) {
    count[arr[k]]++;
  }
  var result = [];
  for (var m = min; m <= max; m++) {
    while (count[m] > 0) {
      result.push(m);
      count[m]--;
    }
  }
  return result;
}

11. 求最大公约数

题目描述

求两个整数的最大公约数。

代码解析

function gcd(num1, num2) {
  if (num2 === 0) {
    return num1;
  }
  return gcd(num2, num1 % num2);
}

12. 斐波那契数列（优化版）

题目描述

输出斐波那契数列的第 n 项。

代码解析

function fibonacci(n) {
  var arr = [0, 1];
  for (var i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

13. 编辑距离

题目描述

计算两个字符串之间的编辑距离。

代码解析

function editDistance(str1, str2) {
  var m = str1.length;
  var n = str2.length;
  var dp = [];
  for (var i = 0; i <= m; i++) {
    dp[i] = [];
    for (var j = 0; j <= n; j++) {
      if (i === 0) {
        dp[i][j] = j;
      } else if (j === 0) {
        dp[i][j] = i;
      } else if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[m][n];
}

14. 爬楼梯

题目描述

有一个 n 级的楼梯，每次可以爬一级或两级，问有多少种爬楼梯的方案。

代码解析

function climbStairs(n) {
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 2;
  } else {
    var arr = [1, 2];
    for (var i = 2; i < n; i++) {
      arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n - 1];
  }
}

15. 最长递增子序列

题目描述

求一个数组中最长递增子序列的长度。

代码解析

function longestIncreasingSubsequence(arr) {
  var dp = [];
  for (var i = 0; i < arr.length; i++) {
    dp[i] = 1;
    for (var j = 0; j < i; j++) {
      if (arr[j] < arr[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

16. 最长公共子序列

题目描述

求两个字符串的最长公共子序列。

代码解析

function longestCommonSubsequence(str1, str2) {
  var m = str1.length;
  var n = str2.length;
  var dp = [];
  for (var i = 0; i <= m; i++) {
    dp[i] = [];
    for (var j = 0; j <= n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 0;
      } else if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

17. 最长回文子串

题目描述

求一个字符串中最长的回文子串。

代码解析

function longestPalindrome(str) {
  var n = str.length;
  var dp = [];
  var start = 0;
  var maxLen = 1;
  for (var i = 0; i < n; i++) {
    dp[i] = [];
    dp[i][i] = true;
  }
  for (var j = 1; j < n; j++) {
    for (var i = 0; i < j; i++) {
      if (str[i] === str[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (j - i + 1 > maxLen) {
          maxLen = j - i + 1;
          start = i;
        }
      } else {
        dp[i][j] = false;
      }
    }
  }
  return str.substring(start, start + maxLen);
}

18. 最小路径和

题目描述

求一个二维数组中从左上角到右下角的最小路径和。

代码解析

function minPathSum(grid) {
  var m = grid.length;
  var n = grid[0].length;
  for (var i = 0; i < m; i++) {
    for (var j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        continue;
      } else if (i === 0) {
        grid[i][j] += grid[i][j - 1];
      } else if (j === 0) {
        grid[i][j] += grid[i - 1][j];
      } else {
        grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
      }
    }
  }
  return grid[m - 1][n - 1];
}

19. 最长无重复子串

题目描述

求一个字符串中最长的无重复子串。

代码解析

function longestSubstringWithoutRepeatingCharacters(str) {
  var n = str.length;
  var set = new Set();
  var maxLength = 0;
  var i = 0;
  var j = 0;
  while (i < n && j < n) {
    if (!set.has(str[j])) {
      set.add(str[j++]);
      maxLength = Math.max(maxLength, j - i);
    } else {
      set.delete(str[i++]);
    }
  }
  return maxLength;
}

20. 字符串转换整数

题目描述

将一个字符串转换成整数。

代码解析

function stringToInteger(str) {
  var sign = 1;
  var i = 0;
  var result = 0;
  while (str[i] === ' ') {
    i++;
  }
  if (str[i] === '-' || str[i] === '+') {
    sign = str[i] === '-' ? -1 : 1;
    i++;
  }
  while (i < str.length) {
    var digit = str.charCodeAt(i) - 48;
    if (digit < 0 || digit > 9) {
      break;
    }
    result = result * 10 + digit;
    i++;
  }
  result *= sign;
  if (result < -2147483648) {
    return -214748364