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

# LeetCode 题解四（python版）

LeetCode Python

Markdown版请移步

## Binary Tree Level Order 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 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

# 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 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

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)

1. 所有不能转换为字符串的都返回0
2. 出现多个+-号则不能转化，如++2不能转成2
3. 当所表示字符串大于2^31-1或小于-2^31时，返回2^31-1或小于-2^31
4. +-号后面必须接数字，否则返回0
5. " +0 123"应返回0，而不是123

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

# 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 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

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

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

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)

• 私有
• 公开
• 删除