@chanvee 2015-01-04T10:47:26.000000Z 字数 4412 阅读 3153

LeetCode 题解五（python版）

LeetCode Python

Find Minimum in Rotated Sorted Array

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

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        for i in range(len(num)):
            if i ==  len(num) -1:
                return(num[i])
            if num[i] < num[i-1] and num[i] < num[i+1]:
                return(num[i])

Find Minimum in Rotated Sorted Array II

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

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        minimum = num[0]
        for i in range(len(num)):
            if num[i] < minimum:
                minimum =  num[i]
        return(minimum)

Jump Game

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

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        index = len(A) - 1
        for i in reversed(range(len(A)-1)):
            if i + A[i] >= index:
                index = i
        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) + ....

代码如下：

class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        tmp = 5
        result = 0
        while n >= tmp:
            result += n//tmp
            tmp *= 5
        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];

于是有代码如下：

class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        for i in range(len(triangle))[::-1]:
            if i == len(triangle) - 1:
                m = triangle[i]
            else:
                for j in range(i+1):
                    m[j] = triangle[i][j] + min(m[j],m[j+1])
        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了。代码如下：

class Solution:
    # @param s, a string
    # @return an integer
    def numDecodings(self, s):
        if s == '':
            return(0)
        result = []
        result.append(1)
        if int(s[len(s)-1]) > 0 and int(s[len(s)-1]) <= 26:
            result.append(1)
        else:
            result.append(0)
        tmp = s[len(s)-1]
        k = 2
        for i in range(len(s)-1)[::-1]:
            result.append(0)
            if s[i] == '0':
                k += 1
                continue
            tmp = s[i] + tmp
            if int(tmp) <= 26:
                result[k] = result[k-1] + result[k-2]
            else:
                result[k] = result[k-1]
            tmp = tmp[0]
            k += 1
        return(result[len(result)-1])

Implement strStr()

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

class Solution:
    # @param haystack, a string
    # @param needle, a string
    # @return an integer
    def strStr(self, haystack, needle):
        return(haystack.find(needle))

Longest Common Prefix

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

class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:
            return('')
        if len(strs) == 1:
            return(strs[0])
        idx = 0
        for i in range(1, len(strs)):
            if len(strs[i]) < len(strs[idx]):
                idx = i
        if len(strs[idx]) == 0:
            return('')
        tmp = ''
        for i in range(len(strs[idx])):
            tmp1 = tmp + strs[idx][i]
            for j in range(len(strs)):
                if strs[j].find(tmp1) != 0:
                    return(tmp)
            tmp = tmp1
            if i == len(strs[idx]) - 1:
                return(tmp)

Find Peak Element

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

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        i = 0
        while i < len(num):
            if i == 0 and (len(num) == 1 or num[i] > num[i+1]):
                return(i)
            if i == len(num) - 1 and (len(num) == 1 or num[i] > num[i-1]):
                return(i)
            if num[i] > num[i-1] and num[i] > num[i+1]:
                return(i)
            i += 1

Sum Root to Leaf Numbers

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

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param root, a tree node
    # @return an integer
    def sumNumbers(self, root):
        sum = 0
        if root == None:
            return(sum)
        if root.left == None and root.right ==  None:
            sum += root.val
        if root.left:
            sum += self.sumNumbers1(root.left, 10*root.val)
        if root.right:
            sum += self.sumNumbers1(root.right, 10*root.val)
        return(sum)
    def sumNumbers1(self, root, sum):
        if root == None:
            return(sum)
        if root.left == None and root.right ==  None:
            sum += root.val
            return(sum)
        left = right = 0
        if root.left:
            left = self.sumNumbers1(root.left, 10*(root.val + sum))
        if root.right:
            right = self.sumNumbers1(root.right, 10*(root.val + sum))
        sum = left + right
        return(sum)