[关闭]
@chanvee 2015-01-04T10:47:26.000000Z 字数 4412 阅读 3189

LeetCode 题解五(python版)

LeetCode Python


Markdown版请移步

Find Minimum in Rotated Sorted Array


找到一个可旋转数列的最小值,很简单,判断这个数是不是小于它的前一个值和后一个值,是的话就是最小值,对于最小值在最后一位,特殊判断就行了。代码如下:

  1. class Solution:
  2. # @param num, a list of integer
  3. # @return an integer
  4. def findMin(self, num):
  5. for i in range(len(num)):
  6. if i == len(num) -1:
  7. return(num[i])
  8. if num[i] < num[i-1] and num[i] < num[i+1]:
  9. return(num[i])

Find Minimum in Rotated Sorted Array II


遇上个题目要求,只不过这一次元素可以重复,简单,直接贴代码,当然这个题也可以用二分法,代码如下:

  1. class Solution:
  2. # @param num, a list of integer
  3. # @return an integer
  4. def findMin(self, num):
  5. minimum = num[0]
  6. for i in range(len(num)):
  7. if num[i] < minimum:
  8. minimum = num[i]
  9. return(minimum)

Jump Game


给定一个数组,判断从首位置能否到达最后一个位置。这个问题我们可以反过来看,如果从第n-1个位置能够到达第n个位置,那么我们就可以判断前面n-2个位置能否到达第n-1个位置,以此类推,如果最后能反推到第一个位置则说明可以,否则不行。代码如下:

  1. class Solution:
  2. # @param A, a list of integers
  3. # @return a boolean
  4. def canJump(self, A):
  5. index = len(A) - 1
  6. for i in reversed(range(len(A)-1)):
  7. if i + A[i] >= index:
  8. index = i
  9. return(not index)

Factorial Trailing Zeroes


这个题刚开始题目都没看懂,最后还是看了别人的题解才懂的,意思是给定一个整数n,返回n!(n的阶乘)数字中的后缀0的个数。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数,问题就解决了。考虑下面的例子:

n = 5: 5!的质因子中 (2 * 2 * 2 * 3 * 5)包含一个5和三个2。因而后缀0的个数是1。

n = 11: 11!的质因子中(2^8 * 3^4 * 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。

我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢?一个简单的方法是计算floor(n/5)。例如,7!有一个5,10!有两个5。除此之外,还有一件事情要考虑。诸如25,125之类的数字有不止一个5。例如,如果我们考虑28!,我们得到一个额外的5,并且0的总数变成了6。处理这个问题也很简单,首先对n÷5,移除所有的单个5,然后÷25,移除额外的5,以此类推。下面是归纳出的计算后缀0的公式。

n!后缀0的个数 = n!质因子中5的个数
          = floor(n/5) + floor(n/25) + floor(n/125) + ....

代码如下:

  1. class Solution:
  2. # @return an integer
  3. def trailingZeroes(self, n):
  4. tmp = 5
  5. result = 0
  6. while n >= tmp:
  7. result += n//tmp
  8. tmp *= 5
  9. return(result)

Triangle


给定一个杨辉三角,找到这个杨辉三角从上到下最小路径之和。是一个典型的动态规划的题目,从下至上,我们有:

minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];

如果我们用一个一维数组把最小路径之和存下来,得到:

For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i]; 

于是有代码如下:

  1. class Solution:
  2. # @param triangle, a list of lists of integers
  3. # @return an integer
  4. def minimumTotal(self, triangle):
  5. for i in range(len(triangle))[::-1]:
  6. if i == len(triangle) - 1:
  7. m = triangle[i]
  8. else:
  9. for j in range(i+1):
  10. m[j] = triangle[i][j] + min(m[j],m[j+1])
  11. return(m[0])

Decode Ways


