それでは毛玉諸君、これにて失敬

日々の精進を備忘録的に綴ります。

leetcode日記4

お腹の肉が気になるko_ya346です。
寝る前の日課なのでleetcodeやります。

findMedianSortedArrays

Loading...

nums1とnums2を結合してソートして真ん中の値取って終わり!

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        print(nums1, nums2)
        merged_list = []
        merged_list.extend(nums1)
        merged_list.extend(nums2)
        merged_list = sorted(merged_list)
        len_merged_list = len(merged_list)
        half_index = len_merged_list // 2
        if len_merged_list % 2:
            return merged_list[half_index]
        else:
            return sum(merged_list[half_index - 1: half_index + 1]) / 2

longestPalindrome

Loading...

愚直に文字列の左端右端を全探索であぶり出し、逆さにしても同じ文字になるものを探す解法で提出したら時間オーバー。
Expand Around Centerという方法で解きました。
回文は必ず左右対称になるので、中心位置を決めてその両側を1つずつ調べるという手法です。
文字数が偶数の場合、中心の文字が存在しないので、場合わけが面倒なので文字の間に適当なブランク文字を挟み、必ず中心に文字が存在するように前処理をしました。
答えを返すときは、ブランク文字を消すのを忘れずに。
あと、inputに含まれる可能性のある文字を使わないようにしましょう(0を入れてて無事死亡しました)。

class Solution:

    # 計算時間オーバー
#     def longestPalindrome(self, s: str) -> str:
#         ans = ""
#         for i in range(len(s)):
#             for j in range(i + 1, len(s) + 1):
#                 tmp_s = s[i: j]
#                 if tmp_s == tmp_s[::-1] and len(tmp_s) > len(ans):
#                     ans = tmp_s
#         return ans
    
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        
        s0 = ""
        for ss in s:
            s0 += ss
            s0 += "#"
        s0 = s0[:-1]
        print(s0)
        
        ans = ""
        for i in range(len(s0)):
            print(i)
            # iを中心として回文判定
            pal_s = self.get_palindromic(s0, i).replace("#", "")
            
            if len(ans) < len(pal_s):
                ans = pal_s

        return ans

    def get_palindromic(self, s, mid):
        low = mid
        high = mid
        while True:
            if low - 1 < 0 or high + 1 >= len(s):
                break
            if s[low - 1] != s[high + 1]:
                break
            low -= 1
            high += 1
        print(low, high)
        print(s[low: high + 1])
        return s[low: high + 1]