服装购物网站排名,ppt制作神器,什么系统做网站好,推推蛙品牌策划如果数字序列由至少三个元素组成并且任何两个连续元素之间的差异相同#xff0c;则称为算术序列。
例如#xff0c;这些是算术序列#xff1a;
1#xff0c;3#xff0c;5#xff0c;7#xff0c;9 7#xff0c;7,7#xff0c;7 3#xff0c;-1#xff0c;-5则称为算术序列。
例如这些是算术序列
13579 77,77 3-1-5-9 以下序列是不算术。
1, 1, 2, 5, 7
给出了由N个数组成的零索引数组A. 该阵列的子序列切片是任何整数序列P0P1...Pk使得0≤P0P1 ... Pk N。
如果序列A [P0]A [P1]...A [Pk-1]A [Pk]是算术的则阵列A的子序列片P0P1...Pk被称为算术。特别是这意味着k≥2。
该函数应返回数组A中的算术子序列片数。
输入包含N个整数。每个整数的范围为-231和231-10≤N≤1000。输出保证小于231-1。
例
输入[2,4,6,8,10]
输出7
说明 所有算术子序列切片为 [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10] 简单的子序列这种题一般思路先想到的dp就是设置以第i个元素结尾的一种状态然后能推到最后吧
比如最长递增子序列这种的题。 那我们就试试dp[i]代表以第i个元素结尾的等差数列的个数。
然后我们想一下状态转移方程是什么
我们会发现挺难推出来的。。因为对于本个元素最容易想的思路就是把前面的结尾都遍历一遍然后能组成等差数列的都加起来吧
但是我们无法判断之前的结尾组成的等差数列中加上第i个元素还能不能是等差数列。。。
比如第5个数是5能和前面组成12345和2345和345和135这几个序列那dp[4]应该是4咯我们对于后面的结尾比如数字7算dp时遍历到dp[4]了我们无法判断dp[4]里这四个序列有几个公差为7-52也就是能组成。
我之前写过动态规划就是空间优化时间的算法。
我们推不出来因为信息不全。需要记录更多的信息。我们不止要知道dp[i]是多少还要知道每个公差的序列有多少才能推出来之后的dp序列。
我们可以二维dp[a][b]表示第a个元素结尾公差为b的序列个数但是由于数据较为稀疏浪费空间时间较大我们可以map走一波。
比如上面那个例子我们要记录dp[4],公差为1的序列有仨公差为2的有一个。
这样我们之后遇到了6那6-51dp[4]里有三个序列公差为1我们就能知道这三个序列加上6还是等差的。
遇到7也能7-52找dp[4]中公差为2的即可。 还有一个需要注意的点题目说长度最小为3才算。
过程叙述
计算两个数字之差diff如果越界了不做处理
如果没越界dp[i]中diff的映射增1然后看dp[j]中是否有diff的映射
如果有的话说明此时已经能构成等差数列了三个数将dp[j][d]加入结果res中然后再更新dp[i][d]
这样等遍历完数组res即为总数。
#include iostream
#include vector
#include map
#include set
#include queue
#include stack
#include string
#include climits
#include algorithm
#include sstream
#include functional
#include bitset
#include cmathusing namespace std;class Solution
{
public:int numberOfArithmeticSlices(vectorint A) {if (A.size() 2)return 0;int count 0;vectormapint, int dp(A.size());for (int i 0; i A.size(); i){for (int j 0; j i; j){if ((long)A[i] - (long)A[j] INT_MAX || (long)A[i] - (long)A[j] INT_MIN) continue;//节省时间int diff A[i] - A[j];//公差dp[i][diff] 1;if (dp[j].find(diff) ! dp[j].end()) //能构成至少三个数等差{dp[i][diff] dp[j][diff];count dp[j][diff];}}}return count;}
};
