• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

413.等差数列划分

admin

11月 28, 2021

413.等差数列划分

题目:

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

例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。

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

示例 1:

输入:nums = [1,2,3,4]
输出:3
解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2:

输入:nums = [1]
输出:0

解法一 动态规划

动态规划重要几点:(1) dp[i]的定义;(2)状态;(3)选择;

dp[i]的定义:表示第i个元素包括第i个元素之前的所有等差数列。

状态:选择了这个元素,可以组成更长的等差数组。或者选择了这个元素,不能组成更长的等差数组。

选择:只能选择下一个。

所以动态规划的方程为:

dp[i] = dp[i-1]+1 //如果能组成更长的等差数组
dp[i] = 0 //如果组不成更长的等差数组

如果能组成更长的等差数组:那么num[i]-num[i-1] == num[i-1]-num[i-2]

否则的话不能组成。所以动态规划方程就出来了。

需要注意的是,一般情况下,在开始动态规划的时候,需要定义初始状态,这道题中初始状态都是0,所以可以直接去掉。具体看代码提示。

image-20210810154932459

代码

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        //这里应该有初始状态.即dp[0]=dp[1]=dp[2] = 0,可以不用罗列,具体原因:
        //在定义数组的时候,基本类型的数组初始化为零值.int的话为0,boolean的话是false。
        for (int i = 2; i < n; i++) {
            if (nums[i]-nums[i-1] == nums[i-1]-nums[i-2]){
                dp[i] = dp[i-1]+1;
            }else {
                dp[i] = 0;
            }
        }
        return Arrays.stream(dp).sum();
    }
}

解法二:查分+计数

leetcode的官方题解。

感觉讲的太复杂了,代码其实挺简单的。

image-20210810161211163

public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int d = nums[0] - nums[1], t = 0;
        int ans = 0;
        //因为等差数列的长度至少为3,所以可以从i=2开始枚举
        for (int i = 2; i < n; i++) {
            if (nums[i-1] - nums[i] == d){
                ++t;
            }else{
                d = nums[i-1] - nums[i];
                t= 0;
            }
            ans+=t;
        }
        return ans;
    }

就是在循环数组中的每个数,多设置一个重置位,当不满足等差定义的时候,将重置位置为0,否则的话重置位++,每次循环把重置位和ans相加即可。

博客网站 https://yamon.top
个人网站 https://yamon.top/resume
GitHub网站 https://github.com/yamonc
欢迎前来访问

发表回复

您的电子邮箱地址不会被公开。