介紹

這是程式碼出現(xiàn)的第五天，今天我們遇到了一個(gè)有趣的頁(yè)面排序問(wèn)題。讓我們深入探討這個(gè)問(wèn)題以及我是如何解決它的。如果平靜地思考，這是一個(gè)非常簡(jiǎn)單的問(wèn)題，否則，它會(huì)陷入地圖、清單和索引的混亂中。

您可以在 GitHub 上查看我的解決方案。

輸入

在第 5 天的輸入中，我們有兩個(gè)部分，第一個(gè)部分定義了頁(yè)面排序規(guī)則，具體來(lái)說(shuō)哪個(gè)頁(yè)面應(yīng)該在哪個(gè)頁(yè)面之前，第二個(gè)部分包含頁(yè)面的實(shí)際順序。

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

因此，第一部分制定了規(guī)則，另一部分制定了頁(yè)面的順序，每一行都是查詢或頁(yè)面列表，作為我們要處理的實(shí)際資料。我們需要在第 1 部分和第 2 部分的處理中使用它。

閱讀部分

因此，我們需要解析這些部分並以更易於存取的資料結(jié)構(gòu)讀取它們。

一個(gè)方法是

• 包含兩個(gè)部分的列表

• 第一部分將是一個(gè)清單

  • 該列表將是一個(gè)整數(shù)列表，用於保存兩個(gè)整數(shù)，即用於規(guī)則

• 第二部分將是一個(gè)清單

  • 列表將是一個(gè)整數(shù)列表，用於保存頁(yè)面列表

因此，資料結(jié)構(gòu)看起來(lái)像是整數(shù)列表的列表。

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    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, "\n")
        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 的函數(shù)接受輸入檔案的路徑並傳回所討論的整數(shù)清單的切片/陣列。我們首先讀取檔案並將位元組拆分為兩個(gè)換行符，這將作為各部分的分隔符，我們將這些行儲(chǔ)存為字串列表，第一個(gè)將包含規(guī)則行，第二個(gè)將包含頁(yè)面列表行。

然後我們迭代該部分並使用對(duì)應(yīng)的分隔符號(hào)分別分割各部分的各個(gè)行，即 |對(duì)於第一部分，（空白）對(duì)於第二部分。我們正在解析每一行以獲取整數(shù)列表並將它們附加到相應(yīng)的部分。

所以，我們現(xiàn)在有了可以用來(lái)建立規(guī)則和頁(yè)面來(lái)幫助處理問(wèn)題的資料。

建構(gòu)規(guī)則

現(xiàn)在，我們需要處理規(guī)則列表以方便訪問(wèn)，我們需要獲取給定頁(yè)面之後應(yīng)該出現(xiàn)的頁(yè)碼，因此我們將使用帶有整數(shù)列表的整數(shù)映射，其中鍵為第一個(gè)數(shù)字和值中的一個(gè)將是第二個(gè)數(shù)字（按頁(yè)面順序應(yīng)出現(xiàn)在其後的數(shù)字）。

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
}

我們簡(jiǎn)單地迭代整數(shù)列表，並將第一個(gè)元素映射為鍵，將值映射為列表中的第二個(gè)元素，以便可視化：

FROM

[][]int

[
    [47,53]
    [97,13]
    [97,61]
]

TO

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

所以，現(xiàn)在規(guī)則是整數(shù)與整數(shù)的對(duì)應(yīng)。

建構(gòu)指數(shù)

現(xiàn)在，為了使第一部分和第二部分更容易，我們需要使用頁(yè)面清單中出現(xiàn)的索引為規(guī)則部分中的每個(gè)數(shù)字製作一個(gè)映射。

因此，我們將迭代規(guī)則，這是一個(gè)整數(shù)和整數(shù)的映射，我們將創(chuàng)建一個(gè)整數(shù)映射，它將幫助我們根據(jù)規(guī)則創(chuàng)建唯一的整數(shù)列表。

現(xiàn)在，一旦我們從規(guī)則中獲得了整數(shù)列表，我們將迭代所有數(shù)字，並在每個(gè)頁(yè)面行上檢查它出現(xiàn)的索引，以建立整數(shù)（索引）列表。

因此，我們迭代頁(yè)面行中的所有數(shù)字，如果我們?cè)陧?yè)面列表中找到該數(shù)字，則附加索引，但是，如果沒(méi)有，我們附加-1，因此對(duì)於每一行，我們需要為該數(shù)字附加一個(gè)索引，如下圖所示：

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

所以，在上面的例子中，我們以75為參考，我們將得到每個(gè)頁(yè)碼列表的索引，並得到75出現(xiàn)的索引列表。

現(xiàn)在，這可以透過(guò)以下函數(shù)來(lái)完成：

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    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, "\n")
        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
}

因此，我們現(xiàn)在已經(jīng)根據(jù)規(guī)則將索引對(duì)應(yīng)到每個(gè)頁(yè)碼清單。

第 1 部分

現(xiàn)在，對(duì)於第一部分，我們需要迭代每個(gè)頁(yè)面更新（行），然後我們需要檢查頁(yè)碼是否遵循規(guī)則，每個(gè)數(shù)字都應(yīng)該遵循規(guī)則。這意味著，如果一個(gè)數(shù)字在某個(gè)數(shù)字之後，但規(guī)則規(guī)定它應(yīng)該在之前，那麼它就違反了該更新中的頁(yè)碼規(guī)則，因此我們不能將其視為正確的有序頁(yè)面，我們需要添加中間頁(yè)面每個(gè)更新的編號(hào)已正確排序?yàn)榈谝徊糠值拇鸢浮?

為此，我們迭代每個(gè)頁(yè)面更新，然後我們需要迭代該頁(yè)面更新中的每個(gè)數(shù)字，我們獲得與該數(shù)字關(guān)聯(lián)的所有規(guī)則（讓我們稱之為當(dāng)前數(shù)字），因?yàn)槲覀冇幸粋€(gè)帶有整數(shù)列表的整數(shù)映射?，F(xiàn)在，我們必須檢查目前所在的數(shù)字是否在其規(guī)則中的數(shù)字之前。因此，我們使用我們創(chuàng)建的數(shù)字索引來(lái)檢查當(dāng)前數(shù)字的索引，該索引是一個(gè)以整數(shù)列表作為索引的數(shù)字映射。因此，我們獲取地圖的索引列表，其中當(dāng)前編號(hào)作為地圖的鍵，列表中的索引作為我們目前所在的行/頁(yè)面更新的數(shù)量。

然後，一旦我們獲得了當(dāng)前數(shù)字的索引，我們就獲得了第二個(gè)數(shù)字的相同索引，即其規(guī)則中的所有數(shù)字，並且如果其規(guī)則中的該數(shù)字存在於該頁(yè)行/更新中，即它是不是-1，如果是這種情況，我們類似地獲取它的索引，並檢查它是否出現(xiàn)在符合規(guī)則的當(dāng)前數(shù)字之後，因此，如果任何數(shù)字違反規(guī)則，我們需要將頁(yè)面更新標(biāo)記為不正確訂購(gòu)。

當(dāng)我們發(fā)現(xiàn)該頁(yè)面更新的索引規(guī)則被違反時(shí)，我們將訂單標(biāo)記為 false。如果我們看到有序標(biāo)誌仍然為 true，我們會(huì)使用該頁(yè)面更新的中間元素來(lái)更新分?jǐn)?shù)。

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
}

因此，重申一下，我們建立一個(gè)名為 GetOrderedPage 的函數(shù)，其中包含規(guī)則和數(shù)字索引作為帶有整數(shù)列表的整數(shù)映射，以及頁(yè)面更新時(shí)的整數(shù)列表。我們傳回分?jǐn)?shù)作為該函數(shù)的輸出。

我們迭代每個(gè)頁(yè)面更新，然後透過(guò)更新中的每個(gè)頁(yè)碼，檢查該數(shù)字的規(guī)則，如果該數(shù)字的索引低於當(dāng)前數(shù)字，我們將其標(biāo)記為未排序，因此在每個(gè)頁(yè)面更新的末尾，如果順序正確，我們會(huì)使用頁(yè)面更新的中間元素來(lái)更新分?jǐn)?shù)。

所以，這就是第一部分的總結(jié)，我們只需要獲得正確排序的頁(yè)面更新的分?jǐn)?shù)。

第2部分

但是在第 2 部分中，我們需要檢查頁(yè)面更新是否按順序進(jìn)行，如果不按順序進(jìn)行更新。

我們對(duì)第二部分做了類似的事情，我們需要迭代每個(gè)頁(yè)面更新，並且對(duì)於該頁(yè)面更新中的每個(gè)數(shù)字，我們需要檢查是否違反規(guī)則，如果遇到以下情況對(duì)於任何數(shù)字都違反了規(guī)則，我們將有序標(biāo)誌標(biāo)記為false，我們將使用它來(lái)修正頁(yè)面更新的順序。更新該頁(yè)面行/更新中的頁(yè)面後，我們需要新增頁(yè)面更新正確順序的中??間元素的分?jǐn)?shù)。

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

我們需要實(shí)作 CorrectPageOrder 函數(shù)，該函數(shù)接受頁(yè)面行或頁(yè)面更新和規(guī)則，我們需要建立一個(gè)新的頁(yè)面更新，它將填充遵循所有規(guī)則的頁(yè)面。

因此，我們首先追蹤初始化的元素索引，如果需要移動(dòng)它之前的元素，則更新索引。

因此，我們迭代頁(yè)面更新中的所有數(shù)字，並在規(guī)則中的任何數(shù)字之前設(shè)定索引，如果我們?cè)谝?guī)則映射中遇到任何此類數(shù)字，我們需要使用該數(shù)字的索引來(lái)更新索引。

一旦我們獲得了要交換元素的索引，我們就在該索引之前建立一個(gè)切片並將該數(shù)字附加到其中，並在該索引之後附加所有內(nèi)容。

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    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, "\n")
        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
}

因此，這個(gè)函數(shù)將找到一個(gè)數(shù)字的索引，將其放置在最左邊（列表的開(kāi)頭），這樣我們就不會(huì)違反該數(shù)字的任何規(guī)則，然後我們創(chuàng)建一個(gè)切片來(lái)將該數(shù)字附加到之前該索引並附加該索引後的所有內(nèi)容。

第二部分就是這樣，如果頁(yè)面順序有任何差異，我們已經(jīng)更新了頁(yè)面順序。

您可以在 GitHub 上查看我的解決方案。

結(jié)論

所以，這就是 Golang 程式碼降臨的第五天，如果您有任何建議，以及您是如何實(shí)現(xiàn)的，請(qǐng)告訴我。有更好的解決方案嗎？

快樂(lè)編碼:)

以上是Golang 程式碼的出現(xiàn)：排序頁(yè)面的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！