HackerRank - string-reduction【反推】
题意 给出一串 只有 字母 a, b, c 组成的字符串，然后没两个不同的字符碰到一起都可以变成另外一个字符，然后变到最后，求最短的字符串长度。
思路
①如果给出的字符串都是相同的字符，那么显然，答案就是这个字符串的长度
②如果不是 那么答案 可能是1 或者是 2
③我们可以反着推回去。就是假如 刚开始的状态的1 我们可以先假定 x = 字符a的数量 y = 字符b的数量 z = 字符c的数量
如果某个字符串 是由 1 推过去的 那么刚开始 x, y, z的数量就是 (1, 0, 0) || (0, 1, 0) || (0, 0, 1) 其奇偶状态就是 奇，偶，偶， 如果一个字符变成连个字符 其奇偶状态就变为 偶，奇，奇 如果继续变 其奇偶状态就变为 奇，偶，偶 所以 如果答案是1 那么 奇偶状态就是 两奇一偶 或者 一奇两偶 如果某个字符串是由 2 推过去的 刚开始的奇偶状态是 偶，偶，偶 如果减少一个字符，加另外两个字符 其奇偶状态就变成 奇，奇，奇
所以 我们可以得出，如果 一个字符串的奇偶状态是 全奇 或者 全偶 那么最后的答案 就是2 如果是其他情况 最后的答案 就是1
AC代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; int main() { int t; cin >> t; while (t--) { string s; cin >> s; int n[3] = {0}; int len = s.size(); for (int i = 0; i < len; i++) { n[s[i] - 'a'] ++; } if (n[0] == len || n[1] == len || n[2] == len) { cout << len << endl; } else if((n[0] % 2 == 1 && n[1] % 2 == 1 && n[2] % 2 == 1) || (n[0] % 2 == 0 && n[1] % 2 == 0 && n[2] % 2 == 0)) cout << 2 << endl; else cout << 1 << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433367.html
