初试Leetcode

作者: Lunafobia | 来源:发表于2019-05-31 06:37 被阅读1次

    玩了一下leetcode,做最简单的two sum问题(https://leetcode.com/problems/two-sum/ )。
    首先上来用了简单粗暴的for循环,还用了两次。虽然正确算出结果,却用了6400ms的时间(大部分答案的运算时间在几十毫秒)。

    # first try
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            for i in range(len(nums)):
                for j in range(i+1, len(nums)):
                    if nums[i]+nums[j] == target:
                        result = [i,j]
                        break
                        
            return result
    

    后来尝试用library,先把list整个转化成library,再做一些算法运算。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            
            dictA = {k: v for v, k in enumerate(nums)}
    
            for i, el in enumerate(nums):
                dictA.pop(nums[i])
                
                if target-nums[i] in dictA.keys():
                    result=[i,dictA[target-nums[i]]]
                else:
                    print(dictA)
            return result
    

    这种算法在input列表里有重复元素是会出现Runtime Error,应该array是整体转化成dict之后,有重复元素,在for loop里pop或del后便会报错。

    后来朋友提醒我,何必一开始就全部转化呢?如果前两个元素就符合要求的话,全部转化之后再计算会耗费更多的资源。
    于是有了后来这个算法,运算时间32ms:

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            
            dictA = {}
            
            for i in range(len(nums)):
                if target-nums[i] in dictA.keys():
                    result=[dictA[target-nums[i]],i]
                    return result
                    break
                else:
                    dictA.update({nums[i]:i})
    

    相关文章

      网友评论

        本文标题:初试Leetcode

        本文链接:https://www.haomeiwen.com/subject/jmeitctx.html