[Algorithm][综合训练][非对称之美][添加字符][数组变换]详细讲解

本文主要是介绍[Algorithm][综合训练][非对称之美][添加字符][数组变换]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.非对称之美

1.题目链接

非对称之美

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

自己的版本：动态规划 --> 内存超限 --> 23.44%

#include <iostream>
#include <string>
#include <vector>
using namespace std;int main()
{string str;cin >> str;int n = str.size();vector<vector<bool>> dp(n, vector<bool>(n, false));int maxLen = 0;for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(str[i] == str[j]){dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}if(!dp[i][j]){maxLen = max(maxLen, j - i + 1);}}}cout << maxLen << endl;return 0;
}

优化版本：规律 + 贪心

#include <iostream>
#include <string>
using namespace std;int n;
string str;int Adjust()
{// 1.判断是否全都是相同字符bool flag = true;for(int i = 1; i < n; i++){if(str[i] != str[0]){flag = false;break;}}if(flag){return 0;}// 2.判断本身是否是回文flag = true;int left = 0, right = n - 1;while(left < right){if(str[left] == str[right]){left++;right--;}else{flag = false;break;}}if(flag){return n - 1;}else{return n;}
}int main()
{cin >> str;n = str.size();cout << Adjust() << endl;return 0;
}

2.添加字符

1.题目链接

添加字符

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

解法：暴力枚举

#include <iostream>
#include <string>
using namespace std;int main()
{string a, b;cin >> a >> b;int m = a.size(), n = b.size();int ret = m;for(int i = 0; i <= n - m; i++) // 枚举b的起始位置{int tmp = 0;for(int j = 0; j < m; j++){if(a[j] != b[i + j]){tmp++;}}ret = min(tmp, ret);}cout << ret << endl;return 0;
}

3.数组变换

1.题目链接

数组变换

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

自己的版本：排序 + 模拟 --> 100%

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;bool Check(int small, int large)
{while(small < large){if((small *= 2) == large){return true;}}return false;
}int main()
{int n = 0;cin >> n;vector<int> nums(n, 0);for(int i = 0; i < n; i++){cin >> nums[i];}sort(nums.begin(), nums.end());int r = n - 1;while(r > 0){if(Check(nums[r - 1], nums[r]) || nums[r] == nums[r - 1]){r--;}else{break;}}cout << (r == 0 ? "YES" : "NO") << endl;return 0;
}

优化版本：贪心 + 位运算

贪心：以最大值为基准，判断较小的数都否变成最大值
位运算：判断一个数是否是x是 $2^n$
- 方法一：x - (x & -x) == 0 ? true : false
  - x & -x提取出最后一个二进制为1的位
  - 如果该位为仅有的二进制位为1的位，则是
- 方法二：x & (x - 1) == 0 ? true : false

#include <iostream>
#include <vector>
using namespace std;int n = 0, maxValue = 0;
vector<int> nums;bool Check()
{for(int i = 0; i < n; i++){if(maxValue % nums[i]){return false;}int x = maxValue / nums[i];if(x - (x & -x)){return false;}}return true;
}int main()
{cin >> n;nums.resize(n, 0);for(auto& x : nums){cin >> x;maxValue = max(x, maxValue);}if(Check()){cout << "YES" << endl;}else{cout << "NO" << endl;}return 0;
}