@chanvee 2015-01-21T21:23:25.000000Z 字数 4907 阅读 6992

LeetCode 题解六（python版）

LeetCode Python

Binary Tree Preorder Traversal

二叉树的先序遍历输出，思想很简单，直接代码了：

# 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 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 = None
class 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 = None
class 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)

Linked List Cycle

判断一个链表是否有循环，思路是我先建一个节点，然后遍历这个链表，每遍历一个节点，就让这个节点指向刚刚新建的那个节点，这样如果有循环，那么它回来之后的next就会指向那个节点，那么就代表有循环。代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class 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

Linked List Cycle II

与上个题类似，只不过不是判断是否有循环，变为了如果有循环则输出循环开始的位置，这个题就不能向上一个题那样做了，因为上一个题改变了原有的链表的结构，而这个题要返回链表，所有不幸，但思路一致，我们可以把遍历过的节点的值都变为负无穷，如果遇到节点的信息为负无穷，那么这个点就是循环开始的点。代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class 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 = None
class 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

关于Polish Notation的背景介绍，详细见这里。看完之后可以知道我们可以用栈来实现Reverse Polish Notation，也就是遇到数字加入栈，遇到操作符则将出栈两个数来进行操作，并将操作结果加入到栈中。这里需要注意的是关于python的整除，跟C和java不同，python是向下取整的，而C和Java是向零取整，所以对于负数的整除需要特别改一下。代码如下：

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)

求X的平方根，如果不直接用x^2来计算的话，则采用牛顿法。代码如下：

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

给定整数n和k，输出长度为k的有1到n的组合有多少个。思路是比如说对于k=2到k=3,我们其实相当于在k的基础上加上比第二大但是不大于n的这么多种组合方式，所以可以利用迭代。代码如下：

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)