介绍
这是代码出现的第五天，今天我们遇到了一个有趣的页面排序问题。让我们深入探讨这个问题以及我是如何解决它的。如果平静地思考，这是一个非常简单的问题，否则，它会陷入地图、列表和索引的混乱中。
您可以在 github 上查看我的解决方案。
破坏先生 / 代码出现
代码的出现
输入
在第 5 天的输入中，我们有两个部分，第一个部分定义了页面排序规则，具体来说哪个页面应该在哪个页面之前，第二个部分包含页面的实际顺序。
47|53 97|13 97|61 97|47 75|29 61|13 75|53 29|13 97|29 53|29 61|53 97|53 61|29 47|13 75|47 97|75 47|61 75|61 47|29 75|13 53|13 75,47,61,53,29 97,61,53,29,13 75,29,13 75,97,47,61,53 61,13,29 97,13,75,29,47
因此，第一部分制定了规则，另一部分制定了页面的顺序，每一行都是一个查询或页面列表，作为我们要处理的实际数据。我们需要在第 1 部分和第 2 部分的处理中使用它。
阅读部分
因此，我们需要解析这些部分并以更易于访问的数据结构读取它们。
一种方法是
立即学习“go语言免费学习笔记（深入）”；
-
包含两个部分的列表
-
第一部分将是一个列表
- 该列表将是一个整数列表，用于保存两个整数，即用于规则
-
第二部分将是一个列表
- 列表将是一个整数列表，用于保存页面列表
因此，数据结构看起来像一个整数列表的列表。
func readfilesections(path string) [][][]int { filebytes := readfilebytes(path) lines := []string{} separator := []byte(" ") for _, line := range bytes.split(filebytes, separator) { if string(line) != "" { lines = append(lines, string(line)) } } sections := [][][]int{} for i, section := range lines { nums := [][]int{} linestrs := strings.split(section, " ") separator := "," if i == 0 { separator = "|" } for _, linestr := range linestrs { if linestr == "" { continue } numl := []int{} for _, numstr := range strings.split(linestr, separator) { num, _ := strconv.atoi(numstr) numl = append(numl, num) } nums = append(nums, numl) } sections = append(sections, nums) } return sections }
上述名为 readfilesections 的函数接受输入文件的路径并返回所讨论的整数列表的切片/数组。我们首先读取文件并将字节拆分为两个换行符，这将作为各部分的分隔符，我们将这些行存储为字符串列表，第一个将包含规则行，第二个将包含页面列表行。
然后我们迭代该部分并使用相应的分隔符分别分割各部分的各个行，即 |对于第一部分，（空白）对于第二部分。我们正在解析每一行以获取整数列表并将它们附加到相应的部分。
所以，我们现在有了可以用来构建规则和页面来帮助处理问题的数据。
构建规则
现在，我们需要处理规则列表以便于访问，我们需要获取给定页面之后应该出现的页码，因此我们将使用带有整数列表的整数映射，其中键为第一个数字和值中的一个将是第二个数字（按页面顺序应出现在其后的数字）。
func constructrules(ruleslist [][]int) map[int][]int { rules := make(map[int][]int) for _, rule := range ruleslist { rules[rule[0]] = append(rules[rule[0]], rule[1]) } return rules }
我们简单地迭代整数列表，并将第一个元素映射为键，将值映射为列表中的第二个元素，以便可视化：
from [][]int [ [47,53] [97,13] [97,61] ] to map[int][]int { 47: [53] 97: [13,61] }
所以，现在规则是整数与整数的映射。
构建指数
现在，为了使第一部分和第二部分更容易，我们需要使用页面列表中出现的索引为规则部分中的每个数字制作一个映射。
因此，我们将迭代规则，这是一个整数和整数的映射，我们将创建一个整数映射，它将帮助我们根据规则创建唯一的整数列表。
现在，一旦我们从规则中获得了整数列表，我们将迭代所有数字，并在每个页面行上检查它出现的索引，以创建整数（索引）列表。
因此，我们迭代页面行中的所有数字，如果我们在页面列表中找到该数字，则附加索引，但是，如果没有，我们附加 -1，因此对于每一行，我们需要为该数字附加一个索引，如下所示：
# 75 75,47,61,53,29 -> 0 97,61,53,29,13 -> -1 75,29,13 -> 0 75,97,47,61,53 -> 0 61,13,29 -> -1 97,13,75,29,47 -> 2 75[0,-1,0,0,-1,2] # map[int][]int # 75 -> int # [0,-1,0,0,-1,2] -> []int
所以，在上面的例子中，我们以75为参考，我们将得到每个页码列表的索引，并得到75出现的索引列表。
现在，这可以通过以下函数来完成：
func getpageindices(rules map[int][]int, pages [][]int) map[int][]int { nums := make(map[int]bool) for num, list := range rules { nums[num] = true for _, elem := range list { if !nums[elem] { nums[elem] = true } } } numindices := make(map[int][]int) for num, _ := range nums { for _, numline := range pages { index := -1 for i, n := range numline { if n == num { index = i } } numindices[num] = append(numindices[num], index) } } return numindices }
因此，我们现在已经根据规则将索引映射到每个页码列表。
第 1 部分
现在，对于第一部分，我们需要迭代每个页面更新（行），然后我们需要检查页码是否遵循规则，每个数字都应该遵循规则。这意味着，如果一个数字在某个数字之后，但规则规定它应该在之前，那么它就违反了该更新中的页码规则，因此我们不能将其视为正确的有序页面，我们需要添加中间页面每个更新的编号已正确排序为第一部分的答案。
为此，我们迭代每个页面更新，然后我们需要迭代该页面更新中的每个数字，我们获得与该数字关联的所有规则（让我们称之为当前数字），因为我们有一个带有整数列表的整数映射。现在，我们必须检查当前所在的数字是否在其规则中的数字之前。因此，我们使用我们创建的数字索引来检查当前数字的索引，该索引是一个以整数列表作为索引的数字映射。因此，我们获取地图的索引列表，其中当前编号作为地图的键，列表中的索引作为我们当前所在的行/页面更新的数量。
然后，一旦我们获得了当前数字的索引，我们就获得了第二个数字的相同索引，即其规则中的所有数字，并且如果其规则中的该数字存在于该页行/更新中，即它是不是-1，如果是这种情况，我们类似地获取它的索引，并检查它是否出现在符合规则的当前数字之后，因此，如果任何数字违反规则，我们需要将页面更新标记为不正确订购。
当我们发现该页面更新的索引规则被违反时，我们将订单标记为 false。如果我们看到有序标志仍然为 true，我们会使用该页面更新的中间元素来更新分数。
func getorderedpages(rules, numindices map[int][]int, pages [][]int) int { score := 0 for index, pageline := range pages { ordered := true for _, num1 := range pageline { rule := rules[num1] index1 := numindices[num1][index] for _, num2 := range rule { index2 := numindices[num2][index] if index1 == -1 || index2 == -1 { continue } if index1 > index2 { ordered = false } } } if ordered { score += pageline[int(len(pageline)/2)] } } return score }
因此，重申一下，我们创建一个名为 getorderedpage 的函数，其中包含规则和数字索引作为带有整数列表的整数映射，以及页面更新时的整数列表。我们返回分数作为该函数的输出。
我们迭代每个页面更新，然后通过更新中的每个页码，检查该数字的规则，如果该数字的索引低于当前数字，我们将其标记为未排序，因此在每个页面更新结束时，如果顺序正确，我们会使用页面更新的中间元素更新分数。
所以，这就是第一部分的总结，我们只需要获得正确排序的页面更新的分数即可。
第2部分
但是在第 2 部分中，我们需要检查页面更新是否按顺序进行，如果不按顺序进行更新。
我们对第二部分做了类似的事情，我们需要迭代每个页面更新，并且对于该页面更新中的每个数字，我们需要检查是否违反规则，如果遇到以下情况对于任何数字都违反了规则，我们将有序标志标记为 false，我们将使用它来纠正页面更新的顺序。更新该页面行/更新中的页面后，我们需要添加页面更新正确顺序的中间元素的分数。
func getcorrectorderedpages(rules, numindices map[int][]int, pages [][]int) int { score := 0 for index, pageline := range pages { ordered := true for _, num1 := range pageline { rule := rules[num1] index1 := numindices[num1][index] for _, num2 := range rule { index2 := numindices[num2][index] if index1 == -1 || index2 == -1 { continue } if index1 > index2 { ordered = false } } } if !ordered { newline := correctpageorder(pageline, rules) score += newline[len(newline)/2] } } return score }
我们需要实现 correctpageorder 函数，该函数接受页面行或页面更新和规则，我们需要创建一个新的页面更新，它将填充遵循所有规则的页面。
因此，我们首先跟踪初始化的元素索引，如果需要移动它之前的元素，则更新索引。
因此，我们迭代页面更新中的所有数字，并在规则中的任何数字之前设置索引，如果我们在规则映射中遇到任何此类数字，我们需要使用该数字的索引来更新索引。
一旦我们获得了要交换元素的索引，我们就在该索引之前创建一个切片并将该数字附加到其中，并在该索引之后附加所有内容。
func CorrectPageOrder(line []int, rules map[int][]int) []int { newLine := []int{} for _, num := range line { index := make(map[int]int) for i, n := range newLine { index[n] = i } newInsertIndex := len(newLine) for _, rule := range rules[num] { if idx, ok := index[rule]; ok { if newInsertIndex > idx { newInsertIndex = idx } } } afterNum := slices.Clone(newLine[newInsertIndex:]) newLine = append(newLine[:newInsertIndex], num) newLine = append(newLine, afterNum...) } return newLine }
因此，这个函数将找到一个数字的索引，将其放置在最左边（列表的开头），这样我们就不会违反该数字的任何规则，然后我们创建一个切片来将该数字附加到之前该索引并附加该索引后的所有内容。
第二部分就是这样，如果页面顺序有任何差异，我们已经更新了页面顺序。
您可以在 github 上查看我的解决方案。
破坏先生 / 代码出现
代码的出现
结论
所以，这就是 golang 代码降临的第五天，如果您有任何建议，以及您是如何实现的，请告诉我。有更好的解决方案吗？
快乐编码:)
