[关闭]
@chanvee 2014-12-29T10:36:47.000000Z 字数 5817 阅读 4740

LeetCode 题解四(python版)

LeetCode Python


Markdown版请移步

Binary Tree Level Order Traversal


二叉树的层次遍历,可以利用列表来模拟队列,queue.append()相当于入队列,queue.pop(0)相当于出队列。利用队列我们就可以进行二叉树的层次遍历了,方法是:首先把根节点入队列,同时再将None入队列表示这一层结束,然后出队列,如果出队列的这个节点有左右子树则入列,以此循环。需要注意的就是每次一个层出列完之后,入列None,表示下一个层级入列完。代码如下:

  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 lists of integers
  10. def levelOrder(self, root):
  11. if root == None:
  12. return([])
  13. else:
  14. queue = []
  15. queue.append(root)
  16. queue.append(None)
  17. result = []
  18. tmp = []
  19. while queue:
  20. node = queue.pop(0)
  21. if node:
  22. tmp.append(node.val)
  23. if node.left:
  24. queue.append(node.left)
  25. if node.right:
  26. queue.append(node.right)
  27. else:
  28. result.append(tmp)
  29. tmp = []
  30. if queue:
  31. queue.append(None)
  32. return(result)

Binary Tree Level Order Traversal II


这个题我感觉和上个题一样的个,只不过是要由下向上输出。取巧的做法是直接最后的结果revers一下就可以了,当然还有其他的办法,详见这个题LeetCode的Disscuss。代码如下:

  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 lists of integers
  10. def levelOrderBottom(self, root):
  11. if root == None:
  12. return([])
  13. else:
  14. queue = []
  15. queue.append(root)
  16. queue.append(None)
  17. result = []
  18. tmp = []
  19. while queue:
  20. node = queue.pop(0)
  21. if node:
  22. tmp.append(node.val)
  23. if node.left:
  24. queue.append(node.left)
  25. if node.right:
  26. queue.append(node.right)
  27. else:
  28. result.append(tmp)
  29. tmp = []
  30. if queue:
  31. queue.append(None)
  32. result.reverse()
  33. return(result)

Majority Element


