Golang 程式碼的出現：排序頁面-Golang-PHP中文網

首頁

後端開發

Golang

Golang 程式碼的出現：排序頁面

Mary-Kate Olsen

Dec 28, 2024 am 07:33 AM

介紹

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

您可以在 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 部分的處理中使用它。

閱讀部分

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

一個方法是

包含兩個部分的列表
第一部分將是一個清單
- 該列表將是一個整數列表，用於保存兩個整數，即用於規則
第二部分將是一個清單
- 列表將是一個整數列表，用於保存頁面列表

因此，資料結構看起來像是整數列表的列表。

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 的函數接受輸入檔案的路徑並傳回所討論的整數清單的切片/陣列。我們首先讀取檔案並將位元組拆分為兩個換行符，這將作為各部分的分隔符，我們將這些行儲存為字串列表，第一個將包含規則行，第二個將包含頁面列表行。

然後我們迭代該部分並使用對應的分隔符號分別分割各部分的各個行，即 |對於第一部分，（空白）對於第二部分。我們正在解析每一行以獲取整數列表並將它們附加到相應的部分。

所以，我們現在有了可以用來建立規則和頁面來幫助處理問題的資料。

建構規則

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

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，因此對於每一行，我們需要為該數字附加一個索引，如下圖所示：

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為參考，我們將得到每個頁碼列表的索引，並得到75出現的索引列表。

現在，這可以透過以下函數來完成：

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
}

因此，我們現在已經根據規則將索引對應到每個頁碼清單。

第 1 部分

現在，對於第一部分，我們需要迭代每個頁面更新（行），然後我們需要檢查頁碼是否遵循規則，每個數字都應該遵循規則。這意味著，如果一個數字在某個數字之後，但規則規定它應該在之前，那麼它就違反了該更新中的頁碼規則，因此我們不能將其視為正確的有序頁面，我們需要添加中間頁面每個更新的編號已正確排序為第一部分的答案。

為此，我們迭代每個頁面更新，然後我們需要迭代該頁面更新中的每個數字，我們獲得與該數字關聯的所有規則（讓我們稱之為當前數字），因為我們有一個帶有整數列表的整數映射。現在，我們必須檢查目前所在的數字是否在其規則中的數字之前。因此，我們使用我們創建的數字索引來檢查當前數字的索引，該索引是一個以整數列表作為索引的數字映射。因此，我們獲取地圖的索引列表，其中當前編號作為地圖的鍵，列表中的索引作為我們目前所在的行/頁面更新的數量。

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

當我們發現該頁面更新的索引規則被違反時，我們將訂單標記為 false。如果我們看到有序標誌仍然為 true，我們會使用該頁面更新的中間元素來更新分數。

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
}

因此，重申一下，我們建立一個名為 GetOrderedPage 的函數，其中包含規則和數字索引作為帶有整數列表的整數映射，以及頁面更新時的整數列表。我們傳回分數作為該函數的輸出。

我們迭代每個頁面更新，然後透過更新中的每個頁碼，檢查該數字的規則，如果該數字的索引低於當前數字，我們將其標記為未排序，因此在每個頁面更新的末尾，如果順序正確，我們會使用頁面更新的中間元素來更新分數。

所以，這就是第一部分的總結，我們只需要獲得正確排序的頁面更新的分數。

第2部分

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

我們對第二部分做了類似的事情，我們需要迭代每個頁面更新，並且對於該頁面更新中的每個數字，我們需要檢查是否違反規則，如果遇到以下情況對於任何數字都違反了規則，我們將有序標誌標記為false，我們將使用它來修正頁面更新的順序。更新該頁面行/更新中的頁面後，我們需要新增頁面更新正確順序的中間元素的分數。

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

我們需要實作 CorrectPageOrder 函數，該函數接受頁面行或頁面更新和規則，我們需要建立一個新的頁面更新，它將填充遵循所有規則的頁面。

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

因此，我們迭代頁面更新中的所有數字，並在規則中的任何數字之前設定索引，如果我們在規則映射中遇到任何此類數字，我們需要使用該數字的索引來更新索引。

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

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
}

因此，這個函數將找到一個數字的索引，將其放置在最左邊（列表的開頭），這樣我們就不會違反該數字的任何規則，然後我們創建一個切片來將該數字附加到之前該索引並附加該索引後的所有內容。

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

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