258 各位相加

[neptoo]

各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

let addMore = (num) => {
  // 递归的边界条件||递归的出口
  if (num < 10) {
    return num;
  }
  let res = num.toString().split('').reduce((pre, cur) => {
    // parseInt() !!!!
    return pre + parseInt(cur);
  }, 0);
  return addMore(res);
};
// console.log(addMore(38));

tip1: 直到 --> 递归

递归：函数在调用过程中调用自己

fibonacci 数列：该数列从第三项开始，后面的每一项数字都是前面两项数字的和。

F(0)=1, F(1)=1,F(n)=F(n-1)+F(n-2) (n>1) 1,1,2,3,5,8,...

// 最基础的解法
// function fib(n) {
//   if (n == 1 || n == 2) {
//     return 1;
//   } else {
//     return fib(n - 1) + fib(n - 2);
//   }
// }
// 缓存解法 arr=[1,2,3,5]
// 数组方法
// let fibo = (function(){
//   let cache = [];
//   return function(n){
//       if (cache[n] !== undefined){
//           return cache[n];
//       }else{
//           return cache[n] = (n <= 2) ? 1 : fibo(n - 1) + fibo(n - 2);
//       }
//   }
// })();
// let fib = (function () {
//   let memo = new Map();
//   return function (n) {
//     let memorized = memo.get(n);
//     if (memorized) {
//       return memorized;
//     }
//     if (n == 1 || n == 2) {
//       return 1;
//     }
//     let f1 = fib(n - 1);
//     let f2 = fib(n - 2);
//     memo.set(n-1, f1);
//     memo.set(n-2, f2);
//     return f1 + f2;
//   };
// })();
// 动态规划的解法
// let fib = function (n) {
//   let dp = [];
//   dp[0] = 0;
//   dp[1] = 1;
//   // 从2开始 不断用之前的值 填充数组
//   for (let i = 2; i <= n; i++) {
//     dp[i] = dp[i - 1] + dp[i - 2];
//   }
//   return dp[n];
// };