LeetCode把做题当作游戏

LeetCode把做题当作游戏

程序员闲了做什么?你是愿意把有限的时间和金钱花费在打游戏上,锻炼你的虚拟角色,还是花费在编程序上为你自己提升技能呢?相信如果编程序能和打游戏一样好玩的话,有多少人会放弃游戏转向编程。leetcode.com这个网站就可以把编程当作闯关一样。上面有不少很典型的题目,好好修练的话,一定对将来面试找工作很有帮助哦。

我们就拿第一题Two Sum举个例子(Python):

第一题很简单,输入两个参数,nums是个列表,target是一个数,找到nums里的两个数,加起来等于target。输出这两个数的index(起始index为1,不是0)

举个例子:

Input: nums=[2, 7, 11, 15], target=9

Output:[1,2]

很快我就写出第一个程序

V0.1


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n=len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i]+nums[j]==target:
                    return i+1,j+1
        return None
然后我发现这个网站具有很贴心的测试功能: Custom Testcase 这里支持多个测试Case,只需要你把输入参数按行写上就可以。比如:

[3,2,3]
6
[1,2,4]
6

这就表示两个测试Case,然后点击Run Code,网站会输出程序的输出结果,和期望的输出结果。而且你还可以在程序中间进行变量打印,打印的结果也会在这里显示出来。 由于程序比较简单,测两个边界情况ok就提交吧。提交后就Accecpt了。不过如果你没注意到后面还有个more detail链接的话,那你就了解不到这个网站的精髓了。点击more detail后出来这样一幅图。 towsum1

汗,16个测试Case花了5948ms,这么简单一关我只打败了2.69%的用户?打游戏我都没得过这么烂的成绩,改改代码继续。 于是有了下面的代码:

V0.2


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n=len(nums)
        for i in range(n):
            j=target-nums[i]
            if j in nums[i+1:]:
                return [i+1,nums[i+1:].index(j)+i+2]
        return None

提交后,赶紧看more detail。结果 towsum2

提升了不少,904ms,不过还是只打败了14.59%的用户。看来这里的用户比打游戏遇到的用户更难搞定。不出大招是不行了。想想排序,想想二分,继续出来第三版。

V0.3


class Solution(object):
    def twoSum(self, nums, target):
        n=len(nums)
        sortNum = []
        for i in xrange(n):
            sortNum.append((nums[i], i + 1))
        #sort the num
        sortNum.sort()      
start = 0 end = n - 1 while end>start: if sortNum[start][0] + sortNum[end][0] == target: if sortNum[start][1] < sortNum[end][1]: return sortNum[start][1], sortNum[end][1] else: return sortNum[end][1], sortNum[start][1] elif sortNum[start][0] + sortNum[end][0] > target: end -= 1 else: start += 1 return None

提交,more detail towsum3

44ms,这和最初的5000多ms相差100倍。而且这已经打败了72.86%的用户。这还差不多,至少打败大多数吧。。。

你要不要也试一试,看看你是不是战胜的27.2%?

PS: 这个图上点击右侧带颜色图例,还可以看到其他编程语言的用户提交结果的分布情况。如图: towsum4

从图上看,速度对比 C > java > c++ > python > ruby > javascript > csharp

Python还不错嘛,不过又对比之前的图一看,狂汗。。。3000ms以上的程序只有Python。。。估计这些程序就像我的V0.1一样。我只能理解为Python把编程变简单了。。。

过放荡不羁的生活,容易的像顺水推舟。但要结识良朋益友,却难如登天。

巴尔扎克