お腹の肉が気になるko_ya346です。
寝る前の日課なのでleetcodeやります。
findMedianSortedArrays
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
愚直に文字列の左端右端を全探索であぶり出し、逆さにしても同じ文字になるものを探す解法で提出したら時間オーバー。
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]
