题外话

想知道大家都喜欢博客写什么内容,大家可以在评论区留言!!

正题

 第一题

Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

输入一个数我们可以给这个数+1或者-1,让这个数变成斐波那契数中的一个,输出步数最少的变成斐波那契数

当我们输入15的时候,离15最近的斐波那契数为13和21,

15减去2等于13

15加上6等于21

所以最小步数为2

第一题思路

我们只需要找到比输入的数大一点的斐波那契数和小一点的斐波那契数

然后用这两个数和输入的数进行比较差值大小即可

第一题代码详解

public int test11()
{
    Scanner scanner=new Scanner(System.in);
    //输入fib
    int fib= scanner.nextInt();

    //创建a,b,c
    int a=0;
    int b=1;
    int c=0;

    //创建min和max用来记录最近的大于和小于fib
    int min=0;
    int max=0;

    //如果fib=0或者1直接返回0即可
    if (fib==0||fib==1)
    {
        return 0;
    }
    //当a+b小于fib时
    while (a+b<fib)
    {
        //进行斐波那契循环
        c=a+b;
        a=b;
        b=c;
        //如果a+b大于fib的时候
        if (a+b>fib)
        {
            //此时的c就是最近的小于fib的数
            min=c;
            //此时的a+b就是最近的大于fib的数
            max=a+b;
        }
    }
    //最后只需要返回fib-min和max-fib中的最小值即可
    return Math.min((fib - min), (max - fib));
}

第二题

等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

第二题思路

我们要先确立dp状态表示,根据题目,我们可以设置dp[i]是以i位置为结尾的,等差数列的个数

dp[i]的动态转移方程

由上图我们找到了动态转移方程

由示例可知,nums数组长度至少大于等于3

所以当nums数组小于3时,直接返回0

第二题代码详解

 public int numberOfArithmeticSlices(int[] nums) {

        int n=nums.length;

//当数组长度小于3,直接返回0

        if(n<3)

        {

            return 0;

        }

//创建dp数组

        int[] dp=new int[n];

//初始化dp[0],dp[1]为0

        dp[0]=dp[1]=0;

//数组中至少有3个元素才有可能存在等差数列,所以下标从2开始

        for(int i=2;i<n;i++)

        {

            dp[i]=nums[i-1]-nums[i-2]==nums[i]-nums[i-1]?dp[i-1]+1:0;

                    }

//创建count负责计等差数列个数

        int count=0;

//将所有的等差数列个数加在一起,最后返回count即可

        for(int i=0;i<n;i++)

        {

            count+=dp[i];

        }

        return count;

    }

第三题

最长湍流子数组

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组

实例 4:

输入 :arr=[9,9]

输出: 1

第三题思路

我们先讨论一下有什么情况

1.以第i个元素结尾时最后一个符号是">"

2.以第i个元素结尾时最后一个符号是"<"

3.如果以第i个元素为结尾时,第i-1元素和第i个元素,两个数相等的话,湍流子数列长度为1

我们根据这三种情况,分别用g[i]表示以第i个元素结尾时最后一个符号是">"湍流子数组长度

f[i]表示以第i个元素结尾时最后一个符号是"<"

同时我们需要将f[i]和g[i]初始化为1,情况如下图

第三题代码

 public int maxTurbulenceSize(int[] arr) {

//设置数组f[]和数组g[],长度为n

    int n=arr.length;

    int[] f=new int[n];

    int[] g=new int[n];

   //设置count负责记录最大湍流数组长度,初始值为1

      int count=1;

//将两个数组初始值都设为1

   for(int i=0;i<n;i++)

   {

    f[i]=g[i]=1;

   }

//从i=1开始

    for(int i=1;i<n;i++)

    {

//判断以i元素结尾是的符号

        if(arr[i-1]<arr[i])

        {

//小于号,则让f[i]=g[i-1]+1

            f[i]=g[i-1]+1;

        }

        if(arr[i-1]>arr[i])

        {

//大于号,则让g[i]=f[i-1]+1

            g[i]=f[i-1]+1;

        }

最后记录下最长湍流子数组长度即可

        count=Math.max(count,Math.max(f[i],g[i]));

    }

    return count;

    }

小结

好长一段时间没写过博客了,最近很迷茫,快到秋招了,一起努力吧

喜欢的家人们记得给个三连(点赞关注收藏!!!)