[关闭]
@chanvee 2014-12-09T11:34:16.000000Z 字数 3891 阅读 20262

LeetCode 题解一(python版)

LeetCode, Python


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

Reverse Words in a String


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

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

Single Number


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

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

Single Number II


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

  1. class Solution:
  2. # @param A, a list of integer
  3. # @return an integer
  4. def singleNumber(self, A):
  5. ones, twos = 0, 0
  6. for ele in A:
  7. ones = ones^ele & ~twos
  8. twos = twos^ele & ~ones
  9. return(ones)

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

  1. def singleNumber(A,m,n):
  2. tmp = [0]*(m-1)
  3. for ele in A:
  4. for i in range(m-1):
  5. tmp[i] = tmp[i]^ele
  6. for j in range(m-1):
  7. if i != j:
  8. tmp[i] = tmp[i] & ~tmp[j]
  9. return(tmp[n-1])

Valid Palindrome


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

  1. import re # 正则表达式包含在re里面
  2. class Solution:
  3. # @param s, a string
  4. # @return a boolean
  5. def isPalindrome(self, s):
  6. s = s.lower() # 首先将字符串转为小写
  7. s = re.sub('[^A-Za-z0-9]','',s) # 正则表达式去除非字母和数字的符号
  8. if s == s[::-1]: # 如果是回文,即正序和逆序一样
  9. return(True)
  10. else:
  11. 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中某一个为空。代码如下:

  1. class Solution:
  2. # @param A a list of integers
  3. # @param m an integer, length of A
  4. # @param B a list of integers
  5. # @param n an integer, length of B
  6. # @return nothing
  7. def merge(self, A, m, B, n):
  8. for i in range(m+n-1, -1, -1):
  9. if m == 0 or (n > 0 and B[n-1] > A[m-1]): # 判断A、B是否为空
  10. A[i] = B[n-1]
  11. n -= 1
  12. else:
  13. A[i] = A[m-1]
  14. m -= 1
  15. 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)。代码如下:

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

Plus One


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

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

Remove Element


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

  1. class Solution:
  2. # @param A a list of integers
  3. # @param elem an integer, value need to be removed
  4. # @return an integer
  5. def removeElement(self, A, elem):
  6. while elem in A:
  7. A.remove(elem)
  8. return(len(A))

Reverse Integer

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

  1. class Solution:
  2. # @return an integer
  3. def reverse(self, x):
  4. if x >=0:
  5. x = '%d' %x # Convert to string
  6. if int(x[::-1]) > (2 ** 31-1):
  7. return 0;
  8. else:
  9. return(int(x[::-1])) # reverse
  10. else:
  11. x = abs(x)
  12. x = '%d' %x
  13. if int("-" + x[::-1]) < -2 ** 31:
  14. return 0
  15. else:
  16. return(int("-" + x[::-1]))

Two Sum


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

  1. class Solution:
  2. # @return a tuple, (index1, index2)
  3. def twoSum(self, num, target):
  4. tmp = {}
  5. for i in range(len(num)):
  6. if target - num[i] in tmp:
  7. return(tmp[target - num[i]] +1, i + 1)
  8. else:
  9. tmp[num[i]] = i;
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注