当前位置：首页 > article >正文

常见的面试算法题：阶乘、回文、斐波那契数列

article 2024/9/21 12:43:16

1.阶乘算法 Factorial

例如：给出数字5，对其以下的的每个数字相乘，结果等于120

解：递归 Recursive

function factorial(n) {
    // 如果n为0或1，阶乘是1
    if (n === 0 || n === 1) {
        return 1;
    }
    // 否则，返回n乘以n-1的阶乘
    return n * factorial(n - 1);
}
console.log(factorial(5)); // 输出 120

虽然递归是一个直观的解决方案，但对于非常大的数字，递归可能导致栈溢出错误。对于更大的数字，你可以使用迭代方法来避免栈溢出：

解：迭代 Iterative

function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
console.log(factorialIterative(5)); // 输出 120

2.回文算法 Palindrome

实现一个检查回文的算法相对简单。回文是一个字符串，它从前往后读和从后往前读是一样的。下面是一个简单的实现：

解：使用系统自带的reverse函数

function isPalindrome(str) {
    // 移除非字母数字字符并转换为小写
    const cleanedStr = str.replace(/[\W_]/g, '').toLowerCase();
    // 检查清理后的字符串是否是回文
    return cleanedStr === cleanedStr.split('').reverse().join('');
}
// 使用示例
console.log(isPalindrome("A man, a plan, a canal, Panama")); // 应该输出 true
console.log(isPalindrome("racecar")); // 应该输出 true
console.log(isPalindrome("hello")); // 应该输出 false

解：不使用系统自带的reverse函数

这种方法不需要改变字符串本身，只需遍历到字符串的一半即可。

a.清理字符串：和之前一样，首先移除所有非字母数字的字符，并将所有字符转换为同一大小写。
b.手动比较字符：遍历清理后的字符串，直到中间位置。在每一步中，比较第 i 个字符和倒数第 i 个字符。如果这些字符在任何时候不匹配，函数应该返回 false。如果所有对应的字符都匹配，则字符串是回文。

function isPalindrome(str) {
    const cleanedStr = str.replace(/[\W_]/g, '').toLowerCase();
    const len = cleanedStr.length;
    for (let i = 0; i < len / 2; i++) {
        if (cleanedStr[i] !== cleanedStr[len - 1 - i]) {
            return false;
        }
    }
    return true;
}
// 使用示例
console.log(isPalindrome("A man, a plan, a canal, Panama")); // 应该输出 true
console.log(isPalindrome("racecar")); // 应该输出 true
console.log(isPalindrome("hello")); // 应该输出 false

3.斐波那契数列算法 Fibonacci

斐波那契数列是一个著名的数列，其中每个数字是前两个数字之和。数列以0和1开始，后续的数是通过加前两个数来得到的。在JavaScript中实现斐波那契数列有几种方法，包括递归、动态规划和闭包。

1.递归

递归是最直观的实现方式，但对于较大的数字效率较低，因为它包含了大量的重复计算。

function fibonacciRecursion(n) {
    if (n < 2) {
        return n;
    }
    return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
}

2.动态规划

动态规划方法存储了中间结果，避免了重复计算，因此效率更高。

function fibonacciDynamic(n) {
    let fib = [0, 1];
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

3.闭包

使用闭包可以创建一个函数，记住之前计算的值，从而避免重复计算。

function fibonacciClosure() {
    let cache = [0, 1];
    return function fib(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }
}
const fib = fibonacciClosure();