原文: https://zsqk.github.io/news/2020-04-22-leetcode-minimum-number-of-frogs-croaking.html
最近的一道中等难度的题是: Minimum Number of Frogs Croaking
根据 Hints, 用 JavaScript 写了答案, 思路应该是清晰的, 效率也可以接受. 参考 Hints 写的答案都是基础方法, 但软件工程应该就是使用最简单的思路去解决问题.
以下是具体答案:
Runtime: 76 ms, faster than 85.98% of JavaScript online submissions. Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions. (2020-04-22 17:22:18 +8)
/**
* @param {string} croakOfFrogs
* @return {number}
*/
var minNumberOfFrogs = function (croakOfFrogs) {
let max = 0;
const m = { c: 0, r: 0, o: 0, a: 0, k: 0 };
for (const v of croakOfFrogs) {
if (!"croak".includes(v)) {
return -1;
}
if (v === "k") {
m.c -= 1;
m.r -= 1;
m.o -= 1;
m.a -= 1;
if (m.c >= max) {
max = m.c + 1;
}
} else {
m[v] += 1;
if (m.c < m.r || m.r < m.o || m.o < m.a || m.a < m.k) {
return -1;
}
}
}
if (m.c !== 0) {
return -1;
}
return max;
};
附: 如果想回 晋城 了, 咱们联系呀.
1
cxe2v 2020-04-22 20:42:36 +08:00
执行用时 :
96 ms , 在所有 JavaScript 提交中击败了 58.57% 的用户 内存消耗 : 36.7 MB , 在所有 JavaScript 提交中击败了 100.00% 的用户 |
2
cxe2v 2020-04-22 20:43:11 +08:00
你的要快百分之 20
|
3
momocraft 2020-04-22 21:27:51 +08:00 1
https://gist.github.com/jokester/1bfe4f408bf838ae4d3fd52f7d6db8d9
好像思路比楼主的更粗暴... 速度也还行 |
4
also24 2020-04-22 21:56:36 +08:00 1
这题优化时间的方法居然是直接声明 5 个常量来存中间值……
另:楼主没必要每次数到 'k' 就全部减一遍,你需要的只是 m.c - m.k 这个值 |
5
ConradG 2020-04-22 22:12:29 +08:00 1
```ruby
def min_number_of_frogs(croak_of_frogs) s = 'croak' level = s.each_char.each_with_index.inject(Hash.new) {|map, (c, i)| map[c] = i; map} max_level = s.size - 1 process = Hash.new {|map, key| map[key] = 0} total, relax = 0, 0 croak_of_frogs.each_char do |ch| a = level[ch] if a == 0 relax == 0 ? total += 1 : relax -= 1 process[0] += 1 else break if (process[a - 1] -= 1) < 0 a == max_level ? relax += 1 : process[a] += 1 end end return -1 if relax != total return -1 if process.values.find {|x| x != 0} total end ``` 用 Ruby 的好处就是,基本上都是 faster than 100% |
7
willhunger 2020-04-22 22:44:41 +08:00 1
贴一个丑陋的解法,上周周赛现场解法,一直没 review
https://paste.ubuntu.com/p/x6kZ7nvfkT/ |
8
sherlockmao 2020-04-22 23:05:15 +08:00 1
Runtime: 4 ms, faster than 100.00% of Go online submissions for Minimum Number of Frogs Croaking.
Memory Usage: 4.8 MB, less than 100.00% of Go online submissions for Minimum Number of Frogs Croaking. func ord(c byte) int { switch c { case byte('c'): return 0 case byte('r'): return 1 case byte('o'): return 2 case byte('a'): return 3 case byte('k'): return 4 } return -1 } func minNumberOfFrogs(croakOfFrogs string) int { ans := 0 dp := make([]int, 6) for i := 0; i < len(croakOfFrogs); i++ { b := ord(croakOfFrogs[i]) if b < 0 { return -1 } if b == 0 { dp[0]++ if dp[0] > ans { ans = dp[0] } continue } if dp[b-1] == 0 { return -1 } if b != 1 { dp[b-1]-- } if b != 4 { dp[b]++ } else { dp[0]-- } } for i := 0; i < len(dp); i++ { if dp[i] != 0 { return -1 } } return ans } |
9
iugo OP 今天再看, 的确还有值得优化的地方. 比如 m.k 没有意义, 永远是 0.
|
10
iugo OP 写了一个人类优化版和一个机器优化版.
人类优化版性能下降到 88 ms, 但可以支持任意不重复的字符串. 机器优化版 `Runtime: 60 ms, faster than 99.39% of JavaScript online submissions Memory Usage: 36.7 MB, less than 100.00%` |
11
pwrliang 2020-04-23 12:14:06 +08:00
这不是上周周赛题目吗,计数就行了,难在如何判断序列是否合法。我当时的解法是两边扫描,第一次计数,第二次判断序列合法性。
```java class Solution { public int minNumberOfFrogs(String croakOfFrogs) { if (croakOfFrogs.length() == 0) return -1; int count = 0, max = 0; for (int i = 0; i < croakOfFrogs.length(); i++) { if (croakOfFrogs.charAt(i) == 'c') count++; else if (croakOfFrogs.charAt(i) == 'k') count--; max = Math.max(max, count); } int lastC = 0, lastR = 0, lastO = 0, lastA = 0, lastK = 0; while (lastK < croakOfFrogs.length() - 1) { int idxC = croakOfFrogs.indexOf("c", lastC), idxR = croakOfFrogs.indexOf("r", lastR), idxO = croakOfFrogs.indexOf("o", lastO), idxA = croakOfFrogs.indexOf("a", lastA), idxK = croakOfFrogs.indexOf("k", lastK); if (idxC == -1 | idxR == -1 || idxO == -1 || idxA == -1 || idxK == -1) return -1; if (idxC < idxR && idxR < idxO && idxO < idxA && idxA < idxK) { } else return -1; lastC = idxC + 1; lastR = idxR + 1; lastO = idxO + 1; lastA = idxA + 1; lastK = idxK + 1; } return max; } } ``` |