Cabaran Pengekodan: Libatkan dan Belajar Melalui Penyelesaian Masalah

Cabaran Pengekodan: Libatkan dan Belajar Melalui Penyelesaian Masalah

Cabaran pengekodan ialah cara yang hebat untuk meningkatkan kemahiran pengaturcaraan anda, melibatkan diri dengan komuniti dan mempelajari teknik baharu. Dalam catatan blog ini, kami akan membentangkan cabaran pengekodan, membincangkan pelbagai pendekatan untuk menyelesaikannya dan menjemput pembaca untuk berkongsi penyelesaian mereka dalam ulasan. Jom terjun!

Cabaran: Cari Subrentetan Palindromik Terpanjang

Masalah:
Diberi rentetan s, cari subrentetan palindromik terpanjang dalam s. Palindrom ialah rentetan yang membaca sama ke belakang dengan ke hadapan.

Contoh:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Kekangan:

• 1
• s hanya terdiri daripada digit dan huruf Inggeris.

Sila kongsi Penyelesaian anda dengan pendekatan kreatif menggunakan bahasa pengaturcaraan yang berbeza.

Panduan Langkah demi Langkah untuk Menyelesaikan Cabaran

Langkah 1: Fahami Masalah

Sebelum memasuki kod, pastikan anda memahami masalahnya. Subrentetan palindromik ialah jujukan aksara yang dibaca sama ke belakang dengan ke hadapan. Matlamat kami adalah untuk mencari subrentetan yang terpanjang dalam rentetan s yang diberikan.

Langkah 2: Rancang Pendekatan Anda

Terdapat beberapa cara untuk menyelesaikan masalah ini. Kami akan membincangkan tiga pendekatan:

1. Brute Force
2. Kembangkan Sekitar Pusat
3. Pengaturcaraan Dinamik

Langkah 3: Laksanakan Pendekatan Brute Force

Pendekatan kekerasan melibatkan pemeriksaan semua subrentetan yang mungkin dan menentukan sama ada ia adalah palindrom. Kaedah ini mudah tetapi tidak cekap untuk rentetan besar.

def longest_palindrome_brute_force(s):
    def is_palindrome(sub):
        return sub == sub[::-1]

    n = len(s)
    longest = ""
    for i in range(n):
        for j in range(i, n):
            if is_palindrome(s[i:j+1]) and len(s[i:j+1]) > len(longest):
                longest = s[i:j+1]
    return longest


print(longest_palindrome_brute_force("babad"))  # Output: "bab" or "aba"

Langkah 4: Laksanakan Pendekatan Kembangkan Sekitar Pusat

Pendekatan ini melibatkan pengembangan di sekeliling setiap aksara (dan antara aksara) untuk mencari palindrom terpanjang. Ia lebih cekap daripada kekerasan.

def longest_palindrome_expand_center(s):
    def expand_around_center(left, right):
        while left >= 0 and right  len(longest):
            longest = odd_palindrome
        # Even length palindromes
        even_palindrome = expand_around_center(i, i+1)
        if len(even_palindrome) > len(longest):
            longest = even_palindrome
    return longest


print(longest_palindrome_expand_center("babad"))  # Output: "bab" or "aba"

Langkah 5: Laksanakan Pendekatan Pengaturcaraan Dinamik

Pendekatan pengaturcaraan dinamik menggunakan jadual untuk menyimpan sama ada subrentetan ialah palindrom, yang membawa kepada penyelesaian yang cekap.

def longest_palindrome_dp(s):
    n = len(s)
    if n == 0:
        return ""
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

    for i in range(n):
        dp[i][i] = True

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > max_length:
                        start = i
                        max_length = length

    return s[start:start+max_length]


print(longest_palindrome_dp("babad"))  # Output: "bab" or "aba"

Cuba mengoptimumkan algoritma.

Atas ialah kandungan terperinci Cabaran Pengekodan: Libatkan dan Belajar Melalui Penyelesaian Masalah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!