[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;
  }