Leetcode 413. Arithmetic Slice 算术序列切片(动态规划,暴力)

Leetcode 413. Arithmetic Slice 算术序列切片(动态规划,暴力)

题目描述

如果一个数组1.至少三个元素2.两两之间差值相同,那么这个数组就是算术序列

比如下面的数组都是算术序列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

但是这一个就不是:

1, 1, 2, 5, 7

求给定数组,能有多少个算术序列

测试样例

Input: [1, 2, 3, 4]
Output: 3
有三个算术序列切片:
[1,2,3], [2,3,4], [1,2,3,4]
注意,切片是不能跳着选的...

详细分析

  1. 暴力: 从长度3开始直到数组那么长,每次暴力求[k,k+len]是否是算术序列(是否两两差值相同)即可。
  2. 动态规划: 对于[1,2,3,4,3,5,6],我们从3开始:
  • [1,2,3]是一个算术序列,dp[2]=1
  • 然后继续[2,3,4],是算术序列则dp[3]=dp[2]+1;
  • 继续[3,4,3]不是算术序列,dp[4]=0
  • 继续[4,3,5] dp[5]=0
  • [3,5,6] dp[6]= 0

算法实现

  • 方法1:暴力
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.size()<3){
            return 0;
        }
        
        int totalSolution = 0;
        for(int dist=3;dist<=A.size();dist++){
            for(int k=0;k+dist<=A.size();k++){
                // Arithmetic sequence checking for current [k,k+distance] (sub)sequence
                bool isArithmeticSeq = true;
                int diff = A[k+1] - A[k]; 
                for(int p=k+2;p<k+dist;p++){
                    if((A[p]-A[p-1])!=diff){
                        isArithmeticSeq = false;
                        break;
                    }
                }
                if(isArithmeticSeq) totalSolution++;
            
            }
        }
        return totalSolution;
    }
};
  • 方法2:DP
class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int[] dp = new int[A.length];
        int sum = 0;
        for(int i=2;i<A.length;i++){
            if( (A[i]-A[i-1]) == (A[i-1]-A[i-2]) ){
                dp[i]=dp[i-1]+1;
                sum +=dp[i];
            }else{
                dp[i]=0;
            }
        }
        return sum; 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

类的传参以及super属性和super对象

在上述例子我们也看到了指定的子类特有的方法直接指定,那么我们如何指定子类特有的属性呢?我们这里用到了super方法;

1272
来自专栏Golang语言社区

Go队列和堆栈

golang,其实我的实现是利用container/list包实现的,其实container/list包很强大. package main import ...

3697
来自专栏Golang语言社区

go语言基本类型

这篇文章主要介绍了GO语言基本类型,较为详细的分析了整形、浮点型、字符串、指针等类型的具体用法,是深入学习GO语言所必须掌握的重要基础,需要的朋友可以参考下 ...

3246
来自专栏chenjx85的技术专栏

leetcode-438-Find All Anagrams in a String

26310
来自专栏Golang语言社区

【Go 语言社区】Golang 语言再谈接口

Go编程提供所谓的接口是另一种数据类型,代表了一组方法签名。结构数据类型实现这些接口对接口的方法签名,并其实现方法具体定义。 Syntax /* define ...

36115
来自专栏Golang语言社区

go语言json操作指南

1、Go语言的JSON 库   Go语言自带的JSON转换库为 encoding/json 1.1)其中把对象转换为JSON的方法(函数)为 json.Mar...

36612
来自专栏编程坑太多

数据结构之基于Java的顺序栈实现

1264
来自专栏Bingo的深度学习杂货店

Q503 Next Greater Element II

Given a circular array (the next element of the last element is the first elemen...

3336
来自专栏从流域到海域

《笨办法学Python》 第10课手记

《笨办法学Python》 第10课手记 本节课讲转义字符,并在代码中使用了\n(回车) 、\t (制表符,单个使用即输出八个空格)、\(打印一个\),也解释了前...

1958
来自专栏Golang语言社区

GO语言基本类型分析

一、整型 go语言有13种整形,其中有2种只是名字不同,实质是一样的,所以,实质上go语言有11种整形。如下: (1)int :依赖不同平台下的实现,可以是in...

3215

扫码关注云+社区

领取腾讯云代金券