Sudah hari ke-5 kemunculan kod, dan hari ini kami menghadapi masalah yang menarik untuk memesan halaman. Mari kita selami masalah itu dan bagaimana saya menghadapinya. Ia adalah masalah yang agak mudah jika difikirkan dengan tenang, jika tidak, ia akan masuk ke dalam peta, senarai, dan kucar-kacir indeks.
Anda boleh menyemak penyelesaian saya di sini di GitHub.
Dalam input untuk hari ke-5, kami mempunyai dua bahagian, Yang pertama mentakrifkan peraturan untuk memesan halaman, khususnya halaman mana yang harus didahulukan dan yang kedua mengandungi susunan halaman yang sebenar.
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
Jadi, bahagian pertama mempunyai peraturan yang dipetakan, bahagian lain mempunyai susunan halaman dan setiap baris ialah pertanyaan atau senarai halaman sebagai data sebenar kami untuk diproses. Kita perlu menggunakannya dalam pemprosesan bahagian 1 dan 2.
Jadi, kita perlu menghuraikan bahagian ini dan membacanya dalam struktur data yang lebih mudah diakses.
Salah satu cara untuk melakukannya ialah
Senarai dengan dua bahagian
Bahagian pertama akan menjadi senarai
Bahagian kedua akan menjadi senarai
Jadi, struktur data akan kelihatan seperti senarai senarai senarai integer.
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 }
Fungsi di atas yang dipanggil ReadFileSections mengambil laluan ke fail input dan mengembalikan kepingan/tatasusunan) senarai senarai integer seperti yang dibincangkan. Kami mula-mula membaca fail dan membahagikan bait kepada dua aksara baris baharu yang akan menjadi pemisah untuk bahagian, kami akan menyimpan baris sebagai senarai rentetan, yang pertama akan mengandungi baris peraturan dan yang kedua akan mengandungi baris senarai halaman.
Kemudian kami mengulangi bahagian dan membahagikan baris individu untuk bahagian secara berasingan dengan pemisah masing-masing iaitu | untuk bahagian pertama dan (ruang putih) untuk bahagian kedua. Kami sedang menghuraikan setiap baris untuk mendapatkan senarai integer dan menambahkannya pada bahagian masing-masing.
Jadi, kami kini mempunyai data yang boleh kami gunakan untuk membina peraturan dan halaman untuk membantu memproses masalah.
Sekarang, kita perlu memproses senarai peraturan untuk akses mudah, kita perlu mendapatkan nombor halaman yang sepatutnya muncul selepas halaman tertentu, jadi kita akan menggunakan peta integer dengan senarai integer, di mana kuncinya akan nombor pertama dan satu daripada nilai akan menjadi nombor kedua ( nombor yang sepatutnya muncul selepas dalam susunan halaman).
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 }
Kami hanya mengulangi senarai integer dan memetakan elemen pertama sebagai kunci dan nilai sebagai elemen kedua dalam senarai, jadi untuk menggambarkan:
FROM [][]int [ [47,53] [97,13] [97,61] ] TO map[int][]int { 47: [53] 97: [13,61] }
Jadi, sekarang mempunyai peraturan sebagai peta integer dengan integer.
Kini, untuk memudahkan bahagian pertama dan kedua, kita perlu membuat peta untuk setiap nombor dalam bahagian peraturan dengan indeks yang muncul dalam senarai halaman.
Jadi, kami akan mengulangi peraturan, iaitu peta integer dan integer, kami akan mencipta peta integer yang akan membantu kami membuat senarai integer yang unik daripada peraturan.
Sekarang, setelah kami mempunyai senarai integer daripada peraturan, kami akan mengulangi semua nombor dan pada setiap baris halaman, semak pada indeks yang mana ia muncul, untuk membuat senarai integer(indeks).
Jadi, kami mengulangi semua nombor dalam baris halaman, jika kami mendapati nombor itu dalam senarai halaman, kami menambah indeks, namun, jika tidak kami tambahkan -1, jadi untuk setiap baris kami perlu mempunyai indeks yang dilampirkan untuk nombor tersebut seperti:
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
Jadi, dalam contoh di atas, kami telah mengambil 75 sebagai rujukan, kami akan mendapat indeks untuk setiap senarai nombor halaman dan kami mendapat senarai indeks di mana 75 muncul.
Kini, ini boleh dilakukan dengan fungsi berikut:
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 }
Jadi, kami kini mempunyai indeks yang dipetakan pada setiap senarai nombor halaman daripada peraturan.
Sekarang, untuk bahagian satu kita perlu mengulangi setiap kemas kini halaman (baris), kemudian kita perlu menyemak sama ada nombor halaman mengikut peraturan, setiap nombor harus mengikut peraturan. Ini bermakna jika nombor selepas nombor tertentu tetapi peraturan mengatakan ia sepatutnya sebelum, maka ia telah melanggar peraturan penomboran halaman dalam kemas kini itu, jadi kami tidak boleh menganggapnya sebagai halaman tersusun yang betul, kami perlu menambah halaman tengah nombor setiap kemas kini yang disusun dengan betul sebagai jawapan untuk bahagian satu.
Untuk melakukan itu, kami mengulangi setiap kemas kini halaman, kemudian kami perlu mengulangi setiap nombor dalam kemas kini halaman itu, kami memperoleh semua peraturan yang berkaitan dengan nombor itu (mari kita panggil nombor semasa) kerana kami mempunyai peta integer dengan senarai integer. Sekarang, kita perlu menyemak sama ada nombor yang kita ada sekarang adalah sebelum nombor dalam peraturannya. Jadi, kita semak dengan indeks nombor semasa menggunakan indeks nombor yang kami buat iaitu peta nombor dengan senarai integer sebagai indeks. Jadi, kami memperoleh senarai indeks peta dengan nombor semasa sebagai kunci untuk peta dan indeks dalam senarai sebagai bilangan kemas kini baris/halaman yang kami ada sekarang.
Kemudian setelah kami mendapat indeks untuk nombor semasa, kami memperoleh yang sama untuk nombor kedua iaitu semua nombor dalam peraturannya, dan jika nombor itu dalam peraturannya terdapat dalam baris halaman/kemas kini iaitu ia adalah bukan -1 dan jika itu berlaku, kami mendapat indeksnya sama dan semak sama ada ia muncul selepas nombor semasa mengikut peraturan, Dan jika ada nombor yang melanggar peraturan, kami perlu menandakan kemas kini halaman sebagai tidak betul pesanan.
Memandangkan kami melihat bahawa peraturan indeks untuk kemas kini halaman itu dilanggar, kami menandai pesanan itu sebagai palsu. Jika kami melihat bendera yang dipesan masih benar, kami mengemas kini skor dengan elemen tengah kemas kini halaman tersebut.
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 }
Jadi, untuk mengulangi, kami mencipta fungsi yang dipanggil GetOrderedPage dengan peraturan dan indeks nombor sebagai peta integer dengan senarai integer dan halaman yang merupakan senarai integer sebagai kemas kini halaman. Kami mengembalikan skor sebagai output fungsi ini.
Kami berulang melalui setiap kemas kini halaman, kemudian melalui setiap nombor halaman dalam kemas kini, kami menyemak peraturan nombor itu dan jika indeks itu lebih rendah daripada nombor semasa kami menandakannya sebagai tidak dipesan, dan dengan itu pada akhir setiap kemas kini halaman kami mengemas kini skor dengan elemen tengah kemas kini halaman, jika susunannya betul.
Jadi, itu akan menjadi bahagian satu diringkaskan, kita hanya perlu mendapatkan skor kemas kini halaman yang dipesan yang betul.
Walau bagaimanapun, dalam bahagian 2, kita perlu menyemak sama ada kemas kini halaman adalah teratur, jika tidak maka kita perlu menyusunnya dengan teratur.
Kami melakukan perkara yang sama untuk bahagian 2, kami perlu mengulangi setiap kemas kini halaman dan untuk setiap nombor dalam kemas kini halaman itu, kami perlu menyemak sama ada peraturan itu dilanggar atau tidak, jika kami menghadapi sebarang kes di mana peraturan dilanggar untuk sebarang nombor, kami menandakan bendera yang dipesan sebagai palsu, ini akan kami gunakan untuk membetulkan susunan kemas kini halaman. Selepas mengemas kini halaman dalam baris halaman/kemas kini, kami perlu menambah skor dengan elemen tengah urutan kemas kini halaman yang diperbetulkan.
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
Kita perlu melaksanakan fungsi CorrectPageOrder yang mengambil baris halaman atau kemas kini halaman dan peraturan, kita perlu membuat kemas kini halaman baharu, yang akan mengisi halaman yang mengikut semua peraturan.
Jadi, kami mula-mula menjejaki indeks elemen yang dimulakan dan mengemas kini indeks jika kami perlu mengalihkan elemen sebelum itu.
Jadi, kami mengulangi semua nombor dalam kemas kini halaman dan menetapkan indeks sebelum sebarang nombor dalam peraturan, jika kami menemui sebarang nombor sedemikian dalam peta peraturan, kami perlu mengemas kini indeks dengan indeks nombor itu.
Dan sebaik sahaja kami mendapat indeks tempat kami ingin menukar elemen itu, kami membuat hirisan sebelum indeks itu dan menambahkan nombor itu ke dalamnya, dan menambahkan semuanya selepas indeks itu.
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 }
Jadi, fungsi ini akan mencari indeks nombor untuk meletakkannya di sebelah kiri paling ekstrem (permulaan senarai) supaya kami tidak melanggar sebarang peraturan untuk nombor itu, kemudian kami membuat kepingan untuk menambah nombor itu sebelum indeks itu dan tambahkan semuanya selepas indeks itu.
Itu sahaja dari bahagian dua, kami telah mengemas kini susunan halaman jika terdapat sebarang percanggahan dalam susunan halaman.
Anda boleh menyemak penyelesaian saya di sini di GitHub.
Jadi, itu sahaja dari hari ke-5 Kemunculan Kod di Golang, beritahu saya jika anda mempunyai sebarang cadangan dan cara anda mendekatinya. ada penyelesaian yang lebih baik?
Selamat Mengekod :)
Atas ialah kandungan terperinci Kemunculan Kod ay n Golang: Halaman Pesanan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!