admin管理员组文章数量:1794759
【算法/序列】等差数列&&子序列&&算术序列&&最长对称子串
概念：
等差数列：任意两项的差总等于同一个常数 子数组 ：是数组中的一个连续序列。 子序列：是通过从原序列删除零个或多个元素并在不改变顺序的情况下排列其余元素而获得的序列 算术序列：是一个数字列表，其中的连续项相差一个常数，即共同的差（也就是类似于等差数列）
一、是否能形成等差数列
简单模拟，利用等差的性质即可
代码语言：javascript代码运行次数：0运行复制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;
}
};四、计算算术子序列的数目
代码语言：javascript代码运行次数：0运行复制样例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;
}五、最长回文子串
思路： 我们用到的方法为中心扩展法 1、枚举会中心位置时，需要考虑回文串长度的奇偶性。
2、长度的计算： right - left - 1;
int getLongestPalindrome(string s) {
int n = s.size();
int ret = 0;
for (int i = 0; i < n; i++) {
// 以i为中心扩展为奇数的时候
int left = i - 1, right = i + 1;
while (left >= 0 && right < n && s[left] == s[right]) {
left--, right++;
}
ret = max(ret, right - left - 1);
// 以i为中心扩展为偶数的时候
left = i, right = i + 1;
while (left >= 0 && right < n && s[left] == s[right]) {
left--, right++;
}
ret = max(ret, right - left - 1);
}
return ret;
}六、最长对称子序列
思路：
- 求解最长回文子序列，有明显的子问题重叠，使用动态规划，考虑以下最优子结构： （1）dp[i][j]-----序列s[i]-->s[j]的最长回文子序列的长度。 （2）dp[i][i]=1 （3）dp[i][j]=0(j<i) （4）dp[i][j]=dp[i+1][j-1]+2 (if s[i]==s[j]) （5）dp[i][j]=max(dp[i+1,j],dp[i,j-1]) (if s[i]!=s[j])
- (2)显然，（3）是对（4）的边界条件的兼容，（4）易得，（5）由于s[i]!=s[j]，那么s[i]和s[j]最多只有一个能加入到最长回文子序列中，因此从两者中取最大值。
int longestPalindromeSubSeq(string s) {
// write code here
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
//i为起始索引，j为结束索引
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
//相同，则加2
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
//不同，则从dp[i+1][j] dp[i][j-1]中寻找最大值。
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}方法二： 解题思路：
- 方法一中的二维数组dp，我们通过图解和代码发现，每个 dp[ i ][ j ] 只依赖于 dp[ i + 1 ][ j -1 ]，dp[ i + 1][ j ]，dp[ i ][ j - 1 ]。因此，我们只需要一维数组即可。
- 同时由于dp[ i ][ j ] 依赖于dp[ i + 1][ j ]，因此i需要从大往小遍历。
int longestPalindromeSubSeq(string s) {
// write code here
int n = s.size();
vector<int> dp(n, 1);
//i为起始索引，j为结束索引
for (int i = n - 1; i >= 0; i--) {
int pre = 0;
for (int j = i + 1; j < n; j++) {
//临时变量存储dp[j]，需要更新为下一轮遍历的pre
int tmp = dp[j];
//相同，则加2
if (s[i] == s[j])
dp[j] = pre + 2;
//不同，则从dp[j] dp[j-1]中寻找最大值。更新到dp[j]
else
dp[j] = max(dp[j], dp[j - 1]);
pre = tmp;
}
}
return dp[n - 1];
}本文标签： 算法序列等差数列ampamp子序列ampamp算术序列ampamp最长对称子串
版权声明：本文标题：【算法序列】等差数列&&子序列&&算术序列&&最长对称子串 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754826418a1706959.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论