3

编程题 聒噪的青蛙 | news view

 3 years ago
source link: https://zsqk.github.io/news/2020-04-22-leetcode-minimum-number-of-frogs-croaking.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

news view

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

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

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

我们的前端笔试题已经很久没更新了, 后端则没有正式的笔试题. 春季招聘正需要, 就打算去 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;
};

- leetcode

- javascript

This site is open source. Improve this page.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK