LeetCode刷題自己寫的Python3代碼答案(1-10)

筆者也是菜鳥一枚,僅要求把題目做出,對算法的優化沒有能力做太多處理,希望大家給出改進意見.

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

class Solution:
    def twoSum(self, nums, target):
        for idx, a in enumerate(nums):
            for idx2 in range(idx+1,len(nums)):
                 if a + nums[idx2] == target :
                    return [idx,idx2]
           

Runtime: 4916 ms, faster than 21.56% of Python3 online submissions for Two Sum.

Memory Usage: 13.5 MB, less than 51.57% of Python3 online submissions for Two Sum

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters

class Solution:
    def lengthOfLongestSubstring(self, s):
        maxnum = 0
        for i in range(len(s)):
            ss = []
            for j in range(i,len(s)):
                if (s[j] not in ss):
                    ss.append(s[j])
                    if (len(ss))>maxnum : 
                        maxnum = len(ss)
                else:
                    break
        return maxnum
           

這個結果不是很好…

Runtime: 1884 ms, faster than 5.01% of Python3 online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 13.5 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.

4. 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)).

You may assume nums1 and nums2 cannot be both empty.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums = nums1 + nums2
        nums.sort()
        a = len(nums)
        if a % 2 == 1 : return nums[int(a/2)]
        else : return 0.5*(nums[int(a/2)] + nums[int(a/2)-1])
           

Runtime: 56 ms, faster than 100.00% of Python3 online submissions for Median of Two Sorted Arrays.

Memory Usage: 13.6 MB, less than 5.11% of Python3 online submissions for Median of Two Sorted Arrays.

5.Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

class Solution:
    def longestPalindrome(self, s):
      if len(s) == 0 : return ""
      else:
        for j in range(len(s)):
            num = len(s)-j
            for i in range(j+1):
                if s[i] == s[i+num-1]:
                    if s[i+1:i+num-1] == s[i+num-2:i:-1]:
                        return(s[i:i+num])

           

Runtime: 1324 ms, faster than 50.74% of Python3 online submissions for Longest Palindromic Substring.

Memory Usage: 13.2 MB, less than 25.10% of Python3 online submissions for Longest Palindromic Substring.

6.ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N

A P L S I I G

Y I R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

class Solution:
    def convert(self, s,numRows):
      if numRows==1: return s
      myresult = ''
      a = lambda x : s[x] if 0<=x and x<len(s) else ''
      result = ['']*numRows
      for i in range(0,len(s)+2*(numRows-1),2*(numRows-1)):
        result[0] = result[0] + a(i)
        for num in range(1,numRows):
            if num < numRows-1:
                result[num] = result[num] + a(i-num) + a(i+num) 
            else :
                result[num] = result[num] + a(i+num) 
      for i in range(numRows):
            myresult += result[i]
      return myresult
           

Runtime: 108 ms, faster than 34.63% of Python3 online submissions for ZigZag Conversion.

Memory Usage: 13.3 MB, less than 10.35% of Python3 online submissions for ZigZag Conversion.

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

這裡注意32-bit signed integer的範圍.

class Solution:
    def reverse(self, x):
        if (x<-2147483648) or (x > 2147483647): return 0
        sign = 1
        result = 0 
        if x<0:
            x = -x
            sign = -1
        while x != 0:
            result = result*10 + (x%10)
            x = int(x/10)
        if (result<-2147483648) or (result > 2147483647): return 0
        else : return sign*result
            
           

Runtime: 40 ms, faster than 99.98% of Python3 online submissions for Reverse Integer.

Memory Usage: 13.2 MB, less than 5.71% of Python3 online submissions for Reverse Integer.

8.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ’ ’ is considered as whitespace character.

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

class Solution:
    def myAtoi(self, mystr):
        mystr = mystr.lstrip() #去掉頭上的空格
        if mystr == '': return 0
        sign = 1
        result = 0
        i = 0
        if mystr[i] == '-':
            sign = -1
            i = i + 1
        elif mystr[i] == '+': i = i + 1 
        if i < len(mystr):
          while((mystr[i]<='9') & (mystr[i]>='0')):
            result = 10*(result) + int(mystr[i])
            i +=1
            if i == len(mystr): break
        result *= sign
        if result>2**31-1: return 2**31-1
        elif result<-2**31: return -2**31
        else: return result
           

Runtime: 44 ms, faster than 99.93% of Python3 online submissions for String to Integer (atoi).

Memory Usage: 13.4 MB, less than 5.00% of Python3 online submissions for String to Integer (atoi).

9.

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

class Solution:
    def isPalindrome(y,x):
        if x < 0 : 
          return False
        elif x == 0 :
          return True
        else:
          num = []
          while(x!=0):
             num.append(x % 10)
             x= int(x/10)
          for i in range(int(len(num)/2)+1):
            if num[i] != num[len(num)-1-i]:
                return False
          return True
           

Runtime: 140 ms, faster than 85.74% of Python3 online submissions for Palindrome Number.

Memory Usage: 13.3 MB, less than 5.03% of Python3 online submissions for Palindrome Number.

10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

這道題very hard for me,做了20個小時…還是太菜了.選了多條思路去做，最後從前往後比對，隻考慮前2個字元，當出現*和.時考慮所有可以替換的情形，逐一比對，然後遞歸。

class Solution:
    def myreplace(self,s,p):
        if p[0]=='.' and len(p)==1:
            return [s[0]]
        if p[0]=='.' and len(p) > 1 and p[1]!='*':
            return [s[0]+p[1:]]
        if p[1]=='*' and p[0]!='.':
            if p[0]!=s[0]:
                return [p[2:]] if len(p)>2 else ['']
            else:
                num = 1
                while num<len(s) and s[num]==s[0]:
                    num += 1
                return [s[0]*i+p[2:] for i in range(num+1)] if len(p)>2 else [s[0]*i for i in range(num+1)]
        if p[1]=='*' and p[0]=='.':
            if len(p)==2: return '+' #means we get True
            else:
                #print(len(s))
                return [s[:j]+p[2:] for j in range(len(s)+1)]
    def isMatch(self, s: str, p: str):
        p_index = 0
        s_index = 0
        Flag =  True
        if len(p[p_index:])>3:
            if p[p_index]==p[p_index+2] and p[p_index+1]=='*' and p[p_index+3]=='*':
                return self.isMatch(s[s_index:],p[p_index+2:])
        if len(s)==0:
            #print
            if len(p) == 0: return True
            if len(p) == 1: return False
            if  p[1]=='*' : return self.isMatch(s,p[2:])
            else: return False
        elif len(p)==0: return False
        if p[0]!='.' and len(p)==1:
            if p[0]==s[0] and len(s)==1: return True
            else: return False
        elif p[0]!='.' and p[1]!='*':
            if p[0]==s[0]:
                if len(p)==0 and len(s)==0: return True
                elif len(p)==0 and len(s)!=0: return False
                elif len(p)!=0 and len(s)==0: return self.isMatch('',p[1:])
                else:
                    return self.isMatch(s[1:],p[1:])
            if p[0]!=s[0]:
                return False
        else:
            if self.myreplace(s,p) == '+':return True
            if True in(self.isMatch(s,replaced) for replaced in self.myreplace(s,p)): return True
            else: return False
####測試程式
# Mysoulution = Solution()
# print(Mysoulution.isMatch("aa","a")==False)
# print(Mysoulution.isMatch("aa","a*")==True)
# print(Mysoulution.isMatch("b",".*")==True)
# print(Mysoulution.isMatch("aab","a*b")==True)
# print(Mysoulution.isMatch("aab","c*a*b")==True)
# print(Mysoulution.isMatch("mississippi","mis*is*p*.")==False)
# print(Mysoulution.isMatch("a",".*.")==True)
# print(Mysoulution.isMatch("",".*")==True)
# print(Mysoulution.isMatch("","a*")==True)
# print(Mysoulution.isMatch("","")==True)
# print(Mysoulution.isMatch("ab",".*c")==False)
# print(Mysoulution.isMatch("aaaaaaaaaaaaab","a*a*a*a*a*a*a*a*a*a*c")==False)
# print(Mysoulution.isMatch("aaab","a*c")==False)
# print(Mysoulution.isMatch("aaaaaaaaaaaaab","a*c")==False)
# print(Mysoulution.isMatch("","c*c*")==True)
# print(Mysoulution.isMatch("a",".*a*")==True)
# print(Mysoulution.isMatch("aaa","aaaa")==False)
# print(Mysoulution.isMatch("cbaacacaaccbaabcb","c*b*b*.*ac*.*bc*a*")==True)
# print(Mysoulution.isMatch("caccccaccbabbcb","c*c*b*a*.*c*.a*a*a*")==True)
           

Runtime: 216 ms, faster than 26.22% of Python3 online submissions for Regular Expression Matching.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Regular Expression Matching.