@chanvee 2014-12-14T11:29:58.000000Z 字数 7687 阅读 6143

# LeetCode 题解二（python版）

LeetCode, Python

## Same Tree

# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # @param p, a tree node    # @param q, a tree node    # @return a boolean    def isSameTree(self, p, q):          if p == None and q == None:            return(True)        elif p == None or q == None:            return(False)        else:            if p.val != q.val:                return(False)            else:                  if self.isSameTree(p.left, q.left):                     return(self.isSameTree(p.right, q.right))                else:                    return(False) 

## Symmetric Tree

# 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 a boolean    def isSymmetric(self, root):        if root == None:            return(True)        else:            return(self.isSameTree(root.left, root.right))    def isSameTree(self, p, q):        if p == None and q == None:            return(True)        elif p == None or q == None:            return(False)        else:            if p.val != q.val:                return(False)            else:                if self.isSameTree(p.left, q.right):                     return(self.isSameTree(p.right, q.left))                else:                    return(False) 

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @return a ListNode    def addTwoNumbers(self, l1, l2):        add = 0        l3 = ListNode(0)        cur = l3        while l1 or l2:            node = ListNode(add)            if l1:                node.val += l1.val                l1 = l1.next            if l2:                node.val += l2.val                l2 = l2.next            if node.val >= 10:                add = 1            else:                add = 0            node.val %= 10            cur.next, cur = node, node         if add:            cur.next = ListNode(1)        return(l3.next)

## Remove Duplicates from Sorted List

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @param head, a ListNode    # @return a ListNode    def deleteDuplicates(self, head):        if head == None:            return(None)        else:            cur = ListNode(head.val)            cur.next, head = head, cur            while cur:                if cur.next and cur.val == cur.next.val:                    if cur.next.next:                        cur.next = cur.next.next                    else:                        cur.next = None                else:                    cur = cur.next            return(head)

## Remove Duplicates from Sorted List II

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @param head, a ListNode    # @return a ListNode    def deleteDuplicates(self, head):        if head == None or head.next == None:            return(head)        cur = ListNode(head.val)        cur.next, head = head, cur        flag = False        while cur:            if cur.next and cur.next.next and cur.next.val == cur.next.next.val:                cur.next = cur.next.next                flag = True            elif flag and cur.next:                cur.next = cur.next.next                flag = False            else:                cur = cur.next        return(head.next)

## Remove Duplicates from Sorted Array

class Solution:    # @param a list of integers    # @return an integer    def removeDuplicates(self, A):        if A == []:            return(0)        count = 1        for i in range(1,len(A)):            if A[i] != A[i-1]:                A[count] = A[i]                count += 1        return(count)

## Remove Duplicates from Sorted Array II

class Solution:    # @param A a list of integers    # @return an integer    def removeDuplicates(self, A):        if len(A) <= 2:             return(len(A))        count = 2        for i in range(2,len(A)):            if A[i] != A[count-1] or A[i] != A[count-2]:                A[count] = A[i]                count += 1        return(count)

## Pascal's Triangle

class Solution:    # @return a list of lists of integers    def generate(self, numRows):        if numRows == 1:            return([[1]])        elif numRows == 2:            return([[1],[1,1]])        elif numRows == 0:            return([])        else:            result = [[1],[1,1]]            for i in range(3, numRows+1):                tmp = [1]*i                last = result[i-2]                for j in range(1,(i-1)//2 + 1):                    tmp[j] = tmp[i-1-j] = last[j-1] +last[j]                result.append(tmp)            return(result)

## Pascal's Triangle II

L(i,j)=Cj1i=i!(j1)!(nj+1)!
,所有我们就可以很简单得到任意一行的值了，只需再添加一个计算阶乘的函数，代码如下：

class Solution:    # @return a list of integers    def getRow(self, rowIndex):        result = [1]*(rowIndex + 1)        for i in range(1,(rowIndex)//2 + 1):            result[i] = result[rowIndex-i] = self.factorial(rowIndex)//(self.factorial(i)*self.factorial(rowIndex-i))        return(result)    def factorial(self, n):        if n == 1:            return(1)        else:            return(n*self.factorial(n-1))

## Minimum Depth of Binary Tree

# 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 minDepth(self, root):        if root == None:            return(0)        if root.left == None and root.right == None:            return(1)        left = right = float("inf") # 表示无穷大        if root.left != None:            left = 1 + self.minDepth(root.left)        if root.right != None:            right = 1 + self.minDepth(root.right)        return(min(left, right))

## Maximum Depth of Binary Tree

# 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 maxDepth(self, root):        if root == None:            return(0)        if root.left == None and root.right == None:            return(1)        left = right = -1        if root.left != None:            left = 1 + self.maxDepth(root.left)        if root.right != None:            right = 1 + self.maxDepth(root.right)        return(max(left, right))

## Path Sum

# 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    # @param sum, an integer    # @return a boolean    def hasPathSum(self, root, sum):        result = False        if root == None:            return(result)        else:            sum -= root.val            if sum == 0 and root.left == None and root.right == None:                result = True                return(result)            else:                if root.left:                    result = result or self.hasPathSum(root.left, sum) # 只要存在一条就返回True                if root.right:                    result = result or self.hasPathSum(root.right, sum)                return(result)

## Length of Last Word

class Solution:    # @param s, a string    # @return an integer    def lengthOfLastWord(self, s):        if s == '':            return(0)        result = s.split()        if result == []:            return(0)        return(len(result[-1]))

class Solution:    # @param a, a string    # @param b, a string    # @return a string    def addBinary(self, a, b):        a = a[::-1] # 字符串倒序        b = b[::-1] # 字符串倒序        i = j = 0        c = []        add = 0 # 表示进位        while i < len(a) or j < len(b):            if i < len(a) and j < len(b):                tmp = (int(a[i]) + int(b[j]) + add) % 2                c.append(str(tmp))                if (int(a[i]) + int(b[j]) + add) >= 2:                    add = 1                else:                    add = 0                i += 1                j += 1            if i < len(a) and j>= len(b):                tmp = (int(a[i]) + add)%2                c.append(str(tmp))                if (int(a[i]) + add) >= 2:                    add = 1                else:                    add = 0                i += 1            if i >= len(a) and j < len(b):                tmp = (int(b[j]) + add)%2                c.append(str(tmp))                if (int(b[j]) + add) >= 2:                    add = 1                else:                    add = 0                j += 1        if add:            c.append('1')        c = c[::-1]        result = "".join(c)        return(result)

## Valid Parentheses

class Solution:    # @return a boolean    def isValid(self, s):        if len(s)%2 != 0 or s[-1] == '(' or s[-1] =='[' or s[-1] =='{':            return(False)        result = True        a = []        for i in range(len(s)):            if s[i] =='(' or s[i] =='[' or s[i] =='{':                a.append(s[i])            else:                if len(a) == 0:                    result = False                    break                if s[i] == ')':                    if a.pop() != '(':                        result = False                        break                if s[i] == ']':                    if a.pop() != '[':                        result = False                        break                if s[i] == '}':                    if a.pop() != '{':                        result = False                        break        return(result)

• 私有
• 公开
• 删除