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!
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:
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.
Terdapat beberapa cara untuk menyelesaikan masalah ini. Kami akan membincangkan tiga pendekatan:
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"
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"
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!