leetcode python 2-11

作者: lifesmily | 来源:发表于2017-05-31 22:02 被阅读79次

说明：自己思考以及和别人对比，参考对比程序来源

包含 2 - 11 题

002、单向链表两数相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        current = ListNode(0)
        p = current
        value = 0

        while l1 or l2:

            if l1:
                value = value + l1.val
                l1 = l1.next

            if l2:
                value = value + l2.val
                l2 = l2.next

            # current.var = value % 10
            var = value % 10
            value = value / 10
            current.next = ListNode(var)
            current = current.next

        if value:
            # current.var = value
            current.next = ListNode(value)

        return p.next

if __name__ == '__main__':
    a, a.next, a.next.next = ListNode(2), ListNode(4), ListNode(3)
    b, b.next, b.next.next = ListNode(5), ListNode(6), ListNode(4)
    result = Solution().addTwoNumbers(a, b)
    print "%d -> %d -> %d " %(result.val , result.next.val , result.next.next.val)

这个题主要注意以下问题：要考虑两个链表不同长度的相加；第一个头结点不保留数据，返回p.next；

003、最大不重复的子串

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

以下是自己的答案，用了两个for循环，还是复杂了点,最后一个测试超时

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length_max = 0

        for i in range(0,len(s)):
            mystr , length = self.search(s[i:])
            if length > length_max:
                length_max = length
        return length_max



    def search(self,s):
        i = 0
        while s[i] not in s[0:i]:
            i += 1
            if i == len(s):
                break

        length = i
        mystr = s[0:i]
        #print mystr
        return mystr,length


if __name__ == '__main__' :

    s = Solution()
    length_max1 = s.lengthOfLongestSubstring('abcdefgabc')
    print length_max1

别人的答案 48.5%

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        longest, start, visited = 0, 0, [False for _ in xrange(256)]
        for i, char in enumerate(s):
            if visited[ord(char)]:
                while char != s[start]:
                    visited[ord(s[start])] = False
                    start += 1
                start += 1
            else:
                visited[ord(char)] = True
            longest = max(longest, i - start + 1)
        return longest

if __name__ == "__main__":
    print Solution().lengthOfLongestSubstring("abcabcbb")

004、Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n))

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        result = []
        i = 0
        j = 0
        median, flag = (len(nums1) + len(nums2))//2, (len(nums1) + len(nums2))%2
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                result.append(nums1[i])
                i += 1
            else:
                result.append(nums2[j])
                j += 1
        result += nums1[i:]
        result += nums2[j:]
        if flag == 1:
            return (result[median] + result[median]) * 0.5
        if flag == 0:
            return (result[median - 1] + result[median]) * 0.5


if __name__ == '__main__':
    print Solution().findMedianSortedArrays([1, 3, 5, 7], [2, 4, 6])
    print Solution().findMedianSortedArrays([1, 2], [3,4])

这个题目反应出基础功，由于快速过了一遍数据结构和算法，将两个排好序的序列重新组合这么简单的问题居然会无从下手，而又觉得特别熟悉，其实在归并排序中就有出现，而这边也是完全借用归并排序的思想。其实上述有个明显的缺点就是将整个数组排序了，实际上只需要排序到指定位置即可。

运行时间 108ms 超过了60%

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1, len2 = len(nums1), len(nums2)
        if (len1 + len2) % 2 == 1: 
            return self.getKth(nums1, nums2, (len1 + len2)/2 + 1)
        else:
            return (self.getKth(nums1, nums2, (len1 + len2)/2) + \
                    self.getKth(nums1, nums2, (len1 + len2)/2 + 1)) * 0.5

    def getKth(self, A, B, k):
        m, n = len(A), len(B)
        if m > n:
            return self.getKth(B, A, k)

        left, right = 0, m    
        while left < right:
            mid = left + (right - left) / 2
            if 0 <= k - 1 - mid < n and A[mid] >= B[k - 1 - mid]:
                right = mid
            else:
                left = mid + 1

        Ai_minus_1 = A[left - 1] if left - 1 >= 0 else float("-inf")
        Bj = B[k - 1 - left] if k - 1 - left >= 0 else float("-inf")

        return max(Ai_minus_1, Bj)

上述为别人的思路，运行时间95ms。

005 Longest Palindromic Substring 最大回文字符串

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        maxlen, maxL, maxR = 0, 0, 0
        for i in range(length):
            start = i    #考虑为偶数情况
            end = i + 1
            while start >= 0 and end <= length - 1:
                if s[start] == s[end]:
                    if end - start + 1 > maxlen:
                        maxlen = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
            start = i - 1   #考虑为奇数情况
            end = i + 1
            while start >= 0 and end <= length - 1:
                if s[start] == s[end]:
                    if end - start + 1 > maxlen:
                        maxlen = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
        return s[maxL:maxR+1]
        
