Code ay n Golang の出現: ページの注文-Golang-php.cn

導入

コードの出現から 5 日目ですが、今日はページの順序付けという興味深い問題があります。この問題と、私がどのようにそれに取り組んだのかを見ていきましょう。冷静に考えれば非常に単純な問題ですが、そうでないとマップ、リスト、インデックスが混乱してしまいます。

ここ GitHub で私のソリューションをチェックできます。

ミスター・ディストラクティブ / コードの出現

コードの到来

入力

5 日目の入力には 2 つのセクションがあります。最初のセクションでは、ページの順序付けのルール、具体的にはどのページをどのページの前に置くかを定義し、2 番目のセクションには実際のページの順序が含まれます。

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 つのセクションにはページの順序があり、各行は処理する実際のデータとしてのクエリまたはページのリストです。パート 1 と 2 の処理で使用する必要があります。

読書セクション

したがって、これらのセクションを解析し、アクセスしやすいデータ構造で読み取る必要があります。

そのための 1 つの方法は次のとおりです

2 つのセクションからなるリスト
最初のセクションはリストになります
- リストは 2 つの整数を保持するための整数のリスト、つまりルール用です
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 と呼ばれる上記の関数は、入力ファイルへのパスを受け取り、説明したように整数のリストのスライス/配列を返します。まずファイルを読み取り、バイトをセクションの区切りとなる 2 つの改行文字に分割します。行を文字列のリストとして保存します。最初の行にはルール行が含まれ、2 番目の行にはページリスト行が含まれます。

次に、セクションを反復処理し、それぞれの区切り文字を使用してセクションの個々の行を個別に分割します。つまり、 |最初のセクションには (空白) が 2 番目のセクションに使用されます。各行を解析して整数のリストを取得し、それらをそれぞれのセクションに追加します。

これで、問題の処理に役立つルールとページの構築に使用できるデータが得られました。

ルールの構築

ここで、アクセスしやすいようにルールリストを処理する必要があります。特定のページの後に表示されるページ番号を取得する必要があるため、整数のリストを持つ整数のマップを使用します。キーは次のとおりです。最初の番号と値の 1 つは 2 番目の番号 (ページ順で後に表示される番号) になります。

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
}

ログイン後にコピー

単純に整数のリストを反復処理し、リスト内の最初の要素をキーとして、値を 2 番目の要素としてマップします。これにより、次のことが視覚化されます。

FROM

[][]int

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

TO

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

ログイン後にコピー

それで、ルールを整数と整数のマップとして作成しました。

インデックスの構築

ここで、最初と 2 番目の部分を簡単にするために、ページリストに表示されるインデックスを使用して、ルールセクションの各番号のマップを作成する必要があります。

そこで、整数と整数のマップであるルールを反復処理し、ルールから一意の整数リストを作成するのに役立つ整数のマップを作成します。

ルールから整数のリストを取得したら、すべての数値を反復処理し、ページの各行で、どのインデックスが表示されるかを確認して、整数 (インデックス) のリストを作成します。

そこで、ページの行にあるすべての数値を反復処理します。ページのリストでその数値が見つかった場合はインデックスを追加しますが、見つからなかった場合は -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 では、各ページ更新 (行) を反復する必要があります。次に、ページ番号がルールに従っているかどうかを確認する必要があります。各番号はルールに従っている必要があります。これは、番号が特定の番号の後であるが、ルールでは前にあるべきであると規定されている場合、その更新でページ番号付けルールに違反しているため、それを正しい順序のページと見なすことができず、中央のページを追加する必要があることを意味します。パート 1 の回答として正しく順序付けされた各更新の番号。

これを行うには、各ページ更新を反復し、次にそのページ更新の各数値を反復する必要があります。その数値 (現在の数値と呼ぶことにします) に関連付けられたすべてのルールを取得します。整数のリストを含む整数のマップ。ここで、現在いる番号がそのルールの番号より前であるかどうかを確認する必要があります。そこで、作成した数値インデックス (整数のリストをインデックスとして持つ数値のマップ) を使用して、現在の数値のインデックスを確認します。したがって、現在の番号をマップのキーとして使用し、リスト内のインデックスを現在いる行/ページの更新数としてマップのインデックスのリストを取得します。

現在の番号のインデックスを取得したら、そのルール内のすべての番号である 2 番目の番号についても同じものを取得します。また、ルール内のその番号がそのページ行/更新に存在するかどうか、つまり、 -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 という関数と、ページ更新としての整数のリストであるページを作成します。この関数の出力としてスコアを返します。

各ページの更新を繰り返し、更新内の各ページ番号でその番号のルールを確認し、その番号のインデックスが現在の番号より小さい場合は、その番号を順序付けされていないとしてマークします。順序が正しければ、各ページ更新の最後にページ更新の中央要素でスコアを更新します。

これがパート 1 の要約になります。必要なのは、正しい順序で更新されたページのスコアを取得することだけです。

パート 2

パート 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
}

ログイン後にコピー

したがって、この関数は数値のインデックスを見つけて、その数値のルールに違反しないように最も左端 (リストの先頭) に配置します。その後、その数値を前に追加するスライスを作成します。そのインデックスを作成し、そのインデックスの後にすべてを追加します。

パート 2 はここまでです。ページの順序に矛盾があった場合は、ページの順序を更新しました。

ここ GitHub で私のソリューションをチェックできます。