给定一个编码的字符串,判断其有多少种编码方式。这其实也是一个动态规划的题目。举个例子如果输入的字符串是‘123’,我们知道‘3’有一种编码方式为‘3’,而加了一个‘2’之后的‘23’就会在原来的基础上多一种方式为2种为‘2,3’,‘23’,而‘123’则有‘1,2,3’,‘1,23’(此对应‘23’方式),‘12,3’(此对应‘3’的编码次数)。所以第k次所含的编码方式则会前两次编码方式之和。但是,这里有一个特例是比如‘323’没有‘32,3’这种编码方式,则这个时候跟上一次的编码次数一致。另外需要注意的就是‘0’这种特殊情况就OK了。代码如下:

  1. class Solution:
  2. # @param s, a string
  3. # @return an integer
  4. def numDecodings(self, s):
  5. if s == '':
  6. return(0)
  7. result = []
  8. result.append(1)
  9. if int(s[len(s)-1]) > 0 and int(s[len(s)-1]) <= 26:
  10. result.append(1)
  11. else:
  12. result.append(0)
  13. tmp = s[len(s)-1]
  14. k = 2
  15. for i in range(len(s)-1)[::-1]:
  16. result.append(0)
  17. if s[i] == '0':
  18. k += 1
  19. continue
  20. tmp = s[i] + tmp
  21. if int(tmp) <= 26:
  22. result[k] = result[k-1] + result[k-2]
  23. else:
  24. result[k] = result[k-1]
  25. tmp = tmp[0]
  26. k += 1
  27. return(result[len(result)-1])

Implement strStr()


这个题直接调用的现成的函数,如果自己写的话,那我也是会直接暴力循环的。代码如下:

  1. class Solution:
  2. # @param haystack, a string
  3. # @param needle, a string
  4. # @return an integer
  5. def strStr(self, haystack, needle):
  6. return(haystack.find(needle))

Longest Common Prefix


寻找字符数组中最长的共同前缀,找到最短的数组,然后每次加一个看是不是他们的前缀,如果数组中含有一个‘’的话,则前缀为‘’。代码如下:

  1. class Solution:
  2. # @return a string
  3. def longestCommonPrefix(self, strs):
  4. if len(strs) == 0:
  5. return('')
  6. if len(strs) == 1:
  7. return(strs[0])
  8. idx = 0
  9. for i in range(1, len(strs)):
  10. if len(strs[i]) < len(strs[idx]):
  11. idx = i
  12. if len(strs[idx]) == 0:
  13. return('')
  14. tmp = ''
  15. for i in range(len(strs[idx])):
  16. tmp1 = tmp + strs[idx][i]
  17. for j in range(len(strs)):
  18. if strs[j].find(tmp1) != 0:
  19. return(tmp)
  20. tmp = tmp1
  21. if i == len(strs[idx]) - 1:
  22. return(tmp)

Find Peak Element


找到一个数组的peak element(该元素比起邻居都大的元素),很简单,需要注意的是这个题只需要返回一个值即可。代码如下:

  1. class Solution:
  2. # @param num, a list of integer
  3. # @return an integer
  4. def findPeakElement(self, num):
  5. i = 0
  6. while i < len(num):
  7. if i == 0 and (len(num) == 1 or num[i] > num[i+1]):
  8. return(i)
  9. if i == len(num) - 1 and (len(num) == 1 or num[i] > num[i-1]):
  10. return(i)
  11. if num[i] > num[i-1] and num[i] > num[i+1]:
  12. return(i)
  13. i += 1

Sum Root to Leaf Numbers


给定一棵树,从其根节点至其任意一个叶子节点分别代表一个数,求这些数之和。其实就是遍历这个二叉树,每次遍历的时候把上次的数记下来,在下一次乘10在加起来就可以了。代码如下:

  1. # Definition for a binary tree node
  2. # class TreeNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.left = None
  6. # self.right = None
  7. class Solution:
  8. # @param root, a tree node
  9. # @return an integer
  10. def sumNumbers(self, root):
  11. sum = 0
  12. if root == None:
  13. return(sum)
  14. if root.left == None and root.right == None:
  15. sum += root.val
  16. if root.left:
  17. sum += self.sumNumbers1(root.left, 10*root.val)
  18. if root.right:
  19. sum += self.sumNumbers1(root.right, 10*root.val)
  20. return(sum)
  21. def sumNumbers1(self, root, sum):
  22. if root == None:
  23. return(sum)
  24. if root.left == None and root.right == None:
  25. sum += root.val
  26. return(sum)
  27. left = right = 0
  28. if root.left:
  29. left = self.sumNumbers1(root.left, 10*(root.val + sum))
  30. if root.right:
  31. right = self.sumNumbers1(root.right, 10*(root.val + sum))
  32. sum = left + right
  33. return(sum)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注