Cabaran Pengekodan: Libatkan dan Belajar Melalui Penyelesaian Masalah

DDD
Lepaskan: 2024-10-01 12:12:03
asal
416 orang telah melayarinya

Coding Challenges: Engage and Learn Through Problem Solving

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.
Salin selepas log masuk

Kekangan:

  • 1 <= s.panjang <= 1000
  • 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"




<h4>
  
  
  Langkah 4: Laksanakan Pendekatan Kembangkan Sekitar Pusat
</h4>

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

<pre class="brush:php;toolbar:false">def longest_palindrome_expand_center(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

    longest = ""
    for i in range(len(s)):
        # Odd length palindromes
        odd_palindrome = expand_around_center(i, i)
        if len(odd_palindrome) > 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"
Salin selepas log masuk

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"
Salin selepas log masuk

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!

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan