时间戳

首页 > 解决方案 > Codewars“最接近和最小” - 与预期输出不匹配

javascript - Codewars“最接近和最小” - 与预期输出不匹配

问题描述

我为 Codewars 5kyu 挑战Closest 和 Smallest编写了以下代码。

输入

  • 一串strngn 个正数（n = 0 或 n >= 2） 让我们将一个数字的权重称为其数字的总和。例如99会有 "weight" 18，100会有 "weight" 1。

如果它们的权重差异很小，则两个数字是“接近的”。

任务：

对于每个数字，strng计算其“权重”，然后找到其中的两个数字strng：

  • 最小的权重差异，即最接近的
  • 用最小的权重
  • 并且具有最小的索引（或排名，从 0 开始编号）strng

输出：

  • 由两个数组组成的数组，每个子数组的格式如下：

    [number-weight, index in strng of the corresponding number, original
corresponding number in strng]

如果两个子数组的权重不同，则按它们的数字权重升序排序，如果它们具有相同的权重，则按它们在字符串中的索引进行排序。

我在节点中使用 Jest 在本地对其进行测试 - 一切正常。
但它没有通过 Codewars 的测试。我真的很感激这方面的任何提示。谢谢！

function closest(string) {
  if (string.length < 1)
    return [];
  const nums = string.split(" ");
  const weights = nums.map(e => e.split('').reduce((p, a) => Number(p) + Number(a)));
  const indexedWeights = [];
  let indexCounter = 0;
  for (let w of weights)
    indexedWeights.push([w, indexCounter++, Number(nums.shift())])
  let collected = [];
  indexedWeights.forEach(iw => {
    const iWCopy = indexedWeights.filter(item => item !== iw);
    const closest = iWCopy.reduce((a, b) => Math.abs(b[0] - iw[0]) < Math.abs(a[0] - iw[0]) ? b : a);
    const diff = Math.abs(closest[0] - iw[0]);
    collected.push([diff, iw[0], iw[1], iw[2]]);
  });
  collected.sort((a, b) => a[0] - b[0])
  const lowestDiff = collected[0][0]
  const result = collected.filter(n => n[0] === lowestDiff)
  result.sort((a, b) => a[1] - b[1])
  return [result[0].splice(1, 4), result[1].splice(1, 4)];
}

测试：

const closest = require("../5kyu_challenges/closestAndSmallest");
describe("closest", () => {
  test("returns an array containing 2 sub-arrays which consist of 3 numbers representing closest and smallest numbers", () => {
    expect(closest("")).toEqual([]);
    expect(closest("456899 50 11992 176 272293 163 389128 96 290193 85 52")).toEqual([ [13, 9, 85], [14, 3, 176] ]);
  });
  test("sorts by index number if weights are equal", () => {
    expect(closest("239382 162 254765 182 485944 134 468751 62 49780 108 54")).toEqual([ [8, 5, 134], [8, 7, 62] ]);
    expect(closest("403749 18 278325 97 304194 119 58359 165 144403 128 38")).toEqual([ [11, 5, 119], [11, 9, 128] ]);
  });
});

标签： javascriptnode.jstestingjestjs

解决方案

要求也是按匹配的索引对输出进行排序（我强调）：

如果这两个子数组的权重不同，则按它们的数字权重升序排序，如果它们具有相同的权重，则按它们在字符串中的索引进行排序。

所以在你的代码中改变这一行：

result.sort((a, b) => a[1] - b[1])

有了这个：

result.sort((a, b) => a[1] - b[1] || a[2] - b[2])

效率

请注意，排序的时间复杂度为O(nlogn)。因此，如果输入是一个非常大的数组，与扫描数组的最小值collected相比，排序可能是一个较差的解决方案。collected

推荐阅读