V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iugo
V2EX  ›  程序员

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

  •  
  •   iugo ·
    iugo · 2020-04-22 18:27:09 +08:00 · 2601 次点击
    这是一个创建于 1677 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    11 条回复    2020-04-23 12:14:06 +08:00
    cxe2v
        1
    cxe2v  
       2020-04-22 20:42:36 +08:00
    执行用时 :
    96 ms
    , 在所有 JavaScript 提交中击败了
    58.57%
    的用户
    内存消耗 :
    36.7 MB
    , 在所有 JavaScript 提交中击败了
    100.00%
    的用户
    cxe2v
        2
    cxe2v  
       2020-04-22 20:43:11 +08:00
    你的要快百分之 20
    momocraft
        3
    momocraft  
       2020-04-22 21:27:51 +08:00   ❤️ 1
    https://gist.github.com/jokester/1bfe4f408bf838ae4d3fd52f7d6db8d9
    好像思路比楼主的更粗暴... 速度也还行
    also24
        4
    also24  
       2020-04-22 21:56:36 +08:00   ❤️ 1
    这题优化时间的方法居然是直接声明 5 个常量来存中间值……

    另:楼主没必要每次数到 'k' 就全部减一遍,你需要的只是 m.c - m.k 这个值
    ConradG
        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%
    ConradG
        6
    ConradG  
       2020-04-22 22:13:10 +08:00
    @ConradG 咦,回复不支持 MD 的? orz
    willhunger
        7
    willhunger  
       2020-04-22 22:44:41 +08:00   ❤️ 1
    贴一个丑陋的解法,上周周赛现场解法,一直没 review
    https://paste.ubuntu.com/p/x6kZ7nvfkT/
    sherlockmao
        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
    }
    iugo
        9
    iugo  
    OP
       2020-04-23 10:08:29 +08:00
    今天再看, 的确还有值得优化的地方. 比如 m.k 没有意义, 永远是 0.
    iugo
        10
    iugo  
    OP
       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
        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;
    }
    }
    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2977 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 13:08 · PVG 21:08 · LAX 05:08 · JFK 08:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.