打印队列

大家好，今天本人给大家带来文章《打印队列》，文中内容主要涉及到，如果你对文章方面的知识点感兴趣，那就请各位朋友继续看下去吧~希望能真正帮到你们，谢谢！

代码来临 2024 年第 5 天

第 1 部分

会有秩序！

这将会是一件很酷的事情。

我喜欢添加的警告，即不应考虑未包含在更新中的页面规则。

我对如何解决这个难题有一个模糊的想法。

但是我需要在这里制定我的策略以保持清晰并确保我准备好编写实际代码。

我希望跌跌撞撞地制定策略

这很有趣。我觉得我知道如何以过度检查的方式解决这个问题。

这就是我的想法。

将两个列表中的第一个转换为页码目录，其前面必须有任何/所有页面：

来自此：

47|53
97|13
97|61
...

对此：

{
  47: [53],
  97: [13, 61],
  ...
}

但是我该如何使用它呢？

等等。旋转！！

查看第一个示例页面更新：

75,47,61,53,29

并审查其正确顺序的深入证明......

...让我想到了过于乏味的方法：

find all page ordering rules whose two pages are both in the page update list
find the index of each page
if the first is less than the second
  the order is correct

性能方面的缺点：

• 这需要遍历每个列表的整套页面顺序规则
• 似乎是检查所有可能的数字对的任务中的阶乘

不太确定这种方法。

返回我的键对象和“之前”列表。

如果我让对象更全面怎么办：

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

• 第一个嵌套列表列出了必须位于其之前的数字
• 第二个嵌套列表列出了其后必须出现的数字

理论上（和伪代码）：

for each number in the list
  create an ordered list of the previous numbers
    check each one for inclusion in the catalogued list associated with that number
      if they are all in there
        set a flag to true
  create an ordered list of the subsequent numbers
    check each one for inclusion in the catalogued list associated with that number
      if they are all in there
        set a flag to true
  if both flags are true
    number is in the correct order

示例演练：

75

before: []
after: [47,61,53,29]

catalog:
{
  75: [ [29, 47, 53, 61, 13], [97] ]
}

before: empty - success

after: [true, true, true, true]

all true? yes - success

correct order

我绝对认为是时候编写一个至少可以构建我的目录对象的算法了。

构建编目算法

将规则从更新列表中分离出来：

let [rules, updates] = input.split('\n\n')

将输入解析为包含 2 项的列表，其中每个项目都是一个数字：

rules = rules.split('\n').map(el => el.split('|').map(number))

将该列表缩减为一个充满键和列表值的对象：

rules = rules.reduce((obj, item) => {
  if (!(item[0] in obj)) {
    obj[item[0]] = []
  }
  obj[item[0]].push(item[1])
  return obj
}, {})

这是否按预期工作？

是的，它输出这个对象：

{
  '29': [ 13 ],
  '47': [ 53, 13, 61, 29 ],
  '53': [ 29, 13 ],
  '61': [ 13, 53, 29 ],
  '75': [ 29, 53, 47, 61, 13 ],
  '97': [ 13, 61, 47, 29, 53, 75 ]
}

请注意，我回到只记录必须在任何给定数字之后的数字。

那是因为我认为我不必检查双方。

我可能错了。

但我将在这个假设下继续。

检查每个数字后面的所有数字

我将处理第一个示例更新，它应该显示为正确的。

首先，我需要将输入解析为数字列表：

updates = updates.split("\n").map((el) => el.split(",").map(number));

然后，提取第一个列表进行测试：

let test = updates[0];

现在开始真正的工作。

第一次尝试：

let results = test.map((num, index) => {
  if (num in rules) {
    let afters = test.slice(index + 1);
    let bools = afters.map((item) => rules[num].includes(item));
    return bools.every((el) => el == true) ? true : false;
  } else {
    return true;
  }
});

它似乎一直有效，直到我在第五个示例列表项上尝试它：

61, 13, 29

我的算法检查每个数字是否作为目录中的键存在，并检查其关联列表中的所有数字是否匹配。

但是13不在目录中。我的算法错误地假设了正确的判决。

当它达到 29 时，由于没有更多的数字，它也假设是正确的。

所以，我需要调整我的策略。

