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

# LeetCode 题解五（python版）

LeetCode Python

Markdown版请移步

## 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

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 = 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。

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

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

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

# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass 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)

• 私有
• 公开
• 删除