Leetcode刷题python-python黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

听爸爸的话

1124

文章

934786

访问

+关注

分类

暂无分类

日期归档

2024-11(1)

Leetcode刷题python

发布于2019-08-05 18:28 阅读(834) 评论(0) 点赞(1) 收藏(2)

知识预热：
python内置类型的时间复杂度
 单向链表
 python数据结构内置方法的时间复杂度

Two Sum
两数==target
方法二更好
题1，对时间复杂度有要求O(n)，所以维护一个字典，遍历过的数值放在字典中，直接遍历时候查找字典中有没有出现差，查找字典时间复杂度是O(1)，所以O(n)*O(1) = O(n)，满足要求。

nums = [0, 1, 2, 7, 11, 15]
target = 9

def chek(nums, target):
    dict1 = {}
    for i, ele in enumerate(nums):
        if (target-ele) in dict1:
            return dict1[target-ele], i
        else:
            dict1[ele] = i

print(chek(nums, target))

下面方法和上面方法一样，但是内存稍稍省下0.1M

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for i in range(len(nums)):
            if dict.get(target-nums[i]) == None:
                dict[nums[i]] = i
            else:
                return dict[target-nums[i]], i

方法二，不用维护一个字典的开销

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            if (target-nums[i]) in nums[i+1:]:
            	# 这里返回加i+1是因为nums[i+1:]计数又是从0开始了
                return i, nums[i+1:].index(target-nums[i])+i+1

感觉方法二的if ele in list的时间复杂度就是O(n),所以不对，这道题应该是需要维护哈希表。
2. Add Two Numbers
题2，Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

# 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
        """
        cur = l1
        sum = 0
        idx = 0
        while cur:
            sum += cur.val*(10**idx)
            cur = cur.next
            idx += 1
        
        cur = l2
        idx = 0
        while cur:
            sum += cur.val*(10**idx)
            cur = cur.next
            idx += 1
        
        if sum == 0:
            return ListNode(0)
        else:
            self.head = ListNode(sum%10)
            cur = self.head
            sum //= 10
            while sum > 0:
                cur.next = ListNode(sum%10)
                cur = cur.next
                sum //= 10
            return self.head

Longest Substring Without Repeating Characters
题3，

#基本思路是维护left和right两个指针，max_num，
#一个集合，先移动右指针，不在集合中则加入集合里，
#否则移动左指针，并右指针=左指针。
#用集合是因为集合的查询速度是o(1)!!

class Solution(object):
   def lengthOfLongestSubstring(self, s):
       """
       :type s: str
       :rtype: int
       """
       l = r = 0; set1= set()
       max = 0
       while r < len(s) and r < len(s):
           if not s[r] in set1:
               set1.add(s[r])
               r += 1
               if max < len(set1):
                   max = len(set1)
           else:
               l += 1
               r = l
               set1 = set()
       return max

Median of Two Sorted Arrays
题4， The overall run time complexity should be O(log (m+n))我并没有注意到这句话，但是结果竟然通过了。我自算的时间复杂度应该是 O( (m+n)log(m+n) )+ O(m).

class Solution:
   def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
       nums1.extend(nums2)
       nums1.sort()
       if not len(nums1)%2:
           n = len(nums1)//2
           return (nums1[n-1]+nums1[n])/2
       else:
           return nums1[len(nums1)//2]

Longest Palindromic Substring
用的是马拉车算法，原理链接

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        b = "$#"
        for i in s:
            b += i
            b += "#"
        maxr = 0;idx = -1
        for i in range(3,len(b)):
            r = 1
            while (i+r)<len(b) and (i-r)>=0:
                if b[i-r] == b[i+r]:
                    r += 1
                else:
                    break
            (maxr,idx) = (r,i) if maxr<=r else (maxr,idx)
            # 起点, 最大长度
            # (idx-maxr)//2, axr-1
        return s[(idx-maxr)//2: (idx-maxr)//2 + maxr-1]

ZigZag Conversion
我用的方法时间超出限制，我分别考虑了头、中、尾三种情况，需要改进算法。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        a = ""
        gap = (numRows-2)*2+2
        for i in range(numRows):
            # 头情况
            if i == 0:
                n = 0
                while n*gap < len(s):
                    a += s[n*gap]
                    n += 1

            # 中间的情况
            if i>0 and i<numRows-1:
                n = 1
                a += s[i]
                while n*gap+i < len(s) or n*gap-i < len(s):
                    if n*gap-i < len(s):
                        a += s[n*gap-i]
                    if n*gap+i < len(s):
                        a += s[n*gap+i]
                    n += 1

            # 尾情况
            if i == numRows-1:
                bg = numRows-1
                n = 0
                while n*gap+bg < len(s):
                    a += s[n*gap+bg]
                    n += 1
        return a

上面方法耗时超限制，改进思路，按照遍历放入的思想来实现。代码，核心思想是控制向下走或者向上走，然后放入对应的行。

s = "PAYPALISHIRING"

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        s1 = [''] * numRows
        dir = 1
        countn = 0
        for i in range(len(s)):
            if countn == 0:
                s1[countn] += s[i]
                dir = 1
                countn += dir

            elif countn == numRows-1:
                s1[countn] += s[i]
                dir = -1
                countn += dir

            else:
                s1[countn] += s[i]
                countn += dir
        return "".join(s1)


solu = Solution()
s1 = solu.convert(s, 3)
print(s)
print(s1)

改进后通过，内存消耗控制很好。运行速度到112ms。
更近一步：
思考用列表[] .append()的方法可能会提高计算速度，

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        s1 = []
        for i in range(numRows):
            s1.append([])
        dir = 1
        countn = 0
        for i in range(len(s)):
            if countn == 0:
                s1[countn].append(s[i])
                dir = 1
                countn += dir

            elif countn == numRows-1:
                s1[countn].append(s[i])
                dir = -1
                countn += dir

            else:
                s1[countn].append(s[i])
                countn += dir
        return "".join(j for i in s1 for j in i)

结论：果然[].append(“str_”)的效率比“”+str_效率高，列表扩展效率比字符串扩展效率高。运行耗时提高到100ms
下面在上面代码基础上进行精简，减少一点内存消耗。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        s1 = []
        for i in range(numRows):
            s1.append([])
        dir = 1
        countn = 0
        for i in range(len(s)):
            s1[countn].append(s[i])
            countn += dir
            if countn == 0:
                dir = 1
            if countn == numRows-1:
                dir = -1
        return "".join(j for i in s1 for j in i)

整数反转

class Solution:
    def reverse(self, x: int) -> int:
        x = int(str(x)[::-1]) if x>=0 else -int(str(x)[1:][::-1])
        if x>-2**31 and x<(2**31)-1:
            return x
        else:
            return 0

字符串转换整数 (atoi)

#这道题应该仔细看看题目要求，实现并不难，坑很多。
#还是正则表达式来的最痛快，规则实现需要考虑的细节太多。
#代码不是我的思路，[来自](https://blog.csdn.net/coder_orz/article/details/52053932)
class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        try:
            res = re.search('(^[\+\-]?\d+)', str).group()
            res = int(res)
            res = res if res <= 2147483647 else 2147483647
            res = res if res >= -2147483648 else -2147483648
        except:
            res = 0
        return res

正则表达式忘了不少了，拾起来。
9. 回文数
这道题进阶版本是不用str，可提速。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return x>=0 and str(x) == str(x)[::-1]

进阶版本如下，思想是把数字倒过来。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0:return False
        elif x == 0:return True
        else:
            temp = 0
            t_x = x
            while x>0:
                temp = 10*temp + x%10
                x //= 10
            return temp == t_x

虽然内存没省，但运算速度提升了。

Regular Expression Matching
这道题属于困难，用正则模块可以实现，但是这不是本题考察目的。

class Solution:
    def isMatch(self, s, p):
        if not s:return False
        res = re.match(p, s)
        if res == None:
            return False
        else:
            return res.group() == s

预留地
找到了思路  https://www.cnblogs.com/Jessey-Ge/p/10993447.html

Container With Most Water
左右两个游标来寻找最大的体积。哪个游标高度小就移动哪个。时间复杂度O(n)

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0; r = len(height)-1
        max_vol = 0
        while l < r:
            v= min(height[r], height[l])*(r-l)
            max_vol = v if max_vol<v else max_vol
            if height[r] >= height[l]:
                l += 1
            else:
                r -= 1
        return max_vol

Integer to Roman
这道题的思想，列出罗马数字和数字的所有对应字典，搞清对应关系，做减法。是人生吗。
解法
#python2中有错误，但是python3却可以通过。

class Solution(object):
   def intToRoman(self, num):
       """
       :type num: int
       :rtype: str
       """

       dic  = { "M":1000, "CM":900, "D":500, "CD":400, "C":100, "XC":90, "L":50,"XL":40, "X":10, "IX":9, "V":5,"IV":4 ,"I":1         }
       ele = ""
       for key,item in dic.items():
           while num >= item:
               num -= item
               ele += key

       return ele

RomanToInterger
思路：判断相邻的左边数和右边数：左边>右边，取负数，左边<右边，取正数。最后数字相加。

class Solution:
    def romanToInt(self, s):
        # dic = {"M": 1000, "CM": 900, "D": 500, "CD": 400, "C": 100, "XC": 90, "L": 50, "XL": 40, "X": 10, "IX": 9, "V": 5, "IV": 4, "I": 1}
        dic = {"M": 1000, "D": 500, "C": 100, "L": 50,  "X": 10, "V": 5, "I": 1}
        num = 0
        for i in range(len(s)-1):
            temp = dic[s[i]] if dic[s[i]]>=dic[s[i+1]] else -1*dic[s[i]]
            num +=temp
        num += dic[s[-1]]
        return num

solu = Solution()
print(solu.romanToInt("XC"))

Longest Common Prefix
这道题的解法来自网络，对min函数用法值得我学习。
最长的共同前缀，思路：找到最短的字符串，一个个字符在其他字符串中比较是不是相同，不同返回之前相同部分

class Solution(object):
   def longestCommonPrefix(self, strs):
       """
       :type strs: List[str]
       :rtype: str
       """
       shotstr = min(strs, key=len)
       
       for i, letter in enumerate(shotstr):
           for other in strs:
               if other[i] == letter:
                   pass
               else:
                   return shotstr[:i]
       return shotstr

6.mergeTwoLlists
链表结构。leetcode链接

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

class Solution(object):
   def mergeTwoLists(self, l1, l2):
       """
       :type l1: ListNode
       :type l2: ListNode
       :rtype: ListNode
       """
       if l1 is None or l2 is None:
           return l1 or l2
       if l1.val > l2.val:
           l2.next = self.mergeTwoLists(l2.next, l1)
           return l2
       else:
           l1.next = self.mergeTwoLists(l1.next, l2)
           return l1

7.去除相同元素
Remove Duplicates from Sorted Array
这道题返回不正确，应该是返回不重复的列表

nums = [0,1,2,3,3,3,3,4,9]
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        lenResult = 0
        index = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[index]:
                lenResult += 1
                index = i

        return lenResult+1

print(Solution().removeDuplicates(nums=nums))