欢迎光临
我们一直在努力

[宝宝也能看懂的活动篇][30-Day LeetCoding Challenge] 第七天

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 – 30-Day LeetCoding Challenge。这是一个 leetcode 官方的小活动。可以在官网看到,从 4 月 1 号开始,每天官方会选出一道题,在 24 小时内完成即可获得一点小奖励。

这里是 4 月 7 号的题,是一道新题,不在之前的题目列表中 — 『Counting Elements』

题目描述

Given an integer array arr, count element x such that x + 1 is also in arr.
给定一个整数数组 arr,对于其中的任何一个 x,如果 x + 1 也在数组中,则计数结果加一。

If there’re duplicates in arr, count them seperately.
如果存在多个相同的 x,我们需要分别进行计数。

示例 1:

输入: arr = [1,2,3]
输出: 2
解释: 1 and 2 are counted cause 2 and 3 are in arr.

示例 2:

输入: arr = [1,1,3,3,5,5,7,7]
输出: 0
解释: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

示例 3:

输入: arr = [1,3,2,3,5,0]
输出: 3
解释: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

示例 4:

输入: arr = [1,1,2,2]
输出: 2
解释: Two 1s are counted cause 2 is in arr.

数据范围:

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 1000

官方难度

UNKNOWN(我猜 EASY)

解决思路

虽然是一道新题,不过看起来也很直白。我们可以通过记录出现过的数字,然后再判断是否存在 +1 的数字,来轻松 AC。

直接方案

思路如上,代码如下:

const countElements = (arr) => {
  const counts = new Uint8Array(1001);
  let ret = 0;
  for (const val of arr) counts[val] = 1;
  for (const val of arr) counts[val + 1] && ++ret;
  return ret;
};

换个思路

上面的代码里,我们是通过两轮遍历来完成计算。那是否可以只用一轮遍历来实现呢?

如果只用一轮遍历,就意味着在遍历过程中我们不会有完整的数字存在与否的信息,也就意味着我们需要结合当前的数据来逐渐推出结果。不过我们很容易发现,在遍历的过程中其实只有两种情况:

  • 如果存在 +1 的数字,则我们需要对当前数字进行计数,并且当前数字将被消耗掉,不能在以后继续用作累计。
  • 如果存在 -1 的数字,则我们需要对之前所有的 -1 数字进行计数,并且把它们消耗掉。

所以我们可以添加一种特殊的标识,用以指示当前数字是存在的,但是已经被完全消耗掉了。从而完成整个计数过程。具体代码如下:

const countElements = (arr) => {
  const counts = new Uint16Array(1001);
  const MAGIC = 2000;
  let ret = 0;
  for (const val of arr) {
    if (counts[val - 1] && counts[val - 1] !== MAGIC) {
      ret += counts[val - 1];
      counts[val - 1] = MAGIC;
    }
    counts[val + 1] ? (++ret, (counts[val] = MAGIC)) : ++counts[val];
  }
  return ret;
};

优化

其实这里可能有的小伙伴已经发现了,在上面的思路中,如果一个数字第一次完成了在情况 2 中的处理,那么它将不会再遇到情况 2。所以我们可以省去相关的判断,其实也就是省去这个特殊的标识,直接就能完成计数的过程。具体代码如下:

const countElements = (arr) => {
  const counts = new Uint16Array(1001);
  let ret = 0;
  for (const val of arr) {
    counts[val - 1] && !counts[val] && (ret += counts[val - 1]);
    counts[val + 1] && ++ret;
    ++counts[val];
  }
  return ret;
};

总结

虽然是一道新题目,不过想 AC 还是非常容易的,因为思路是非常明显的。只不过从两轮遍历到一轮遍历,可能稍微需要思考一下。

这里其实很有可能小伙伴们会直接跳过第二种方案,想到第三种方案。不过小猪还是把它写了出来,当做中间思路的过渡。希望能帮到有需要的小伙伴。

如果觉得不错的话,记得『三连』哦。小猪爱你们哟~

相关链接

qrcode_green.jpeg

https://segmentfault.com/a/1190000022292577

赞(0)
未经允许不得转载:ITyet » [宝宝也能看懂的活动篇][30-Day LeetCoding Challenge] 第七天
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址