LeetCode 新题, 聒噪的青蛙, 参考

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1665 天前的主题，其中的信息可能已经有所发展或是发生改变。

原文: 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;
};

附: 如果想回晋城了, 咱们联系呀.

return

Max

JavaScript

11 条回复 • 2020-04-23 12:14:06 +08:00

cxe2v

2020-04-22 20:42:36 +08:00

执行用时 :
96 ms
, 在所有 JavaScript 提交中击败了
58.57%
的用户
内存消耗 :
36.7 MB
, 在所有 JavaScript 提交中击败了
100.00%
的用户

cxe2v

2020-04-22 20:43:11 +08:00

你的要快百分之 20

momocraft

2020-04-22 21:27:51 +08:00

https://gist.github.com/jokester/1bfe4f408bf838ae4d3fd52f7d6db8d9
好像思路比楼主的更粗暴... 速度也还行

also24

2020-04-22 21:56:36 +08:00

这题优化时间的方法居然是直接声明 5 个常量来存中间值……

另：楼主没必要每次数到 'k' 就全部减一遍，你需要的只是 m.c - m.k 这个值

ConradG

2020-04-22 22:12:29 +08:00

```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%

ConradG

2020-04-22 22:13:10 +08:00

@ConradG 咦，回复不支持 MD 的？ orz

willhunger

2020-04-22 22:44:41 +08:00

贴一个丑陋的解法，上周周赛现场解法，一直没 review
https://paste.ubuntu.com/p/x6kZ7nvfkT/

sherlockmao

2020-04-22 23:05:15 +08:00

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
}

iugo

2020-04-23 10:08:29 +08:00

今天再看, 的确还有值得优化的地方. 比如 m.k 没有意义, 永远是 0.

iugo

2020-04-23 11:42:23 +08:00

写了一个人类优化版和一个机器优化版.

人类优化版性能下降到 88 ms, 但可以支持任意不重复的字符串.

机器优化版 `Runtime: 60 ms, faster than 99.39% of JavaScript online submissions Memory Usage: 36.7 MB, less than 100.00%`

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