【算法/序列】等差数列&&子序列&&算术序列&&最长对称子串

概念：

等差数列：任意两项的差总等于同一个常数

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

子序列：是通过从原序列删除零个或多个元素并在不改变顺序的情况下排列其余元素而获得的序列

算术序列：是一个数字列表，其中的连续项相差一个常数，即共同的差（也就是类似于等差数列）

一、是否能形成等差数列

简单模拟，利用等差的性质即可

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        int d = arr[1] -arr[0];
        for(int i = 0; i < arr.size() - 1; i++)
        {
            if(arr[i + 1] - arr[i] != d) return false;
        }
        return true;
    }
};

二、等差数列划分 I - 子数组

思路：

该题主要是求其满足等差性质的子数组个数，并且子数组在原数组的相对顺序不能变，并且子数组 是数组中的一个连续序列。

注意：

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0;
        int d = nums[1] - nums[0], t = 0;
        int ans = 0;
        for(int i = 1; i < n - 1; i++)
        {
            if(nums[i + 1] - nums[i] == d) ++t;
            else{
                d  = nums[i + 1] - nums[i];
                t = 0;
            } 
            ans += t;
        }
        return ans;
    }
};

三、等差数列划分 II - 子序列

思路：

注意：

• 1  <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        vector<unordered_map<long long, int>> f(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long d = (long long) nums[i] - nums[j];
                int cnt = 0; //初始化为0
                if (f[j].find(d) != f[j].end()) { //如果能够找到差为d的则取出来
                    cnt = f[j].find(d)->second;
                }
                ans += cnt;
                //以当前i为尾项的数目：
            //cnt+1是由当前j位置确定的间隔为d的上一个尾项数目+1转移过来的
            //而再加上f[i][d]，是因为要加上其他任何与当前j不同位置，但产生公差依然为d的数目
                f[i][d] += cnt + 1;
            }
        }
      return ans;
    }
};

 四、计算算术子序列的数目

样例1输入：

5
1 2 3 2 3

输出：5 10 3 0 0
 

样例2输入：

4
1 2 3 4

输出：4 6 2 1
 

样例3输入：

1
100

输出：1

思路：

相当于对于n个数字，输出长度为i（1<=i<=n）的子序列个数，对于子序列要求其相应顺序不变，比如样例1中

长度为1的子序列：（1）、（2）、（3）、（4）、（5）

长度为2的子序列：长度为2的子序列都是算术子序列

长度为3的子序列：（1，2，3）、（1，2，5）、（1，4，5）

长度为4的子序列：0

长度为5的子序列：0

注意：

子序列：是通过从原序列删除零个或多个元素并在不改变顺序的情况下排列其余元素而获得的序列

算术序列：是一个数字列表，其中的连续项相差一个常数，即共同的差（也就是类似于等差数列）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 85, M = 998244353;
ll n, a[N], f[N][N][N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++) 
			f[i][j][2] = 1; //初始化
	}
	cout << n << ' ';
	ll ans = 0;
	for (int l = 2; l <= n; l++) {
		ll as = 0;
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				for (int k = 1; k < j; k++) {
					if (a[i] - a[j] == a[j] - a[k]) {
						f[i][j][l] += f[j][k][l - 1];
						f[i][j][l] %= M;
					}
				}
				as += f[i][j][l], as %= M;
			}
		}
		cout << as << ' ';
		//ans += as;
	}
	//cout << ans << "\n";
	return 0;
}

五、最长对称子串

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int i, j, t;
    string s;
    getline(cin, s);
    int n = s.size();
    int cnt, maxi = 1;
    for (t = 0; t < n; t++)
    {
        cnt = 0, i = t, j = n - 1;
        while (i < j)
        {
            if (s[i] == s[j])
            {
                if (j - i == 2)//奇数
                    cnt++;
                i++, j--;
                cnt += 2;//偶数
            }
            if (s[i] != s[j])
            {
                j--;
                i = t;
                cnt = 0;//清零
            }
        }
        maxi = max(maxi, cnt);
    }
    printf("%d\n", maxi);
    return 0;
}