[Algorithm][综合训练][小葱的01串][小红的ABC][不相邻取数]详细讲解

---

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