if __name__ == '__main__':
    solution = Solution()
    print solution.longestPalindrome('abbacd')

上面的程序运行效率不是很高，只优于41%的提交。
是否能把所有的情况全部转换为奇数处理？Manacher算法，且这个算法求最长回文子串的时间复杂度是线性O(N)的。参考

def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def preProcess(s):
            if not s:
                return ['^', '$']
            T = ['^']
            for c in s:
                T +=  ['#', c]
            T += ['#', '$']
            return T

        T = preProcess(s)
        P = [0] * len(T) 
        center, right = 0, 0
        for i in xrange(1, len(T) - 1):
            i_mirror = 2 * center - i
            if right > i:
                P[i] = min(right - i, P[i_mirror])
            else:
                P[i] = 0

            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1

            if i + P[i] > right:
                center, right = i, i + P[i]       
        
        max_i = 0
        for i in xrange(1, len(T) - 1):
            if P[i] > P[max_i]:
                max_i = i
        start = (max_i - 1 - P[max_i]) / 2
        return s[start : start + P[max_i]]

6、 ZigZag Conversion

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1:
            return s
        str1 = ''
        j, flag = 0, 0
        T = ['' for i in range(numRows)]

        for i in range(len(s)):
            if flag == 0:
                T[j] += s[i]
                j += 1
                if j == numRows:
                    flag = 1
                    j -= 2
            else:
                #p[i] = j
                T[j] += s[i]
                j -= 1
                if j == -1:
                    flag = 0
                    j += 2

        for i in range(numRows):
            str1 += T[i]
        return str1

if __name__ == '__main__':
    solution = Solution()
    print solution.convert('abc',2)

上述算法思路主要是：0123432101234321。
运行结果出来一瞬间真是崩了，216ms，只胜于10%，可能原因一是算法确实没别人好，二是字符串操作可能会带来开销。

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1:
            return s
        step, zigzag = 2 * numRows - 2, ""
        for i in xrange(numRows):
            for j in xrange(i, len(s), step):
                zigzag += s[j]
                if 0 < i < numRows - 1 and j + step - 2 * i < len(s):
                    zigzag += s[j + step - 2 * i]
        return zigzag

if __name__ == "__main__":
    print Solution().convert("PAYPALISHIRING", 3)

该算法优于40%，还是不够好

7、Reverse digits of an integer

Example1: x = 123, return 321
Example2: x = -123, return -321

这个问题需要注意的有两个问题，一是可能是负数，二是考虑是否越界，假设为有符号32bit。
反转一般有两种常用解决方式，一是以整数方式，除10取余，二是利用字符串自带的反转功能，str1[::-1]。

