笔试题9. LeetCode OJ (9) Arithmetic Slices

2017-01-14 19:44:06来源:CSDN作者:shenhuan1104人点击

第七城市

这里写图片描述
题目的意思是:给你一串数字(至少3个),其中的一串数字(子串——3个或者3个以上数字组成)相邻两个数字之间的差两两相等,那么这串数字就是“Arithmetic Slices”——“算数片”,请计算一串数字中的“算数片”。

class Solution {public:    int numberOfArithmeticSlices(vector<int>& A) {        int len=A.size();        if(len<3){            return 0;        }        int cnt=0;        vector<int> dp(len,0);        for(int i=1;i<len-1;i++){            if(A[i+1]-A[i]==A[i]-A[i-1])                dp[i]=dp[i-1]+1;            cnt+=dp[i];        }        return cnt;    }};

最为关键的就是“ dp[i]=dp[i-1]+1;”这个语句,就是每当串长度加1的时候,整个“算数片”数量会加dp[i-1]+1个,这是整道题目的关键。

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台