⭐️个人主页：摸鱼の文酱博客主页?‍♂️
?博客领域：java编程基础,mysql
?写作风格：干货,干货,还是tmd的干货
?精选专栏：【Java】【mysql】 【算法刷题笔记】
?博主的码云gitee，平常博主写的程序代码都在里面。
?支持博主：点赞?、收藏⭐、留言?
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

今日学习内容:第2讲 数列

由于这个系列的博客内容是参照博主英雄哪里出来的付费专栏《算法零基础100讲》
为避免侵犯博主权益 ,本章学习内容参考《算法零基础100讲》(第2讲) 数列

本节内容主要学习关于等差数列,等比数列以及斐波那契数列的相关问题解决方法

练习题目:

?509. 斐波那契数

问题描述:
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。给定 n ，请计算 F(n) 。

? 思路一:递归

int fib(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fib(n-1) + fib(n-2);
}

? 思路二:动态规划

int fib(int n) {
    if (n < 2) {
        return n;
    }
    int a = 0, b = 0, c = 1;
    for (int i = 2; i <= n; ++i) {
        a = b;
        b = c;
        c = a + b;
    }
    return c;
}

? 思路三:矩阵快速幂

之前经常看见过用矩阵快速幂来解题的,但是一直都没有好好学习这个思想,今天就趁这道题来学习一下,矩阵快速幂怎么用
这里先来解释一下矩阵乘法:

这里就是个矩阵乘法等式左边:1f(n-1)+1f(n-2)=f(n);1f(n-1)+0f(n-2)=f(n-1);

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n - 1);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

?1137. 第 N 个泰波那契数

问题描述:
泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

? 思路一:递归

class Solution {
    
      int[] cache = new int[40];
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (cache[n] != 0) return cache[n];
        cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
        return cache[n];
    }
}

? 思路二:动态规划

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int p = 0, q = 0, r = 1, s = 1;
        for (int i = 3; i <= n; ++i) {
            p = q;
            q = r;
            r = s;
            s = p + q + r;
        }
        return s;
    }
}

? 思路三:矩阵快速幂

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int[][] q = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
        int[][] res = pow(q, n);
        return res[0][2];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
            }
        }
        return c;
    }
}

?剑指 Offer 64. 求1+2+…+n

问题描述:
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

? 思路一:递归

嘶~,这限制这么多,我感觉我认识的全没了…

class Solution {
    public int sumNums(int n) {
       return n == 0 ? 0 : n + sumNums(n - 1);
    }
}

递归的关键是要有判断递归出口的条件,而上面规定不可以用$if$,那我们就要想别的办法来判定是否继续执行.
逻辑运算符的短路效应：

if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false
if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

class Solution {
    public int sumNums(int n) {
        boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

?896. 单调数列

问题描述:
如果数组是单调递增或单调递减的，那么它是 单调 的。

如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。 如果对于所有 i <= j，nums[i]> = nums[j]，那么数组 nums 是单调递减的。

当给定的数组 nums 是单调数组时返回 true，否则返回 false。

? 思路一:一次遍历

遍历数组 nums，若既遇到了nums[i]>nums[i+1] 又遇到了 nums[i ]<nums[i +1]，则说明 nums 既不是单调递增的，也不是单调递减的。

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean inc = true, dec = true;
        int n = nums.length;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                inc = false;
            }
            if (nums[i] < nums[i + 1]) {
                dec = false;
            }
        }
        return inc || dec;
    }
}

? 思路二:二次遍历

class Solution {
    public boolean isMonotonic(int[] nums) {
        return isSorted(nums, true) || isSorted(nums, false);
    }

    public boolean isSorted(int[] nums, boolean increasing) {
        int n = nums.length;
        if (increasing) {
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i] > nums[i + 1]) {
                    return false;
                }
            }
        } else {
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i] < nums[i + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

?1313. 解压缩编码列表

题目描述:
给你一个以行程长度编码压缩的整数列表 nums 。

考虑每对相邻的两个元素 [freq, val] = [nums[2i], nums[2i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。

请你返回解压后的列表。

? 思路一:模拟

首先统计数组中位于奇数位置的数值总和，定义一个同等长度的数组，在遍历一次数组，当为奇数时记录数值并循环这么多次，将此位置的后一个位置存入数组，直到数组结束。

class Solution {
    public int[] decompressRLElist(int[] nums) {
        int len = nums.length;
        int count =0;
        for(int i=0;i<len;i++){
            if(i%2==0){
                count += nums[i];
            }
        }
    int[] result = new int[count];
    int temp=0;
    int k=0;
    for(int i=0;i<len;i++){
        if(i%2==0){
            temp = nums[i];
            for(int j=0;j<temp;j++){
            result[k] = nums[i+1];
            k++;
        }
        }
    }
    return result;
    }
}