Membedah teknik dua penunjuk

pengenalan.

Walaupun selepas menguasai asas tatasusunan dan senarai, menyelesaikan masalah yang berkaitan dengan struktur data ini kadangkala boleh berasa sukar. Di luar memahami struktur data itu sendiri - bersama dengan operasi dan kerumitan masa dan ruang; memahami pelbagai teknik yang digunakan untuk masalah ini boleh menjadikan proses lebih mudah.
Ini benar terutamanya memandangkan pelbagai jenis masalah yang boleh timbul dengan tatasusunan atau senarai. Dalam catatan blog ini, saya akan menumpukan pada satu teknik sedemikian: teknik dua mata, yang amat berkesan untuk menangani masalah tatasusunan atau senarai.

Dua petunjuk.

Teknik dua penunjuk ialah pendekatan algoritma, terutamanya berkesan untuk menyelesaikan tatasusunan atau jujukan. Ini bermakna pendekatan itu juga boleh digunakan pada rentetan dan senarai terpaut.
Ia melibatkan penggunaan dua penunjuk yang berbeza untuk merentasi struktur data, selalunya membawa kepada penyelesaian yang cekap dengan kerumitan masa yang lebih rendah.

Jenis dua penunjuk.

Penunjuk bergerak ke arah satu sama lain.

Pendekatan ini melibatkan dua penunjuk bermula dari hujung bertentangan struktur data dan bergerak ke arah satu sama lain, bermakna penunjuk bergerak ke arah yang bertentangan. Teknik dua mata jenis ini amat berguna dalam senario di mana anda ingin mencari sepasang elemen yang memenuhi syarat tertentu atau apabila membandingkan elemen dari kedua-dua hujung. Kes penggunaan biasa termasuk menyemak palindrom atau mencari pasangan dengan jumlah tertentu

Pendekatan

1. Mulakan Penunjuk: Mulakan dengan satu penuding pada permulaan (kiri) dan satu lagi di hujung (kanan) struktur data.
2. Alihkan Penunjuk: Laraskan penunjuk ke arah satu sama lain berdasarkan syarat yang diberikan.
3. Semak Syarat: Teruskan gerakkan penunjuk ke arah satu sama lain sehingga hasil yang diingini ditemui atau syarat tertentu dipenuhi

Contoh:Diberi rentetan s, terbalikkan susunan aksara dalam setiap perkataan dalam ayat sambil mengekalkan ruang putih dan susunan perkataan awal.

def reverseWords(s: str) -> str:
    words = s.split()  # Split the input string into words

    for i in range(len(words)):
        left = 0  # Initialize the left pointer
        right = len(words[i]) - 1  # Initialize the right pointer
        split_word = list(words[i])  # Convert the word into a list of characters

        while left < right:  # Continue until the pointers meet in the middle
            # Swap the characters at the left and right pointers
            temp = split_word[left]
            split_word[left] = split_word[right]
            split_word[right] = temp

            left += 1  # Move the left pointer to the right
            right -= 1  # Move the right pointer to the left

        words[i] = "".join(split_word)  # Rejoin the characters into a word

    return " ".join(words)  # Join the reversed words into a final string

Penunjuk bergerak ke arah yang sama.

Dalam pendekatan ini, kedua-dua penunjuk bermula dari hujung struktur data yang sama dan bergerak ke arah yang sama. Teknik ini sering digunakan apabila anda perlu menjejak tetingkap atau sub-tatasusunan dalam tatasusunan, membolehkan anda mengalih dan melaraskan tetingkap dengan cekap berdasarkan syarat-syarat tertentu. Kes penggunaan biasa termasuk teknik tetingkap gelongsor dan menggabungkan tatasusunan diisih.

Pendekatan

1. Mulakan Dua Penunjuk: Mulakan dengan kedua-dua penunjuk pada permulaan struktur data.
2. Alihkan Penunjuk: Gerakkan satu penuding (biasanya yang lebih laju) mendahului yang lain berdasarkan syarat tertentu.
3. Laraskan Penunjuk: Ubah suai kedudukan penunjuk mengikut keperluan untuk mengekalkan keadaan tetingkap yang diingini.

Contoh:Anda diberi dua rentetan perkataan1 dan perkataan2. Cantumkan rentetan dengan menambah huruf dalam susunan berselang-seli, bermula dengan perkataan1. Jika rentetan lebih panjang daripada yang lain, tambahkan huruf tambahan pada hujung rentetan yang digabungkan.

def mergeAlternately(word1: str, word2: str) -> str:
    # Initialize an empty list to store the merged characters
    word_list = []

    # Initialize two pointers, starting at the beginning of each word
    pointer_1 = 0
    pointer_2 = 0

    # Loop until one of the pointers reaches the end of its respective word
    while pointer_1 < len(word1) and pointer_2 < len(word2):
        # Append the character from word1 at pointer_1 to the list
        word_list.append(word1[pointer_1])
        # Append the character from word2 at pointer_2 to the list
        word_list.append(word2[pointer_2])

        # Move both pointers forward by one position
        pointer_1 += 1
        pointer_2 += 1

    # If there are remaining characters in word1, add them to the list
    if pointer_1 < len(word1):
        word_list.append(word1[pointer_1:])

    # If there are remaining characters in word2, add them to the list
    if pointer_2 < len(word2):
        word_list.append(word2[pointer_2:])

    # Join the list of characters into a single string and return it
    return "".join(word_list)

Kesimpulan

Teknik dua mata ialah alat yang serba boleh dan cekap dalam dunia algoritma, terutamanya apabila berurusan dengan tatasusunan, rentetan dan senarai terpaut. Sama ada penunjuk bergerak ke arah satu sama lain atau ke arah yang sama, pendekatan ini boleh memudahkan masalah yang rumit dan meningkatkan prestasi penyelesaian anda. Dengan memahami dan menggunakan strategi ini, anda akan lebih bersedia untuk menangani pelbagai cabaran pengekodan.

Saya menggalakkan anda mempraktikkan teknik ini dengan menyelesaikan pelbagai masalah dan bereksperimen dengan senario yang berbeza. Dengan masa dan pengalaman, anda akan mendapati teknik dua mata sebagai tambahan yang tidak ternilai kepada kit alat penyelesaian masalah anda.

Atas ialah kandungan terperinci Membedah teknik dua penunjuk. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!