仓库源文，站点原文

title: 编程题 聒噪的青蛙 categories: [leetcode, javascript]

author: iugo

写业务代码, 可能会碰到一些架构上的问题, 但性能不是重点, 很少接触真正的算法.

最近听播客, 道长介绍在硅谷面试时, 一般初级软件工程师就是算法题, 资深之后 才会有架构题, 越资深算法就越不重要.

但代码与性能是一方面, 另一方面, 能否理解问题, 解决问题, 这是任何人都需要的.

我们的前端笔试题已经很久没更新了, 后端则没有正式的笔试题. 春季招聘正需要, 就打算去 LeetCode 上抄那么几道题应对招聘.

最近的一道中等难度的题是: 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;
};

附

这里给出一些我用过的测试:

const test = [
  ["cccroacrkroakroakcroakoak", 4],
  ["cccroacrkroakroakcroakaok", -1],
  ["croakcrook", -1],
  ["croakcroak", 1],
  ["croakcroa", -1],
  ["croakcroac", -1],
];

for (const [v, r] of test) {
  const it = minNumberOfFrogs(v);
  if (it !== r) {
    throw new Error(`${v} 的结果应该为 ${r}, 却是 ${it}`);
  }
}

我最初的答案是这样的:

/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs0 = function (croakOfFrogs) {
  return croakOfFrogs
    .split("k")
    .map((v) => cDisplayTime(v))
    .reduce((acc, v) => {
      if (v > acc) {
        return v;
      }
      return acc;
    }, 0);
};

function cDisplayTime(str) {
  let count = 0;
  for (const v of str) {
    if (v === "c") {
      count += 1;
    }
  }
  return count;
}

这个答案性能不是重点, 看起来也更简单. 但不能找出错误参数. 然后我才意识到, 这道题麻烦的是校验错误.

然后老老实实依照 Hints 写了最终的答案.

Hints:

1. keep the frequency of all characters from "croak" using a hashmap.
2. For each character in the given string, greedily match it to a possible "croak".

更新

第二天早上又花了一点时间写了两个版本:

通用版: https://leetcode.com/submissions/detail/328828305/

性能版: https://leetcode.com/submissions/detail/328832285/

再翻看大家的讨论, 看到其他语言基本与我的性能版思路一致, 但通用版大家都没怎么写.

在我目前的实际工作中, 性能要求并不高, 我们更期望可读性强的代码.

这道题前前后后, 写代码, 整理思路, 发帖, 花了两三个小时, 我想 改动一下是可以作为笔试题了.

通用版代码就不写了, 以下是性能版源代码:

/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs = function (croakOfFrogs) {
  // 多出的数量
  let max = 0;

  // 储存鸣叫数量
  let c = 0;
  let r = 0;
  let o = 0;
  let a = 0;
  let k = 0;

  for (let i = 0; i < croakOfFrogs.length; i++) {
    const v = croakOfFrogs[i];
    switch (v) {
      case "c":
        c += 1;
        break;
      case "r":
        r += 1;
        if (r > c) {
          return -1;
        }
        break;
      case "o":
        o += 1;
        if (o > r) {
          return -1;
        }
        break;
      case "a":
        a += 1;
        if (a > o) {
          return -1;
        }
        break;
      case "k":
        k += 1;
        if (k > a) {
          return -1;
        }
        if (c - k > max) {
          max = c - k;
        }
        break;
      default:
        return -1;
    }
  }
  if (c !== k) {
    return -1;
  }
  return max + 1;
};