@chanvee 2014-12-09T11:34:16.000000Z 字数 3891 阅读 20693

LeetCode 题解一（python版）

LeetCode, Python

前几天听一位好哥们介绍了LeetCode，据说很多公司的面试题目都是从这里参考而来，于是也开始跟风来刷一下这里的题目。LeeTCode是支持python的，而我也不会python，于是想着通过刷题来顺带来学习一下python这门现在很火的语言，于是这周边看边刷，做了10道水题，作为题解以备不时之需。

Reverse Words in a String

这个题的意思是，给定一个字符串，字符串是以单词的形式拼接起来的，需要做的就是把字符串里面的单词逆序输出，但是单词内的顺序是不变的，相信看它的例子大家都能明白。这个题目用python里面的列表的话就非常简单，首先将字符串按“ ”分割，然后去掉分割出来的列表中空格（因为两个单词间可能有多个空格，这是这个题目的陷阱），最后列表倒序再以空格拼接成字符串输出即可。代码如下：

class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        tmp = s.split(' ') # 将字符串分割为列表
        while '' in tmp:   # 清除空元素
            tmp.remove('')
        tmp.reverse()      # 列表倒序
        tmp = ' '.join(tmp) #列表转化为字符串，并以空格连接
        return(tmp)

Single Number

这个题和下一个题都很有技巧，这个题的意思是给定一个序列，这个序列中的数除了有一个数只出现过一次外，其他的数都出现两次，请找出这个只出现一次的数。最直观的想法就是遍历一遍把每个数出现的次数都存起来，然后再看谁的次数为1。但是网上有一种更加简洁而巧妙地方法，用异或来解决这个问题，他的思想是两个相同的数异或为0,0和任何数异或为任何数，这样只需要把整个序列全都异或一遍，最后得到的数就是想要的答案了。代码如下：

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        result = 0
        for i in A:
        # 相同元素异或为0,0与任何数异或等于任何数，有a^b^a = b
        # 此外，异或还可以用于两个元素交换a=a^b^(b=a)
            result = result^i   
        return(result)

Single Number II

这个题更加巧妙，题目与上一个题目类似，不过这一次序列中的数字除了某一个数字外都出现3次，需要找出这个数字，先贴代码再解释。

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        ones, twos = 0, 0
        for ele in A: 
            ones = ones^ele & ~twos 
            twos = twos^ele & ~ones
        return(ones)

当元素ele第一出现时，ones，twos = ele，0；当其第二次出现时，ones,twos = 0,ele；当其第三次出现时ones,twos都变为0，就相当于这个数字没有出现过，这样最后的结果就是ones了。于是，根据这个题我们可以推广到，有这样一个序列，序列中所有的数字都出现m次，只有一个数字出现n次（m>n），请找出这个只出现n次的数字，代码如下：

def singleNumber(A,m,n):
        tmp = [0]*(m-1)
        for ele in A: 
            for i in range(m-1):
                tmp[i] = tmp[i]^ele
                for j in range(m-1):
                    if i != j:
                        tmp[i] = tmp[i] & ~tmp[j]
        return(tmp[n-1])

Valid Palindrome

这个题是判断一个字符串是否是回文，回文的意思是正序和逆序都一样，所以这也成了我们判断的标准，这个题的回文是不区分大小写的，因此首先可以将所有字母转为小（大）写，需要注意的是它这里只关注字母和数字，因此其他的符号需要去掉，需要用到了python的正则表达式。代码如下：

import re # 正则表达式包含在re里面
class Solution:
    # @param s, a string
    # @return a boolean
    def isPalindrome(self, s):
        s = s.lower() # 首先将字符串转为小写
        s = re.sub('[^A-Za-z0-9]','',s) # 正则表达式去除非字母和数字的符号
        if s == s[::-1]: # 如果是回文，即正序和逆序一样
            return(True)
        else:
            return(False)

Merge Sorted Array

这个题目的意思是把两个排好序的序列合并为一个排好序的序列，本来我最开始想的是直接把两个序列拼接在一起，然后用python列表里面自带的sort函数排个序就Ok了，但是这样做的复杂度至少是O((m+n)log(m+n))的，另外一种O(m+n)做法是从后面往前面排，比如合并后的最后一个数A[m+n-1]就应该等于A[m-1]和B[n-1]中较大的一个以此类推，这样可以避免从前往后需要移动的操作，需要注意的特列就是A和B中某一个为空。代码如下：

class Solution:
    # @param A  a list of integers
    # @param m  an integer, length of A
    # @param B  a list of integers
    # @param n  an integer, length of B
    # @return nothing
    def merge(self, A, m, B, n):
        for i in range(m+n-1, -1, -1): 
            if m == 0 or (n > 0 and B[n-1] > A[m-1]): # 判断A、B是否为空
                A[i] = B[n-1]
                n -= 1
            else:
                A[i] = A[m-1]
                m -= 1
        return(A)

Climbing Stairs

这其实是一道组合数学的题目，总共有n步台阶，每次只能走一步或者两步，总共有多少种走法。这个问题可以这样思考：假设已知有n步台阶共有f(n)种走法，对于n+1步台阶由两部分组成：一个是前面n步台阶的f(n)种走法后直接一步到达n+1；另一种是前面n-1步台阶的f(n-1)种走法后走两步到达n+1。因此可以得到递推关系是：f(n+1) = f(n) + f(n-1)。代码如下：

class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        f = [1, 2]
        for i in range(2,n):  
            f.append(f[i-2] + f[i-1])
        return(f[n-1])

Plus One

这个题就是实现大数（用数组存储）加1的功能。需要注意的就是满十进一这个规则，以及类似999+1=1000需要在第一位添一个1这种特例。代码如下：

class Solution:
    # @param digits, a list of integer digits
    # @return a list of integer digits
    def plusOne(self, digits):
        flag = 1
        for i in range(len(digits)-1, -1, -1):
            digits[i] = (digits[i] + 1) % 10 # 加1模10，如果没有进位则跳出循环，否则高一位加1
            if digits[i]:
                flag = 0
                break 
        if flag: # 如果每一位都进位了，则在数组第一位添加1
            digits.insert(0,1)
        return(digits)

Remove Element

这个题目的意思是去掉序列中规定的元素之后求剩下的序列的长度，非常简单，代码如下：

class Solution:
    # @param    A       a list of integers
    # @param    elem    an integer, value need to be removed
    # @return an integer
    def removeElement(self, A, elem):
        while elem in A:
            A.remove(elem)
        return(len(A))

Reverse Integer

这个题是将一个整数逆序输出，当然如果是负数，符号不需要逆序。做法就是将其转化为字符串，然后逆序即可。需要注意的陷阱就是当你逆序之后，该数可能超出了最大值2^31 - 1，需要做判断。

class Solution:
    # @return an integer
    def reverse(self, x):
        if x >=0:
        x = '%d' %x  # Convert to string
        if int(x[::-1]) > (2 ** 31-1):
            return 0;
        else:
            return(int(x[::-1])) # reverse
    else:
        x = abs(x)
        x = '%d' %x   
        if int("-" + x[::-1]) < -2 ** 31:
            return 0
        else:
            return(int("-" + x[::-1]))

Two Sum

需找出一个列表中是否有两个数的和为一个给定的数，并返回这两个数的下标。需要用到python里面的字典（相当于hash表），判断第i个数前面是否有一个数的值为target - num[i]。代码如下：

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        tmp = {}
        for i in range(len(num)):
            if target - num[i] in tmp:
                return(tmp[target - num[i]] +1, i + 1)
            else:
                tmp[num[i]] = i;