@chanvee 2015-01-21T13:23:25.000000Z 字数 4907 阅读 6873

# LeetCode 题解六（python版）

LeetCode Python

Markdown版请移步

## Binary Tree Preorder Traversal

# 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 list of integers    def preorderTraversal(self, root):        result = []        return(self.preorderTraversal1(root, result))    def preorderTraversal1(self, root, result):        if root == None:            return(result)        result.append(root.val)        if root.left:            result = self.preorderTraversal1(root.left, result)        if root.right:            result = self.preorderTraversal1(root.right, result)        return(result)

## Binary Tree Postorder Traversal

# 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 list of integers    def postorderTraversal(self, root):        result = []        return(self.postorderTraversal1(root, result))    def postorderTraversal1(self, root, result):        if root == None:            return(result)        if root.left:            result = self.postorderTraversal1(root.left, result)        if root.right:            result = self.postorderTraversal1(root.right, result)        result.append(root.val)        return(result)

## Binary Tree Inorder Traversal

# 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 list of integers    def inorderTraversal(self, root):        result = []        return(self.inorderTraversal1(root, result))    def inorderTraversal1(self, root, result):        if root == None:            return(result)        if root.left:            result = self.inorderTraversal1(root.left, result)        result.append(root.val)        if root.right:            result = self.inorderTraversal1(root.right, result)         return(result)

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @param head, a ListNode    # @return a boolean    def hasCycle(self, head):        tmp = ListNode(0)        result  = False        if head == None:            return(result)        while head:            if head.next == None:                return(result)            if head.next == tmp:                result = True                return(result)            cur, head.next = head.next, tmp            head = cur

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @param head, a ListNode    # @return a list node    def detectCycle(self, head):        if head == None:            return(None)        while head:            if head.next == None:                return(None)            if head.val == float("inf"):                return(head)            head.val = float("inf")            head = head.next

## Intersection of Two Linked Lists

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # @param two ListNodes    # @return the intersected ListNode    def getIntersectionNode(self, headA, headB):        if headA == None or headB == None:            return(None)        lenA, lenB = 0, 0        curA, curB = headA, headB        while curA:            lenA += 1            curA = curA.next        while curB:            lenB += 1            curB = curB.next        if lenA > lenB:            for i in range(lenA-lenB):                headA = headA.next        if lenA < lenB:            for i in range(lenB-lenA):                headB = headB.next        while headA:            if headA == headB:                return(headA)            headA = headA.next            headB = headB.next        return(None)

## Largest Number

class Solution:    # @param num, a list of integers    # @return a string    def largestNumber(self, num):        if len(num)==0:            return ""        strAry=[str(item) for item in num]        array=self.sorting(strAry)        res=''.join(array)        if int(res)==0:            return '0'        else:            return res    def sorting(self, strAry):        for i in range(len(strAry)-1):            for j in range(i+1, len(strAry)):                if self.compare(strAry[i], strAry[j]):                    temp=strAry[i]                    strAry[i]=strAry[j]                    strAry[j]=temp        return strAry    def compare(self, s1,s2):        return(s1+s2 > s2+s1)

## Evaluate Reverse Polish Notation

class Solution:    # @param tokens, a list of string    # @return an integer    def evalRPN(self, tokens):        tmp = []        result = 0        for i in range(len(tokens)):            if tokens[i] == '+' or tokens[i] == '-' or tokens[i] == '*' or tokens[i] == '/':                a = tmp.pop()                b = tmp.pop()                if tokens[i] == '+':                    result = b + a                if tokens[i] == '-':                    result = b - a                if tokens[i] == '*':                    result = b * a                if tokens[i] == '/':                    if a*b < 0:                        result = abs(b) // abs(a)                        result = -result                    else:                        result = b // a                tmp.append(result)            else:                tmp.append(int(tokens[i]))        return(tmp.pop())

## Sqrt(x)

class Solution:    # @param x, an integer    # @return an integer    def sqrt(self, x):        result = x/2.0        while abs(result*result - x) > 0.00001:            result = (result + x/result) / 2.0        return(int(result))

## Combinations

class Solution:    # @return a list of lists of integers    def combine(self, n, k):        result = []        if k == 1:            for i in range(1, n + 1):                result.append([i])            return(result)        result = self.combine(n, k-1)        tmp = []        for res in result:            for i in range(res[-1] + 1, n + 1):                tmp.append(res + [i])        return(tmp)

• 私有
• 公开
• 删除