leetcode 004-006

这几天疯狂考试，具体的代码思路就不分析了，第四第五题都用自己的方法实现了，只是过程挺惨的。

leetcode 004

代码实现

class Solution:
    
    def delBothArrays(self, lst_nums, del_len):
        """
        :type lst_nums: list[list[int]]
        :type del_len: int
        :rtype: list[int]
        """
        nums1, nums2 = lst_nums
        for t in range(del_len):
            if len(nums1) == 0:
                nums2.pop()
            elif len(nums2) == 0:
                nums1.pop()
            else:
                if nums1[-1] >= nums2[-1]:
                    nums1.pop()
                else:
                    nums2.pop()
    
    def singleLstMedian(self, nums):
        """
        :type nums: List[int]
        :rtype: float
        """
        if len(nums) % 2:
            i = (len(nums)-1) // 2
            return nums[i]
        else:
            i = (len(nums)-2) // 2
            return (nums[i] + nums[i+1]) / 2
    
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        i = len(nums1) - 1
        j = len(nums2) - 1
        if i == -1:
            return self.singleLstMedian(nums2)
        elif j == -1:
            return self.singleLstMedian(nums1)
        if (i + j) % 2:
            del_len = (i + j + 1) // 2
            self.delBothArrays([nums1,nums2], del_len)
            if len(nums1) == 0:
                median = nums2[-1]
            elif len(nums2) == 0:
                median = nums1[-1]
            else:
                median = nums1[-1] if nums1[-1] >= nums2[-1] else nums2[-1]
        else:
            del_len = (i + j) // 2
            self.delBothArrays([nums1,nums2], del_len)
            if len(nums1) == 1:
                lst_new = nums1[-1:] + nums2[-2:]
            elif len(nums2) == 1:
                lst_new = nums1[-2:] + nums2[-1:]
            else:
                lst_new = nums1[-2:] + nums2[-2:]
            lst_new.sort()
            median = (lst_new[-1] + lst_new[-2]) / 2
        return median

其实时间复杂度和答案一样，但是思路好像有点不同。

leetcode 005

代码实现

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0 or len(s) == 1:
            return s
        lst_init = list(s)
        lst_cmp = []
        length = 0
        pos = 1
        is_odd = True
        pop_num = lst_init.pop()
        for i in range(len(s) - 1, 0, -1):
            lst_cmp.append(pop_num)
            offset = 1
            while True:     # 找出偶回文串
                if len(lst_cmp) < offset or len(lst_init) < offset:
                    break
                if lst_cmp[-offset] == lst_init[-offset]:
                    if offset > length:
                        length = offset
                        pos = i
                        is_odd = False
                    offset += 1
                else:
                    break
            pop_num = lst_init.pop()
            offset = 1
            while True:     # 找出奇回文串
                if len(lst_cmp) < offset or len(lst_init) < offset:
                    break
                if lst_cmp[-offset] == lst_init[-offset]:
                    if offset >= length: # 奇大于偶，但会导致不稳定
                        length = offset
                        pos = i
                        is_odd = True
                    offset += 1
                else:
                    break
        if not is_odd:
            right = pos + length
            left = pos - length
        else:
            if length == 0:
                return s[-1]  # 如果不规则，返回最后一个
            right = pos + length
            left = pos - 1 - length
        return s[left:right]

这道题我的解题思路其实是挺清晰的，简而言之就是用两个队列并排比较。代码看起来很复杂，其实时间复杂度为O(n^2)，空间复杂度为O(n)，算是还好。做的时候确实被很多边界卡得很厉害，等以后看看有没有办法简化。

看了下答案，竟然有三四种解法，之后一个个去琢磨。

leetcode 006

代码实现

这道题没有做出来。

class Solution:
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows >= len(s):
            return s

        L = [‘‘] * numRows
        index, step = 0, 1

        for x in s:
            L[index] += x
            if index == 0:
                step = 1
            elif index == numRows -1:
                step = -1
            index += step

        return ‘‘.join(L)

leetcode 004-006

原文：https://www.cnblogs.com/ChanWunsam/p/10230411.html