本文主要是介绍[Algorithm][综合训练][小葱的01串][小红的ABC][不相邻取数]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 1.小葱的01串
- 1.题目链接
- 2.算法原理详解 && 代码实现
- 2.小红的ABC
- 1.题目链接
- 2.算法原理详解 && 代码实现
- 3.不相邻取数
- 1.题目链接
- 2.算法原理详解 && 代码实现
1.小葱的01串
1.题目链接
- 小葱的01串
2.算法原理详解 && 代码实现
- 解法:滑动窗口 --> ⻓度固定的滑动窗⼝,要想符合要求,必定是⼀半⼀半的
- 选择区域的时候,仅需选择长度为字符串长度一半即可
- 细节:没有必要考虑环的问题,因为实际上在一个循环内,如果该部分符合要求,那么剩下的部分也符合要求,所以不用考虑环
- 一个循环内找到一个符合要求的结果时,直接
ret += 2
即可
#include <iostream> #include <string> using namespace std; int main() {int n = 0;string str;cin >> n >> str;int sum[2] = { 0 }; // 统计字符串中所有0和1的个数for(auto& ch : str){sum[ch - '0']++;}int left = 0, right = 0, ret = 0, half = n / 2;int cnt[2] = { 0 }; // 统计窗口内0和1的个数while(right < n - 1) // 细节{cnt[str[right] - '0']++;while(right - left + 1 > half){cnt[str[left++] - '0']--;}if(right - left + 1 == half){if(cnt[0] * 2 == sum[0] && cnt[1] * 2 == sum[1]){ret += 2;}}right++;}cout << ret << endl;return 0; }
- 一个循环内找到一个符合要求的结果时,直接
2.小红的ABC
1.题目链接
- 小红的ABC
2.算法原理详解 && 代码实现
- 自己的版本:动态规划
#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 minLen = 101;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;int len = j - i + 1;if(dp[i][j] && len < minLen && len > 1){minLen = len;}}}}cout << (minLen == 101 ? -1 : minLen )<< endl;return 0; }
- 优化版本:找规律 --> 仅需判断长度为2以及长度为3的子串是否是回文串即可
#include <iostream> #include <string> using namespace std;int main() {string str;cin >> str;int n = str.size();int ret = -1;for(int i = 0; i < n; i++){if(i + 1 < n && str[i] == str[i + 1]) // 判断⻓度为2的⼦串{ret = 2;break;}if(i + 2 < n && str[i] == str[i + 2]) // 判断⻓度为 3 的⼦串{ret = 3;}}cout << ret << endl;return 0; }
3.不相邻取数
1.题目链接
- 不相邻取数
2.算法原理详解 && 代码实现
- 思路:[简单多状态]动态规划 -> 打家劫舍
- 状态表示:
f[i]
:从前i
个数挑选,最后一个位置必选,此时的最大和g[i]
:从前i
个数挑选,最后一个位置不选,此时的最大和
- 状态转移方程:
f[i] = g[i - 1] + nums[i]
g[i] = max(f[i - 1], g[i - 1])
#include <iostream> #include <vector> using namespace std;int main() {int n = 0;cin >> n;vector<int> nums(n + 1, 0);for(int i = 1; i <= n; i++){cin >> nums[i];}vector<int> f(n + 1, 0), g(n + 1, 0);for(int i = 1; i <= n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}cout << max(f[n], g[n]) << endl;return 0; }
- 状态表示:
这篇关于[Algorithm][综合训练][小葱的01串][小红的ABC][不相邻取数]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!