[Algorithm][综合训练][求最小公倍数][跳台阶][最长回文子串]详细讲解

本文主要是介绍[Algorithm][综合训练][求最小公倍数][跳台阶][最长回文子串]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.求最小公倍数

1.题目链接

求最小公倍数

2.算法原理详解 && 代码实现

最小公倍数：两数乘积 / 最大公因数

最大公因数：辗转相除法

原理：GCD(a, b) == GCD(b, a % b)

// 非递归版本
int GCD(int a, int b)
{while(b != 0){int tmp = b;b = a % b;a = tmp;}return a;
}int GCD(int a, int b)
{int tmp = 0;while(a % b){tmp = a % b;a = b;b = tmp;}return b;
}// 递归版本
int GCD(int a, int b)
{if(b == 0){return a;}return GCD(b, a % b);
}

代码：

#include <iostream>
using namespace std;int GCD(int a, int b)
{if(b == 0){return a;}return GCD(b, a % b);
}int main()
{int a = 0, b = 0;cin >> a >> b;cout << (a * b / GCD(a, b)) << endl;return 0;
}

2.跳台阶

1.题目链接

跳台阶

2.算法原理详解 && 代码实现

自己的版本：

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> dp(n + 1, 0);dp[1] = 1, dp[2] = 2;for(int i = 3; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[n] << endl;return 0;
}

优化版本：相较于自己的版本，多了滚动数组进行空间优化

#include <iostream>
using namespace std;int main()
{int n = 0;cin >> n;int a = 1, b = 2, c = 2;for(int i = 3; i <= n; i++){c = a + b;a = b;b = c;}if(n == 0 || n == 1){cout << n << endl;}else{cout << c << endl;}return 0;
}

3.最长回文子串

1.题目链接

最长回文子串

2.算法原理详解 && 代码实现

自己的版本：动态规划 --> 时间/空间复杂度均为

O(N^2)

int getLongestPalindrome(string A) 
{int n = A.size();vector<vector<bool>> dp(n, vector<bool>(n, false));int len = 1;for(int i = n - 1; i >= 0; i--){for(int j = 0; j < n; j++){if(A[i] == A[j]){// i + 1 < j -> 表示至少有三个字符或以上dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;if(dp[i][j] && j - i + 1 > len){len = j - i + 1;}}}}return len;
}

优化版本：中心扩展算法 --> 时间复杂度

O(N^2)

，空间复杂度

O (1)

枚举中心位置的时候，要考虑回文串长度的奇偶性

int getLongestPalindrome(string A) 
{int n = A.size(), len = 1;for(int i = 1; i < n; i++) // 枚举每个中心点{// 当长度是奇数时int left = i - 1, right = i + 1;while(left >= 0 && right < n && A[left] == A[right]){left--;right++;}len = max(len, right - left - 1);// 当长度是偶数时left = i - 1, right = i;while(left >= 0 && right < n && A[left] == A[right]){left--;right++;}len = max(len, right - left - 1);}return len;
}