2022-09-18笔试题00
请注意,本文编写于 673 天前,最后修改于 673 天前,其中某些信息可能已经过时。

面试高频手撕代码题

斐波那契数列(递归,DP,循环)

  • 递归

时间复杂度 O(2^N) 空间复杂度 O(1)

function fiber(n) {
  if (n == 0 || n == 1) {
    return n;
  } else {
    return fiber(n - 1) + fiber(n - 2);
  }
}

console.log(fiber(5));
  • DP 动态规划

时间复杂度 O(N) 空间复杂度 O(N)

function fiber(n) {
  if (n === 0 || n === 1) return n;
  var dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
  • 循环

时间复杂夫 O(N) 空间复杂度 O(1)

function fiber(n) {
  if (n === 0 || n === 1) return n;
  var ret = 1;
  var a = 0;
  var b = 1;
  for (let i = 2; i < n; i++) {
    a = b;
    b = ret;
    ret = a + b;
  }
  return ret;
}

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!