第二次尝试：

let results = test.map((num, index) => {
  let afters = test.slice(index + 1);
  if (afters.length) {
    let bools = afters.map((el) => {
      if (!(el in rules)) {
        return true;
      } else {
        return rules[el].includes(num) ? false : true;
      }
    });
    return bools.every((el) => el == true) ? true : false;
  } else {
    return true;
  }
});

这将为每个示例列表生成正确的答案！

它正确检查每个数字后面出现的数字子列表中的每个数字是否包含正在检查的数字（紧邻子列表之前的数字）。

因此，在以下情况下：

61, 13, 29

当遇到 13 时，它查找 29 并看到 13，这意味着它们的顺序错误。

将其插入到归约中并将中间数字相加

并没有我想象的那么难：

let part1 = updates.reduce((total, list) => {
  let result = list
    .map((num, index) => {
      let afters = list.slice(index + 1);
      if (afters.length) {
        let bools = afters.map((el) => {
          if (!(el in rules)) {
            return true;
          } else {
            return rules[el].includes(num) ? false : true;
          }
        });
        return bools.every((el) => el == true) ? true : false;
      } else {
        return true;
      }
    })
    .every((el) => el == true);
  if (result) {
    total += list[math.floor(list.length / 2)];
  }
  return total;
}, 0);

它为示例输入生成正确的答案！

它会如何处理我的拼图输入？？？

它再次生成了正确答案！！！

呜呼！！！

我觉得我有一段时间想得太多了。当我看到什么不起作用时，答案就变得清晰了。

有趣的东西！

第二部分会带来哪些新挑战......？

第2部分

排序练习

我可能应该预见到这一点。

值得庆幸的是，我认为我的算法已经为此做好了准备。

我必须对每个列表进行排序。

排序的工作原理是比较两个值并根据三个结果之一执行两件事之一：

• 如果排序函数返回 -1，则第一个值位于第二个值之前
• 如果返回 1，则第二个值应位于第一个值之前
• 如果返回 0，则不会移动任何值，因为它们相等

我的算法生成布尔值列表。

当所有布尔值都为 true 时，正确生成它们的数字位于所有布尔值之前。

但是，如果任何布尔值为 false，则其中一个数字应位于当前数字之前。

但是如果我要比较两个数字，并且它们的两个列表都有错误值，我怎么知道哪个应该排在第一位？

我真的只有一种方法来解决一个列表全部为真而另一个列表不为真，或者两者都为真的情况。

嗯嗯。

我认为我需要一次对两个数字而不是数字列表执行测试。

与排序的工作原理完全相同：a 与 b

将我的算法调整为一对一战斗而不是一对多战斗

经过一些令人头疼的事情、三元检查和事后猜测，我得出了一个可行的算法：

function orderer(a, b) {
  let atest = b in rules ? (rules[b].includes(a) ? false : true) : true;
  let btest = a in rules ? (rules[a].includes(b) ? false : true) : true;
  if (atest == false) {
    return 1;
  } else if (btest == false) {
    return -1;
  } else if (atest == btest) {
    return 0;
  }
}

在每个顺序不正确的示例更新上运行它会生成一个正确排序的列表！

我很高兴能在两个输入的所有列表上运行它，并希望今天能获得两颗当之无愧的金星！

俯瞰巨大...小细节

我在示例输入上运行了算法，得到的数字比显示的要大。

我不知道为什么。打印出每个正确排序的列表，证明其元素的顺序正确。

然后我重新阅读了说明：

仅限顺序错误的更新

说得有道理！我正在将每个列表的中间值相加！

修复此问题需要进行一点 slice() 复制列表，然后比较字符串化版本：

let part2 = updates.reduce((total, list) => {
  let copy = list.slice().sort(orderer);
  if (copy.join("") !== list.join("")) {
    total += copy[Math.floor(copy.length / 2)];
  }
  return total;
}, 0);

中提琴！我得到了示例输入的正确答案。

手指交叉，我得到它作为我的拼图输入！

确实！！！

甜甜！！

两颗金星。都是我的！

又一个有趣的谜题。

花了几天时间思考并得出一些策略。

但我最终在迷雾中找到了出路。

进入第六天！

今天关于《打印队列》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！