class Solution(object):
    def reverse(self, x):  #该方法更优
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -self.reverse(-x)

        result = 0
        while x:
            result = result * 10 + x % 10
            x /= 10
        return result if result <= 0x7fffffff else 0  # Handle overflow.

    def reverse2(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            x = int(str(x)[::-1][-1] + str(x)[::-1][:-1])
        else:
            x = int(str(x)[::-1])
        x = 0 if abs(x) > 0x7FFFFFFF else x
        return x

    def reverse3(self, x):
        """
        :type x: int
        :rtype: int
        """
        s = cmp(x, 0)
        r = int(`s * x`[::-1])
        return s * r * (r < 2 ** 31)

字符串反转有以下两种常用方法：

使用[::-1]：
s = 'python'
print s[::-1]
使用reverse()方法：
l = list(s)
l.reverse() #不返回，但是原列表已经反转
print ''.join(l)

8、String to Integer (atoi)

这个题确实有很多细节需要考虑，一开始做的时候只考虑了字符串中间有字母，以及首位可能为'-'，发现还有可能首位为‘+’和一个或多个空格。该题还有一个特殊就是'12a'也能出结果12，就是是逐个判断

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        result, flag = 0, 1
        if len(str) == 0:
            return 0
        if len(str) == 1 and str not in '0123456789':
            return 0
        if str[0] == ' ':
            return self.myAtoi(str[1:])
        
        for i in range(0,len(str)):
            if i == 0 and str[i] not in '-+0123456789':
                return 0
            if i>0 and str[i] not in '0123456789':
                return 0
        
        for c in str:            
            if c == '-':
                flag = -1
                continue
            if c == '+':
                continue
            num = ord(c) - ord('0')
            result = result*10 + num
            
        return result*flag

以上是初步代码，还有很多需要改善，逻辑关系没有划分很清楚，没有考虑到越界，递归调用看似简便但开销大，使用两个循环，略显臃肿。

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        result, i, flag = 0, 0, 1
        if len(str) == 0:
            return 0
        while str[i] == ' ':
            i += 1
        if str[i] == '-':
            flag = -1
            i += 1
        elif str[i] == '+':
            i += 1
        
        while i<len(str) and str[i] >= '0' and str[i] <= '9':
            result = result*10 + ord(str[i]) - ord('0')
            i += 1
            if result > 2147483647:
                break
        
        result *= flag
        if result >= 2147483647:
            return 2147483647
        if result <= -2147483648:
            return -2147483648
        
        return result
        
if __name__ == '__main__':
    solution = Solution()
    print solution.myAtoi('1')

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
            
        l = len(str(x)) - 1
        while l > 0:
            if x % 10 != x // 10**l:
                return False
            x = x // 10
            l -= 1
            x = x % 10**l
            l -= 1
            
        return True
        
if __name__ == '__main__':
    solution = Solution()
    print solution.isPalindrome(12313214)

算比较简单，第一次提交 81% ，第二次就 69% 第三次 21% 。也是很惶恐，本来开开心心。
赶紧找来别人的看看

class Solution:
    # @return a boolean
    def isPalindrome(self, x):
        if x < 0:
            return False
        copy, reverse = x, 0
        
        while copy:
            reverse *= 10
            reverse += copy % 10
            copy /= 10
        
        return x == reverse

if __name__ == "__main__":
    print Solution().isPalindrome(12321)
    print Solution().isPalindrome(12320)
    print Solution().isPalindrome(-12321)

這个看起来更优化点，一测试 30%，已经不知道说啥。

10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

http://www.cnblogs.com/zuoyuan/p/3781773.html
最后一个‘*’一定不要下意识认为是正则表达式中匹配0或任意个字符，這里是匹配前面出现的字符，可以是不匹配（及匹配0次也可以重复）

class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        if len(p)==0: return len(s)==0
        if len(p)==1 or p[1]!='*':
            if len(s)==0 or (s[0]!=p[0] and p[0]!='.'):
                return False
            return self.isMatch(s[1:],p[1:])
   
        else:
            i=-1; length=len(s)
            while i<length and (i<0 or p[0]=='.' or p[0]==s[i]):
                if self.isMatch(s[i+1:],p[2:]): return True
                i+=1
            return False

算法题理清思路很重要：

isMatch(s, p):

1. 当前p为0时，若s也是0时，则返回true，否则为false
2. 当前p不为0时，
　　1) p的下一个不是'*'时
　　　　if: 当前s与p匹配，
　　　　　　则表明到此都是匹配的，只需要检查isMatch(s + 1, p + 1)
　　　　else:
　　　　　　返回false
　　2) p的下一个是'*'时，
　　　　while: 当前s与p匹配，即表明至此也是匹配的
　　　　　　if: 当前s与下一个p也都匹配，即isMatch(s, p + 2)，则返回true
　　　　　　else: s++
　　　　此时，当前s与当前p已经不匹配了（之前s都是匹配的），则检测下一个模板isMatch(s, p + 2)

上面是用递归方法，也有人说用动态规划比较好，待思考。http://www.cnblogs.com/flowerkzj/p/3726667.html

11、Container With Most Water

给定n个数，a1,a2,...,an.在坐标上的位置为（i,ai）,求其中两个点到X轴的线段与x轴围成的面积最大。

思路：
1、暴力法：用两个for循环，超时了，看来还是得动脑子。
2、贪心法，从两边向中间夹逼，两个指针指向列表两端，当左边高度＜右边时，制约在左边，右边往左移肯定找不到更大的，应该左边往右移，反之也成立。
但注意到，每次都会比较一次，但是当右移或左移的数比原来小时，没有必要进行计算，因为肯定会比原来结果小，如何优化代码。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height) 
        if length < 2:
            return -1
        
        left = 0
        right = length - 1
        max_contain = 0
        while left < right:
            max_contain = max(max_contain, min(height[left] , height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1                                     
        return max_contain
                    
            
if __name__ == '__main__':
    solution = Solution()
    print solution.maxArea([1,3,56,57,8])

优化后，击败92%，欣慰。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height) 
        if length < 2:
            return -1
        
        left = 0
        right = length - 1
        max_contain = 0
        while left < right:
            max_contain = max(max_contain, min(height[left] , height[right]) * (right - left))
            if height[left] < height[right]:
                j = left
                left += 1
                
                while height[left] <= height[j] and left < right: #若＜原来的数，直接下一个，算都不用算
                    left += 1
            else:
                j = right
                right -= 1
                
                while height[right] <= height[j] and left < right:
                    right -= 1                                       
        return max_contain                               
if __name__ == '__main__':
    solution = Solution()
    print solution.maxArea([1,2])