@chanvee 2014-12-29T10:36:47.000000Z 字数 5817 阅读 4705

LeetCode 题解四（python版）

LeetCode Python

Binary Tree Level Order Traversal

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

# 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 lists of integers
    def levelOrder(self, root):
        if root == None:
            return([])
        else:
            queue = []
            queue.append(root)
            queue.append(None)
            result = []
            tmp = []
            while queue:
                node = queue.pop(0)
                if node:
                    tmp.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    result.append(tmp)
                    tmp = []
                    if queue:
                        queue.append(None)  
            return(result)

Binary Tree Level Order Traversal II

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

# 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 lists of integers
    def levelOrderBottom(self, root):
        if root == None:
            return([])
        else:
            queue = []
            queue.append(root)
            queue.append(None)
            result = []
            tmp = []
            while queue:
                node = queue.pop(0)
                if node:
                    tmp.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    result.append(tmp)
                    tmp = []
                    if queue:
                        queue.append(None)
            result.reverse()
            return(result)

Majority Element

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

class Solution:
    # @param num, a list of integers
    # @return an integer
    # Sort
    def majorityElement(self, num):
        num.sort()
        return(num[len(num)//2])
    # Another version -- Hash
    def majorityElement(self, num):
        dic = {}
        for i in range(len(num)):
            if num[i] in dic:
                dic[num[i]] = dic[num[i]] + 1
                if dic[num[i]] > len(num)//2:
                    return(num[i])
            else:
                dic[num[i]] = 1
                if dic[num[i]] > len(num)//2:
                    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了。代码如下：

class Solution:
    # @return an integer
    def atoi(self, str):
        if str == '':
            return(0)
        str = list(str)
        result = []
        positive = negtive = 0
        has_digit = False
        for i in range(len(str)):
            if str[i] != '-' and str[i] != '+' and str[i].isdigit() == False and str[i] != ' ':
                if has_digit == False:
                    return(0)
                else:
                    break
            if str[i] == ' ' and has_digit:
                break
            if str[i] == ' ' and (negtive or positive):
                return(0)
            if str[i] == '-':
                negtive = negtive + 1
            if str[i] == '+':
                positive = positive + 1
            if negtive > 1 or positive > 1 or (negtive == 1 and positive == 1):
                return(0)
            if str[i].isdigit():
                has_digit = True
                result.append(str[i])
        result = ''.join(result)
        if negtive:
            result ='-' + result
        if has_digit:
            if int(result) > 2**31 -1:
                return(2147483647)
            if int(result) < -2**31:
                return(-2**31)
            return(int(result))
        else:
            return(0)

Search Insert Position

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

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be inserted
    # @return integer
    def searchInsert(self, A, target):
        for i in range(len(A)):
            if A[i] >= target:
                return(i)
            if A[len(A) - 1] < target:
                return(len(A))

Balanced Binary Tree

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

# 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 boolean
    def isBalanced(self, root):
        if root == None:
            return(True)
        return(self.getDepth(root) != -100)
    def getDepth(self, root):
        if root == None:
            return(0)
        l = self.getDepth(root.left)
        r = self.getDepth(root.right)
        if l == -100  or r == -100 or abs(l-r) > 1:
            return(-100)
        return(1 + max(l,r))

Letter Combinations of a Phone Number

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

class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        if digits == '':
            return([''])
        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']}
        for i in range(len(digits)):
            if digits[i] == '1' or digits[i] == '0':
                continue
            digits = digits[i:len(digits)]
            break
        result = dic[digits[0]]
        for i in range(1,len(digits)):
            if digits[i] == '1' or digits[i] == '0':
                continue
            tmp1 = []
            for j in range(len(result)):
                for k in range(len(dic[digits[i]])):
                    tmp1.append(result[j] + dic[digits[i]][k])
            result = tmp1
        return(result)

Swap Nodes in Pairs

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

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

Excel Sheet Column Number

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

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

Gray Code

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

class Solution:
    # @return a list of integers
    def grayCode(self, n):
        tmp = ['0', '1']
        if n == 0:
            return([0])
        if n == 1:
            return(self.convert2integer(tmp))
        result = []
        for i in range(n - 1):
            for j in tmp:
                result.append('0' + j)
            for j in tmp[::-1]:
                result.append('1' + j)
            tmp = result
            result = []
        return(self.convert2integer(tmp))
    def convert2integer(self, tmp):
        tt = []
        for i in tmp:
            result = int(i[0])
            for j in range(1,len(i)):
                result =  2*result + int(i[j])
            tt.append(result)
        return(tt)