ARTS Week 22

Algorithm

本周的算法题为 665. 非递减数列

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

实现代码如下：

const checkPossibility = function (nums) {

  // 如果数组只有一个元素，则直接返回true
  if (nums.length === 1) {
    return true
  }
  let index = -1
  for (let i = 0; i < nums.length; i++) {
    // 只要有一个不满足的元素，就拿到元素的下标，然后跳出循环。
    if (nums[i] > nums[i + 1]) {
      index = i
      break
    }
  }
  // 如果出现元素A的下一个值A+1大于等于上一个值A-1，则将A赋值为A+1。
  if (index === 0 || nums[index + 1] >= nums[index - 1]) {
    nums[index] = nums[index + 1]
  } else {
    // 否则
    nums[index + 1] = nums[index]
  }

  // 再次遍历,如果修改某个元素后，不满足 nums[i] <= nums[i + 1]，则结果为false
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > nums[i + 1]) {
      return false
    }
  }

  return true
};

解题思路：

首先，要先遍历数组，因为不管出现几次不满足nums[i] <= nums[i + 1]条件的情况，只需要拿一次来改变元素，然后验证即可，所以当拿到不满足条件的情况时，立马跳出循环，然后通过这个元素的上一个和下一个值进行判断和改变，生成新的数组，再次遍历，如果出现一次不满足nums[i] <= nums[i + 1]条件的情况，则可知结果为false，否则为true。

Review

Giant blueberry smashes record for heaviest ever - Breaking News English Lesson

澳大利亚的一位农民刚刚创下了世界上最大蓝莓的纪录。这颗巨大的蓝莓重达惊人的20.4克，轻松打破了之前的记录，之前的纪录是16.2克。这颗创纪录的蓝莓的直径相当于乒乓球大小，直径为39.31毫米，周长为12.35厘米。这颗创纪录的蓝莓几乎比普通蓝莓重了将近10倍。这颗水果是由澳大利亚新南威尔士州的Costa集团员工种植的。高级园艺师布拉德·霍金表示，他对吉尼斯世界纪录正式认证这一记录感到非常高兴。他说：“这是良好育种和良好种植的结合。”

霍金先生表示，他的蓝莓来自Eterna品种，以其脆爽的口感和长久的保鲜期而闻名。他告诉记者：“Eterna作为一个品种，具有非常出色的口味和一致大的果实。当我们采摘这一颗时，可能还有大约20颗其他大小相似的浆果。”他补充说：“尽管这个果实很大，但在质量或口味上绝对没有妥协，就像开发高端品种时所期望的那样。”起初，他不确定是否打破了记录。他说：“我们必须重新校准天平以确保我们没有搞混。”当被问及他会如何处理他的奖品蓝莓时，他建议用它来制作一杯果汁可能是最合适的结局。

Tip

Array.prototype.reduce()

reduce() 方法对数组中的每个元素按序执行一个提供的 reducer 函数，每一次运行 reducer 会将先前元素的计算结果作为参数传入，最后将其结果汇总为单个返回值。

比如使用reduce方法找到子数组长度最长的子数组的写法为：

let longestSubArray = arrs.reduce((prev, current) => {
    return prev.length > current.length ? prev : current;
});

Share