[Algorithm][综合训练][mari和shiny][重排字符串]详细讲解

本文主要是介绍[Algorithm][综合训练][mari和shiny][重排字符串]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.mari和shiny

1.题目链接

mari和shiny

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

自己的版本：三层循环暴力枚举 --> 超时 --> 40%

#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0, cnt = 0;cin >> n;string str;cin >> str;// 三层暴力枚举for(int i = 0; i < n - 2; i++){if(str[i] != 's'){continue;}for(int j = i + 1; j < n - 1; j++){if(str[j] != 'h'){continue;}for(int k = j + 1; k < n; k++){if(str[k] != 'y'){continue;}else{cnt++;}}}}cout << cnt << endl;return 0;
}

优化版本：动态规划 – 多状态的线性dp

状态表示：
- s[i]：[0, i]区间内，有多少个"s"
- h[i]：[0, i]区间内，有多少个"sh"
- y[i]：[0, i]区间内，有多少个"shy"
状态转移方程：
初始化：s[0] = str[0] == 's' ? 1 : 0, h[0] = y[0] = 0;
空间优化：

#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0;string str;cin >> n >> str;long long s = 0, h = 0, y = 0;for(int i = 0; i < n; i++){char ch = str[i];if(ch == 's'){s++;}else if(ch == 'h'){h += s;}else if(ch == 'y'){y += h;}}cout << y << endl;return 0;
}

2.重排字符串

1.题目链接

重排字符串

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

自己的版本：33.33%

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;int main()
{int n = 0;string str;cin >> n >> str;unordered_map<char, int> hash;unordered_set<char> deDup;int maxLen = 0;char maxCh = 'a';for(const auto& ch : str){deDup.insert(ch);hash[ch]++;int tmp = max(maxLen, hash[ch]);if(tmp > maxLen){maxLen = tmp;maxCh = ch;}}bool flag = true;if(maxLen > n / 2 + 1){flag = false;cout << "no" << endl; // 一个字符串的数量如果超过n / 2 + 1，则肯定不可以}// 到这里之后，肯定都是可以的// 这里的重组方法有失偏颇string ret;ret += maxCh, hash[maxCh]--;while(!hash.empty()){for(const auto& ch : deDup){if(hash.count(ch)){ret += ch;hash[ch]--;if(hash[ch] == 0){hash.erase(ch);}}}}if(flag){cout << "yes" << endl<< ret << endl;}return 0;
}

优化版本：贪心 + 构造

不能重排： $x > (n + 1) /2$
能重排：
- 每次去处理一批相同的字符 --> [自己的版本没意识到的思路]
- 优先处理出现次数最多的字符
- 每次摆放的时候，间隔一个格子
- 重点：手动控制间隔 --> [自己的版本没能实现的]

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;int main()
{int n = 0;string str;cin >> n >> str;unordered_map<char, int> hash;int maxLen = 0;char maxCh = 'a';for(const auto& ch : str){if(++hash[ch] > maxLen){maxLen = hash[ch];maxCh = ch;}}if(maxLen > (n + 1) / 2){cout << "no" << endl;}else{int index = 0;string ret;ret.resize(n);// 先去拜访出现次数最多的while(maxLen--){ret[index] = maxCh;index += 2;}hash.erase(maxCh);// 再摆放剩下的for(auto& it : hash){if(it.second){while(it.second--){if(index >= n){index = 1;}ret[index] = it.first;index += 2;}}}cout << "yes" << endl<< ret << endl;}return 0;
}