算法练习

斐波那契数列(leetcode 2360)

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2 输出:1 示例 2:

输入:n = 5 输出:5

var fib = function(n) {
    if(n===0 || n===1){
        return n
    }
    let res;
    let last=1;
    let second_last=0;
    let i = 1;
    while(i<n){
        res = last + second_last;
        if(res>1000000007){
            res-=1000000007
        }
        second_last = last;
        last = res;
        i++
    }
    return res
};

强行写斐波那契会出现栈溢出的问题,实际只需要两个变量不停累计即可,累计过程中,面向题目,可以在大于1000000007直接减去,避免出现大数据的计算造成数据失真

青蛙跳台阶问题 (leetcode 2361)

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2 输出:2 示例 2:

输入:n = 7 输出:21 示例 3:

输入:n = 0 输出:1

// 递归计算跳法 爆栈  
var numWays = function(n) {
    let count = 0;
    function add(total){
        if(total===n){
            count++
        }
        if(total>n){
            return
        }
        if(total<n){
            add(total+1)
            add(total+2)
        }
    }
    add(0)
    return count
};
// 复杂度太高再次超时  
var numWays = function(n) {
    if(n===0)return 1
    let count = 0;
    let processing = [0];
    do{
      let newP = []
      for(let i=0;i<processing.length;i++){
          let temp = processing[i]+1
          let temp2 = processing[i]+2
          if(temp===n){
              count++
          }
          if(temp<n){
              newP.push(temp)
          }
          if(temp2===n){
              count++
          }
          if(temp2<n){
              newP.push(temp2)
          }
      }
      processing = newP
    }while(processing.length!=0)
    return count
};
// 好吧好吧 原来又是一个斐波那契数列  f(n)=f(n-1)+f(n-2)
var numWays = function(n) {
    if(n===0 || n===1)return 1
    let i=2;
    let last = 1;
    let second_last = 1;
    let now;
    while(i<=n){
        now = last + second_last
        if(now>1000000007){
            now-=1000000007
        }
        second_last = last
        last = now
        i++
    }
    return now
};

矩阵中的路径

var exist = function (board, word) {
    let len1 = board.length; //行
    let len2 = board[0].length; //列
    for (let x = 0; x < len1; x++) {
         for (let y = 0; y < len2; y++){
            if (dfs(x, y, 0)) return true;//dfs每个元素
        }
    }
    return false;

    function dfs(x, y, k) {
        //越界或者不想等的情况,返回false
        if (x < 0 || y < 0 || y > len2 - 1 || x > len1 - 1 || board[x][y] !== word[k]) {
            return false;
        }
        //判断到最后一个位置都相等
        if (k === word.length - 1) return true;
        //提前记录当前节点元素值
        let temp = board[x][y];
        //设置为0防止下次访问,实现深度优先
        board[x][y] = 0;
        //偏移量数组,方便实现上下左右偏移
        var dx = [1,-1,0,0],dy = [0,0,1,-1]
        for(var i = 0 ; i < 4 ; i++){
           if(dfs(x+dx[i],y+dy[i],k+1)) return true
        }
        //回溯不要忘记把已经访问过的值设置为之前记录过的temp
        board[x][y] = temp;
        return false
    }
};

来源:力扣(LeetCode)