给定一个数组(列表),找到这个列表中的主元素,所谓主元素就是该元素在列表中出现的次数大于n/2,n为该数组的长度。这里提供两种方法:第一种首先将数组排序,那么中间的那个数num[n//2]必然就是主元素了,因为主元素的个数要大于整个数组长度的一般嘛,O(nlogn)的复杂度;第二种方法是用字典来存储每个数出现的次数,当某个键值的次数大于一般是即返回,O(n)的复杂度。代码如下:

  1. class Solution:
  2. # @param num, a list of integers
  3. # @return an integer
  4. # Sort
  5. def majorityElement(self, num):
  6. num.sort()
  7. return(num[len(num)//2])
  8. # Another version -- Hash
  9. def majorityElement(self, num):
  10. dic = {}
  11. for i in range(len(num)):
  12. if num[i] in dic:
  13. dic[num[i]] = dic[num[i]] + 1
  14. if dic[num[i]] > len(num)//2:
  15. return(num[i])
  16. else:
  17. dic[num[i]] = 1
  18. if dic[num[i]] > len(num)//2:
  19. return(num[i])

String to Integer (atoi)


这个题虽然看上去很简单,但是想一遍AC真的很难,因为要考虑的情形太多了,我基本上就是交一次试出一组特例,交一次试出一组特例这样试出来的。主要的特例有以下几点:
1. 所有不能转换为字符串的都返回0
2. 出现多个+-号则不能转化,如++2不能转成2
3. 当所表示字符串大于2^31-1或小于-2^31时,返回2^31-1或小于-2^31
4. +-号后面必须接数字,否则返回0
5. " +0 123"应返回0,而不是123
注意以上特列,应该就可以AC了。代码如下:

  1. class Solution:
  2. # @return an integer
  3. def atoi(self, str):
  4. if str == '':
  5. return(0)
  6. str = list(str)
  7. result = []
  8. positive = negtive = 0
  9. has_digit = False
  10. for i in range(len(str)):
  11. if str[i] != '-' and str[i] != '+' and str[i].isdigit() == False and str[i] != ' ':
  12. if has_digit == False:
  13. return(0)
  14. else:
  15. break
  16. if str[i] == ' ' and has_digit:
  17. break
  18. if str[i] == ' ' and (negtive or positive):
  19. return(0)
  20. if str[i] == '-':
  21. negtive = negtive + 1
  22. if str[i] == '+':
  23. positive = positive + 1
  24. if negtive > 1 or positive > 1 or (negtive == 1 and positive == 1):
  25. return(0)
  26. if str[i].isdigit():
  27. has_digit = True
  28. result.append(str[i])
  29. result = ''.join(result)
  30. if negtive:
  31. result ='-' + result
  32. if has_digit:
  33. if int(result) > 2**31 -1:
  34. return(2147483647)
  35. if int(result) < -2**31:
  36. return(-2**31)
  37. return(int(result))
  38. else:
  39. return(0)

Search Insert Position


给定一个已经排好序的数组和一个数,如果这个数在这个数组里面,则返回这个数的下标,否则输出这个数如果插入到这个数组的话应该的下标,非常简单,代码如下:

  1. class Solution:
  2. # @param A, a list of integers
  3. # @param target, an integer to be inserted
  4. # @return integer
  5. def searchInsert(self, A, target):
  6. for i in range(len(A)):
  7. if A[i] >= target:
  8. return(i)
  9. if A[len(A) - 1] < target:
  10. return(len(A))

Balanced Binary Tree


判断一棵树是否是平衡树,平衡树的定义是这棵树的任意两颗左右子树的深度之差都不超过1,我们只需递归它的所有子树然后计算他们的深度差是否大于1即可,如果大于1则返回-100,表明其不是平衡树。代码如下:

  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 boolean
  10. def isBalanced(self, root):
  11. if root == None:
  12. return(True)
  13. return(self.getDepth(root) != -100)
  14. def getDepth(self, root):
  15. if root == None:
  16. return(0)
  17. l = self.getDepth(root.left)
  18. r = self.getDepth(root.right)
  19. if l == -100 or r == -100 or abs(l-r) > 1:
  20. return(-100)
  21. return(1 + max(l,r))

Letter Combinations of a Phone Number


手机数字的字母组合,这个题乍一看很简单,但是其实还是不是那么简单的,本来这个题最简单的想法就是循环呗,但是由于输入多少个数字不知道,所以就不知道该循环几次了,所以我们每两个循环,将得到的结果在与下一次的数字在循环就可以了,比如输入‘234’,纳闷2和3可以又一次循环得到结果,将这个结果再与4循环就可以了。代码如下:

  1. class Solution:
  2. # @return a list of strings, [s1, s2]
  3. def letterCombinations(self, digits):
  4. if digits == '':
  5. return([''])
  6. dic = {'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
  7. for i in range(len(digits)):
  8. if digits[i] == '1' or digits[i] == '0':
  9. continue
  10. digits = digits[i:len(digits)]
  11. break
  12. result = dic[digits[0]]
  13. for i in range(1,len(digits)):
  14. if digits[i] == '1' or digits[i] == '0':
  15. continue
  16. tmp1 = []
  17. for j in range(len(result)):
  18. for k in range(len(dic[digits[i]])):
  19. tmp1.append(result[j] + dic[digits[i]][k])
  20. result = tmp1
  21. return(result)

Swap Nodes in Pairs


成对的交换链表中的节点,但是不能只改变数字。这个题可以现在链表的前端添加一个节点然后指向这个链表,然后再开始执行交换的操作,具体如下,举个例子:(0)-> 1 -> 2 -> None, 先让0(我们在头添加的节点)指向2,然后1指向None,2指向1,这样就完成了交换,后面以此类推。代码如下:

  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 a ListNode
  8. # @return a ListNode
  9. def swapPairs(self, head):
  10. if head == None or head.next == None:
  11. return(head)
  12. result = ListNode(0)
  13. result.next, cur = head, result
  14. while head and head.next:
  15. cur.next = head.next
  16. head.next = cur.next.next
  17. cur.next.next = head
  18. cur = head
  19. head = head.next
  20. return(result.next)

Excel Sheet Column Number


将Excel表格的column转化为数字,与以前的有一道题将数字转化为excel的column刚好相反,也就是26进制转化为十进制,代码如下:

  1. class Solution:
  2. # @param s, a string
  3. # @return an integer
  4. def titleToNumber(self, s):
  5. dic = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  6. result = dic.index(s[0]) + 1
  7. for i in range(1,len(s)):
  8. result = 26*result + dic.index(s[i]) + 1
  9. return(result)

Gray Code


输出格雷码的十进制数,包括两步,第一步是给出格雷码,第二步是将二进制转成十进制的数。难点是格雷码的转换,但是知道他的规则就好做了,规则如下:
1. 位格雷码有两个码字
2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0
3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1
有了以上规则就简单了,代码如下:

  1. class Solution:
  2. # @return a list of integers
  3. def grayCode(self, n):
  4. tmp = ['0', '1']
  5. if n == 0:
  6. return([0])
  7. if n == 1:
  8. return(self.convert2integer(tmp))
  9. result = []
  10. for i in range(n - 1):
  11. for j in tmp:
  12. result.append('0' + j)
  13. for j in tmp[::-1]:
  14. result.append('1' + j)
  15. tmp = result
  16. result = []
  17. return(self.convert2integer(tmp))
  18. def convert2integer(self, tmp):
  19. tt = []
  20. for i in tmp:
  21. result = int(i[0])
  22. for j in range(1,len(i)):
  23. result = 2*result + int(i[j])
  24. tt.append(result)
  25. return(tt)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注