本文共 1764 字,大约阅读时间需要 5 分钟。
链接:
有一说一确实是一道好题。在此理解这个青蛙数刚好能和最近看的操作系统多线程扯上关系,来自大佬的思想,想想确实很形象。一个线程就输出一个 "croak"
,可以连续输出,但是只能算作一个线程。思路如下:
dp[MAXN][5]
数组,即处于字符串 i
位置,处于状态 c r o a k
的线程有多少个'c'
,也就意味着有一个新的线程启动了,也就是有一个青蛙要开始准备叫了,就需要在该位置进行自增加一'o'
,那么它肯定就是从 'r'
转移过来的,并不需要关心是哪个线程,只需要关心它进行了状态转移即可dp
值是一个增量,再加上上一个 dp
状态的值就完成了状态更新。在此不需要管上阶段已经蛙叫完毕的,即仅考虑前四个状态就行了dp
求和 sum
,并取 max
,得到最大的线程数就能解决问题了,这个完全可以参考线程池,即线程池大小仅需要与某时刻最大的线程数相当即可上述这个解法建议本地单步调试,就能豁然开朗,写的确实很冗余,这个二维的方法可以通过压缩实现一维的形式。在题解区大多数都是 1 维的直接遍历解法,思想大同小异,就不多赘述了。
参见代码如下:
// 执行用时 :76 ms, 在所有 C++ 提交中击败了100.00%的用户// 内存消耗 :11.3 MB, 在所有 C++ 提交中击败了100.00%的用户const int MAXN = 1e5 + 50;int dp[MAXN][5];int c2i(char x) { if (x == 'c') return 0; if (x == 'r') return 1; if (x == 'o') return 2; if (x == 'a') return 3; if (x == 'k') return 4; return -1;}class Solution { public: int minNumberOfFrogs(string str) { memset(dp[0], 0, sizeof(dp[0])); int n = str.size(), ans = 0; for (int i = 1; i <= n; ++i) { char c = str[i - 1]; int cur = c2i(c); if (cur == -1) return -1; memset(dp[i], 0, sizeof(dp[i])); if (cur == 0) dp[i][0]++; else dp[i][cur]++, dp[i][cur - 1]--; for (int k = 0; k < 4; ++k) dp[i][k] += dp[i - 1][k]; for (int k = 0; k < 5; ++k) if (dp[i][k] < 0) return -1; int sum = 0; for (int k = 0; k < 5; ++k) sum += dp[i][k]; ans = max(ans, sum); } for (int k = 0; k < 4; ++k) if (dp[n][k] != 0) return -1; return ans; }};
转载地址:http://lghpz.baihongyu.com/