Cara menggunakan bahasa golang untuk melaksanakan algoritma penjumlahan senarai terpaut

Menjumlahkan senarai terpaut ialah masalah algoritma biasa. Idea asasnya ialah menambah digit dalam dua senarai terpaut untuk mendapatkan senarai terpaut baharu yang mewakili jumlahnya.

Artikel ini akan memperkenalkan cara menggunakan bahasa golang untuk melaksanakan algoritma penjumlahan senarai terpaut.

Pertama, kita perlu mentakrifkan struktur nod senarai terpaut, yang mengandungi dua medan: val mewakili nilai nod, dan seterusnya mewakili penuding ke nod seterusnya.

type ListNode struct {
    Val  int
    Next *ListNode
}

Seterusnya, kita boleh mentakrifkan fungsi AddTwoNumbers, yang menerima dua senarai terpaut l1 dan l2 serta mengembalikan senarai terpaut baharu yang terdiri daripada jumlahnya.

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0  // 进位值
    dummy := &ListNode{Val: 0, Next: nil}
    curr := dummy  // 当前节点

    for l1 != nil || l2 != nil {
        // 如果两个链表长度不相等，在较短的链表上添加一个0节点，使两个链表长度相等
        if l1 == nil {
            l1 = &ListNode{Val: 0, Next: nil}
        }
        if l2 == nil {
            l2 = &ListNode{Val: 0, Next: nil}
        }

        sum := l1.Val + l2.Val + carry
        carry = sum / 10  // 更新进位值
        curr.Next = &ListNode{Val: sum % 10, Next: nil}
        curr = curr.Next

        l1 = l1.Next
        l2 = l2.Next
    }

    // 最后如果还有进位，添加一个进位节点
    if carry > 0 {
        curr.Next = &ListNode{Val: carry, Next: nil}
    }

    return dummy.Next
}

Dalam fungsi ini, kami menggunakan pembolehubah bawa untuk mewakili nilai bawa, dan nilai awal ialah 0. Kami mentakrifkan dummy nod dummy, yang menghala ke kepala senarai terpaut baharu dan curr penuding, yang menghala ke nod semasa senarai terpaut baharu, dengan nilai awal menghala ke nod dummy. Kemudian kita menggunakan gelung for untuk melintasi dua senarai terpaut Pada masa ini, kita perlu ambil perhatian bahawa jika panjang dua senarai terpaut tidak sama, kita perlu menambah nod 0 ke senarai terpaut yang lebih pendek untuk membuat kedua-dua senarai terpaut. senarai terpaut sama panjang. Seterusnya, kami menambah nod pada kedudukan yang sama dalam senarai terpaut, dan menambah nilai bawaan kepada nilai nod semasa untuk mendapatkan nilai jumlah baharu, yang sepuluh digitnya boleh dibawa ke penambahan seterusnya. Oleh itu, kita perlu mengemas kini nilai bawaan. Pada masa yang sama, kami menggunakan digit tunggal jumlah sebagai nilai nod baharu dan menghalakan penuding curr ke nod yang baru dibuat ini. Akhir sekali, kami membiarkan penuding curr menghala ke nod seterusnya senarai terpaut baharu, dan kemudian mengalihkan penunjuk l1 dan l2 ke nod seterusnya. Ulangi proses ini sehingga kedua-dua senarai terpaut telah dilalui. Akhir sekali, jika terdapat pembawa, tambahkan nod pembawa. Akhirnya, dummy.Next dikembalikan, yang mewakili nod kepala senarai terpaut baharu.

Seterusnya kita boleh menentukan fungsi ujian untuk menguji fungsi AddTwoNumbers.

func TestAddTwoNumbers(t *testing.T) {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}
    l3 := AddTwoNumbers(l1, l2)
    if l3.Val != 7 || l3.Next.Val != 0 || l3.Next.Next.Val != 8 || l3.Next.Next.Next != nil {
        t.Errorf("AddTwoNumbers(%v, %v) = %v, want %v", l1, l2, l3, &ListNode{Val: 7, Next: &ListNode{Val: 0, Next: &ListNode{Val: 8, Next: nil}}})
    }
}

Dalam fungsi ujian ini, kami mencipta dua senarai terpaut l1 dan l2, yang mewakili 342 dan 465 masing-masing. Kami memanggil fungsi AddTwoNumbers, mengira jumlahnya dan mendapatkan senarai terpaut baharu l3, yang nilainya hendaklah 708. Kami menggunakan pernyataan if untuk menyemak nilai l3 Jika ia tidak memenuhi jangkaan, kami menggunakan kaedah t.Errorf untuk merekodkan mesej ralat.

Simpan kod di atas dalam fail sumLinkedList.go, jalankan fungsi ujian, dan anda akan mendapat hasil output:

$ go test -v
=== RUN   TestAddTwoNumbers
--- PASS: TestAddTwoNumbers (0.00s)
PASS
ok      sumLinkedList  0.360s

Melalui fungsi ujian, kami boleh mengesahkan bahawa algoritma pelaksanaan penjumlahan senarai terpaut adalah Betul.

Artikel ini memperincikan cara menggunakan golang untuk melaksanakan algoritma penjumlahan senarai terpaut, termasuk mentakrifkan struktur nod senarai terpaut dan langkah khusus untuk melaksanakan fungsi AddTwoNumbers. Algoritma ini ialah soalan yang sering ditemui dalam temu bual Dengan pelaksanaannya sendiri, anda boleh membuat persediaan dengan lebih baik dan juga membantu memperdalam pemahaman anda tentang senarai terpaut dan petunjuk.

Atas ialah kandungan terperinci Cara menggunakan bahasa golang untuk melaksanakan algoritma penjumlahan senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!