本站消息

站长简介/公众号


站长简介:高级软件工程师,曾在阿里云,每日优鲜从事全栈开发工作,利用周末时间开发出本站,欢迎关注我的微信公众号:程序员总部,程序员的家,探索程序员的人生之路!分享IT最新技术,关注行业最新动向,让你永不落伍。了解同行们的工资,生活工作中的酸甜苦辣,谋求程序员的最终出路!

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

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

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-12(23)

2021-01(42)

Leetcode刷题python

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



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

  1. 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
  1. 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
  1. 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]
  1. 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]
  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)
  1. 整数反转
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
  1. 字符串转换整数 (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

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

  1. 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
  1. 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
  1. 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

  1. 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"))
  1. 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))






所属网站分类: 技术文章 > 博客

作者:听爸爸的话

链接:https://www.pythonheidong.com/blog/article/6259/4e99089a23885297bb44/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

1 0
收藏该文
已收藏

评论内容:(最多支持255个字符)