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

LeetCode 题解六(python版)

LeetCode Python


Markdown版请移步

Binary Tree Preorder Traversal


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

  1. # Definition for a binary tree node
  2. # class TreeNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.left = None
  6. # self.right = None
  7. class Solution:
  8. # @param root, a tree node
  9. # @return a list of integers
  10. def preorderTraversal(self, root):
  11. result = []
  12. return(self.preorderTraversal1(root, result))
  13. def preorderTraversal1(self, root, result):
  14. if root == None:
  15. return(result)
  16. result.append(root.val)
  17. if root.left:
  18. result = self.preorderTraversal1(root.left, result)
  19. if root.right:
  20. result = self.preorderTraversal1(root.right, result)
  21. return(result)

Binary Tree Postorder Traversal


二叉树的后序遍历输出,代码如下:

  1. # Definition for a binary tree node
  2. # class TreeNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.left = None
  6. # self.right = None
  7. class Solution:
  8. # @param root, a tree node
  9. # @return a list of integers
  10. def postorderTraversal(self, root):
  11. result = []
  12. return(self.postorderTraversal1(root, result))
  13. def postorderTraversal1(self, root, result):
  14. if root == None:
  15. return(result)
  16. if root.left:
  17. result = self.postorderTraversal1(root.left, result)
  18. if root.right:
  19. result = self.postorderTraversal1(root.right, result)
  20. result.append(root.val)
  21. return(result)

Binary Tree Inorder Traversal


二叉树的中序遍历,不再赘述,代码如下:

  1. # Definition for a binary tree node
  2. # class TreeNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.left = None
  6. # self.right = None
  7. class Solution:
  8. # @param root, a tree node
  9. # @return a list of integers
  10. def inorderTraversal(self, root):
  11. result = []
  12. return(self.inorderTraversal1(root, result))
  13. def inorderTraversal1(self, root, result):
  14. if root == None:
  15. return(result)
  16. if root.left:
  17. result = self.inorderTraversal1(root.left, result)
  18. result.append(root.val)
  19. if root.right:
  20. result = self.inorderTraversal1(root.right, result)
  21. return(result)

Linked List Cycle


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

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. # @param head, a ListNode
  8. # @return a boolean
  9. def hasCycle(self, head):
  10. tmp = ListNode(0)
  11. result = False
  12. if head == None:
  13. return(result)
  14. while head:
  15. if head.next == None:
  16. return(result)
  17. if head.next == tmp:
  18. result = True
  19. return(result)
  20. cur, head.next = head.next, tmp
  21. head = cur

Linked List Cycle II


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

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. # @param head, a ListNode
  8. # @return a list node
  9. def detectCycle(self, head):
  10. if head == None:
  11. return(None)
  12. while head:
  13. if head.next == None:
  14. return(None)
  15. if head.val == float("inf"):
  16. return(head)
  17. head.val = float("inf")
  18. head = head.next

Intersection of Two Linked Lists


求两个链表交叉的节点,思路是如果两个链表等长的话,那么我们只需依次遍历比较这两个链表的节点是否相同即可,所以如果不等长的话,我们将长的链表多出的节点先遍历过,然后再比较即可。代码如下:

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. # @param two ListNodes
  8. # @return the intersected ListNode
  9. def getIntersectionNode(self, headA, headB):
  10. if headA == None or headB == None:
  11. return(None)
  12. lenA, lenB = 0, 0
  13. curA, curB = headA, headB
  14. while curA:
  15. lenA += 1
  16. curA = curA.next
  17. while curB:
  18. lenB += 1
  19. curB = curB.next
  20. if lenA > lenB:
  21. for i in range(lenA-lenB):
  22. headA = headA.next
  23. if lenA < lenB:
  24. for i in range(lenB-lenA):
  25. headB = headB.next
  26. while headA:
  27. if headA == headB:
  28. return(headA)
  29. headA = headA.next
  30. headB = headB.next
  31. return(None)

Largest Number


给定一个数组列表,输出由这个数组列表中元素组成的最大数。我用的方法比较慢,因为用的是冒泡排序,思路就是比较两个数的“大小”,但是这里不是绝对数值的大小,而是比较两个数拼接起来的大小。代码如下:

  1. class Solution:
  2. # @param num, a list of integers
  3. # @return a string
  4. def largestNumber(self, num):
  5. if len(num)==0:
  6. return ""
  7. strAry=[str(item) for item in num]
  8. array=self.sorting(strAry)
  9. res=''.join(array)
  10. if int(res)==0:
  11. return '0'
  12. else:
  13. return res
  14. def sorting(self, strAry):
  15. for i in range(len(strAry)-1):
  16. for j in range(i+1, len(strAry)):
  17. if self.compare(strAry[i], strAry[j]):
  18. temp=strAry[i]
  19. strAry[i]=strAry[j]
  20. strAry[j]=temp
  21. return strAry
  22. def compare(self, s1,s2):
  23. return(s1+s2 > s2+s1)

Evaluate Reverse Polish Notation


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

  1. class Solution:
  2. # @param tokens, a list of string
  3. # @return an integer
  4. def evalRPN(self, tokens):
  5. tmp = []
  6. result = 0
  7. for i in range(len(tokens)):
  8. if tokens[i] == '+' or tokens[i] == '-' or tokens[i] == '*' or tokens[i] == '/':
  9. a = tmp.pop()
  10. b = tmp.pop()
  11. if tokens[i] == '+':
  12. result = b + a
  13. if tokens[i] == '-':
  14. result = b - a
  15. if tokens[i] == '*':
  16. result = b * a
  17. if tokens[i] == '/':
  18. if a*b < 0:
  19. result = abs(b) // abs(a)
  20. result = -result
  21. else:
  22. result = b // a
  23. tmp.append(result)
  24. else:
  25. tmp.append(int(tokens[i]))
  26. return(tmp.pop())

Sqrt(x)


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

  1. class Solution:
  2. # @param x, an integer
  3. # @return an integer
  4. def sqrt(self, x):
  5. result = x/2.0
  6. while abs(result*result - x) > 0.00001:
  7. result = (result + x/result) / 2.0
  8. return(int(result))

Combinations


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

  1. class Solution:
  2. # @return a list of lists of integers
  3. def combine(self, n, k):
  4. result = []
  5. if k == 1:
  6. for i in range(1, n + 1):
  7. result.append([i])
  8. return(result)
  9. result = self.combine(n, k-1)
  10. tmp = []
  11. for res in result:
  12. for i in range(res[-1] + 1, n + 1):
  13. tmp.append(res + [i])
  14. return(tmp)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注