4. 寻找两个正序数组的中位数
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
num = nums1 + nums2
# print(type(num))
num.sort()
num_len = len(num)
if num_len % 2 == 0:
return (float(num[(num_len//2) - 1] + num[(num_len//2)])/2)
else:
return num[num_len//2]
if __name__ == '__main__':
ret = Solution()
num1 = [1, 2]
num2 = [3, 4]
print(ret.findMedianSortedArrays(num1, num2))
难点以及解决方法:
暂无。
我直接把两个数组拼接在一起了,然后进行了排序,直接进行了输出。
5. 最长回文子串
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
len_s = len(s)
answer = ""
temp = ""
single_letter = ""
max_len = 0
type_right = 1
if len(s) == 1:
return s
for i in range(len_s):
for j in range(len_s-1, i, -1):
type_right = 1
if s[j] == s[i]:
temp = ""
temp = s[i: j+1]
if len(temp) > max_len:
tmp_i = i
tmp_j = j
while 1:
if s[tmp_i] != s[tmp_j]:
type_right = 0
break
tmp_i+=1
tmp_j-=1
if tmp_i >= tmp_j:
break
if type_right == 1:
answer = temp
max_len = len(temp)
break
else:
if j == i + 1:
single_letter += s[i]
if max_len == 0:
max_len = 1
temp = ""
if max_len == 1:
answer = single_letter[0]
return answer
if __name__ == '__main__':
ret = Solution()
print(ret.longestPalindrome("ac"))
难点以及解决方法:
我的基本思路是从两边往中间匹配,先找到2个一样的字符,找到一样的字符之后再判断两个相同字符中间的字符串是否为回文字符串,示意图如下:
回文字符串的判断方法如下:
temp = s[i: j+1]
if len(temp) > max_len:
tmp_i = i
tmp_j = j
while 1:
if s[tmp_i] != s[tmp_j]:
type_right = 0
break
tmp_i+=1
tmp_j-=1
if tmp_i >= tmp_j:
break
回文字符串的判断方法也是从两边往中间判断是否有相同的字符。
还有一种特殊情况:“abcdefg”这种不存在回文字符串的,应该输出的结果是’a’,但这种是特殊情况,因此我需要特殊处理,我的处理思路如下。
因为上述字符串没有回文字符串,所以回文字符串的长度的最大值应该就是0,这种情况只有这时候才会出现,因此为了解决这种问题,我会在从两边往中间遍历的时候记录下每次起点的字符,记作single_letter
,如果当主体函数完成之后回文字符串的长度的最大值还是0的话直接输出single_letter[0]
。
评论(0)
您还未登录,请登录后发表或查看评论