@chanvee 2014-12-14T19:29:58.000000Z 字数 7687 阅读 6240

LeetCode 题解二（python版）

LeetCode, Python

Same Tree

这个题的意思非常简单，给定两颗二叉树，判断这两颗二叉树是否相同。树相同包括两点：一是结构相同，而是值相同。因此我们只需要对两棵树同时遍历)(简单的递归)一遍，遇到不同（结构不同或者值不同）时则返回False；若遍历一遍之后没有发现不同则说明这两棵树相同。代码如下：

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param p, a tree node
    # @param q, a tree node
    # @return a boolean
    def isSameTree(self, p, q):  
        if p == None and q == None:
            return(True)
        elif p == None or q == None:
            return(False)
        else:
            if p.val != q.val:
                return(False)
            else:  
                if self.isSameTree(p.left, q.left): 
                    return(self.isSameTree(p.right, q.right))
                else:
                    return(False)

Symmetric Tree

这个题是判断一棵树是不是对称树。我们可以根据上一个题来解决这个问题，先给代码：

# 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 isSymmetric(self, root):
        if root == None:
            return(True)
        else:
            return(self.isSameTree(root.left, root.right))
    def isSameTree(self, p, q):
        if p == None and q == None:
            return(True)
        elif p == None or q == None:
            return(False)
        else:
            if p.val != q.val:
                return(False)
            else:
                if self.isSameTree(p.left, q.right): 
                    return(self.isSameTree(p.right, q.left))
                else:
                    return(False)

有代码可知，我们首先把这个树分成左右两颗子树，然后遍历这两颗子树，比较时不再是左边和左边的比，因为对称，所以比较左子树的左节点和右子树的右节点以及左子树的右节点和右子树的左节点是否相等即可。

Add Two Numbers

这个题目是实现链表的加法，刚开始理解错了，看到题目给的例子以为给的两个列表长度是相等的，其实不是哈，不一定等长。题目本身很简单，值得一提的是python中链表的操作，才开始我硬是没搞清楚，先贴代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # @return a ListNode
    def addTwoNumbers(self, l1, l2):
        add = 0
        l3 = ListNode(0)
        cur = l3
        while l1 or l2:
            node = ListNode(add)
            if l1:
                node.val += l1.val
                l1 = l1.next
            if l2:
                node.val += l2.val
                l2 = l2.next
            if node.val >= 10:
                add = 1
            else:
                add = 0
            node.val %= 10
            cur.next, cur = node, node 
        if add:
            cur.next = ListNode(1)
        return(l3.next)

代码中·cur = l3,表示cur和l3都指向了同一个链表，在另一句cur.next, cur = node, node中，当第一次执行这句话时，首先cur.next指向了node，也代表了l3.next也指向了node，然后cur再指向node，也就是指向了l3的next；当再一次执行时，首先cur.next指向node就相当于l3.next.next指向node,以此类推，从而cur就相当于实现了C中的指针的作用了。

Remove Duplicates from Sorted List

这个题目的意思是去除掉链表中所有重复的元素，即每个元素只保留一次，方法就是遍历这个链表，每次将当前节点的值跟下一个的节点的值相比，如果相同则将当前节点指向下下个节点即可，需要注意的是如果下下个节点没有的话，则当前节点指向None。代码如下：

# 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 ListNode
    def deleteDuplicates(self, head):
        if head == None:
            return(None)
        else:
            cur = ListNode(head.val)
            cur.next, head = head, cur
            while cur:
                if cur.next and cur.val == cur.next.val:
                    if cur.next.next:
                        cur.next = cur.next.next
                    else:
                        cur.next = None
                else:
                    cur = cur.next
            return(head)

Remove Duplicates from Sorted List 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 ListNode
    def deleteDuplicates(self, head):
        if head == None or head.next == None:
            return(head)
        cur = ListNode(head.val)
        cur.next, head = head, cur
        flag = False
        while cur:
            if cur.next and cur.next.next and cur.next.val == cur.next.next.val:
                cur.next = cur.next.next
                flag = True
            elif flag and cur.next:
                cur.next = cur.next.next
                flag = False
            else:
                cur = cur.next
        return(head.next)

Remove Duplicates from Sorted Array

这个题与上面两个题类似，只是有链表变为了指针，需要注意的是虽然题目只要求返回数组的长度，但是它还有一个隐性的要求就是要使得数组A[0：len]是你想要的得到的不包含重复元素的数组，如他给的例子A=[1，1，2],remove 完之后要求A=[1,2,2]，也就是说A[0：2] = [1，2]。我就在这里卡了好久。。。代码如下：

class Solution:
    # @param a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if A == []:
            return(0)
        count = 1
        for i in range(1,len(A)):
            if A[i] != A[i-1]:
                A[count] = A[i]
                count += 1
        return(count)

Remove Duplicates from Sorted Array II

这个题是上个题目的升级版，这是移除数组中重复元素大于2个的元素并返回新数组的长度，思想类似，这里就不在赘述，直接贴代码：

class Solution:
    # @param A a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if len(A) <= 2: 
            return(len(A))
        count = 2
        for i in range(2,len(A)):
            if A[i] != A[count-1] or A[i] != A[count-2]:
                A[count] = A[i]
                count += 1
        return(count)

Pascal's Triangle

题目的意思是生成n行的Pascal's三角并存入到列表中。思路是第i(i>=3)的第j个元素等于第i-1行的第j-1个元素和第j个元素之和，初识化第一二行之后for一下就可以了，另外由于Pascal's三角是对称的，所以我们每次只需算前一半即可。代码如下：

class Solution:
    # @return a list of lists of integers
    def generate(self, numRows):
        if numRows == 1:
            return([[1]])
        elif numRows == 2:
            return([[1],[1,1]])
        elif numRows == 0:
            return([])
        else:
            result = [[1],[1,1]]
            for i in range(3, numRows+1):
                tmp = [1]*i
                last = result[i-2]
                for j in range(1,(i-1)//2 + 1):
                    tmp[j] = tmp[i-1-j] = last[j-1] +last[j]
                result.append(tmp)
            return(result)

Pascal's Triangle II

这个题跟上一个题目类似，只是这次不是全部返回，而是只返回固定的某一行。由于Pascal's三角中的第i行第j个元素

L (i, j) = C j - 1 i = i ! ( j - 1 ) ! ( n - j + 1 ) !

$L(i,j) = C_i^{j-1}=\frac{i!}{(j-1)!(n-j+1)!}$ ,所有我们就可以很简单得到任意一行的值了，只需再添加一个计算阶乘的函数，代码如下：

class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        result = [1]*(rowIndex + 1)
        for i in range(1,(rowIndex)//2 + 1):
            result[i] = result[rowIndex-i] = self.factorial(rowIndex)//(self.factorial(i)*self.factorial(rowIndex-i))
        return(result)
    def factorial(self, n):
        if n == 1:
            return(1)
        else:
            return(n*self.factorial(n-1))

Minimum Depth of Binary Tree

这个题目是计算一颗二叉树的最小深度，分别计算左右子树的深度，然后取较小，深度的计算方法是如果节点是叶子节点深度加1，如果节点有子节点深度加1，初识化左右子树深度为无穷大。代码如下：

# 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 an integer
    def minDepth(self, root):
        if root == None:
            return(0)
        if root.left == None and root.right == None:
            return(1)
        left = right = float("inf") # 表示无穷大
        if root.left != None:
            left = 1 + self.minDepth(root.left)
        if root.right != None:
            right = 1 + self.minDepth(root.right)
        return(min(left, right))

Maximum Depth of Binary Tree

与上题类似，只不过是找树的最大深度，改一下判别条件就可以了。代码如下：

# 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 an integer
    def maxDepth(self, root):
        if root == None:
            return(0)
        if root.left == None and root.right == None:
            return(1)
        left = right = -1
        if root.left != None:
            left = 1 + self.maxDepth(root.left)
        if root.right != None:
            right = 1 + self.maxDepth(root.right)
        return(max(left, right))

Path Sum

这个题的意思是一颗二叉树上是否存在一条从根节点到叶子节点的路径，其上所有节点之和等于一个指定的数。方法就是当我们从根节点往下递归时，看当前节点是否存在sum减去前面节点之和的路径存在。代码如下：

# 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
    # @param sum, an integer
    # @return a boolean
    def hasPathSum(self, root, sum):
        result = False
        if root == None:
            return(result)
        else:
            sum -= root.val
            if sum == 0 and root.left == None and root.right == None:
                result = True
                return(result)
            else:
                if root.left:
                    result = result or self.hasPathSum(root.left, sum) # 只要存在一条就返回True
                if root.right:
                    result = result or self.hasPathSum(root.right, sum)
                return(result)

Length of Last Word

求一行字符串中最后一个单词的长度，这个题用python做就非常简单了，代码如下：

class Solution:
    # @param s, a string
    # @return an integer
    def lengthOfLastWord(self, s):
        if s == '':
            return(0)
        result = s.split()
        if result == []:
            return(0)
        return(len(result[-1]))

Add Binary

这个题目非常简单，就是二进制的加法。对于我们这种python的初学者来说难点是字符串与列表的转化，题目本身需要注意的一个地方就是，最后可能由于进位需要补一位，我们可以先把字符串先倒一转再加，这样就可以在末尾补位。代码如下：

class Solution:
    # @param a, a string
    # @param b, a string
    # @return a string
    def addBinary(self, a, b):
        a = a[::-1] # 字符串倒序
        b = b[::-1] # 字符串倒序
        i = j = 0
        c = []
        add = 0 # 表示进位
        while i < len(a) or j < len(b):
            if i < len(a) and j < len(b):
                tmp = (int(a[i]) + int(b[j]) + add) % 2
                c.append(str(tmp))
                if (int(a[i]) + int(b[j]) + add) >= 2:
                    add = 1
                else:
                    add = 0
                i += 1
                j += 1
            if i < len(a) and j>= len(b):
                tmp = (int(a[i]) + add)%2
                c.append(str(tmp))
                if (int(a[i]) + add) >= 2:
                    add = 1
                else:
                    add = 0
                i += 1
            if i >= len(a) and j < len(b):
                tmp = (int(b[j]) + add)%2
                c.append(str(tmp))
                if (int(b[j]) + add) >= 2:
                    add = 1
                else:
                    add = 0
                j += 1
        if add:
            c.append('1')
        c = c[::-1]
        result = "".join(c)
        return(result)

Valid Parentheses

这道题是判断括号是否匹配，就是利用栈来进行解决，遇到正括号加入栈，遇到反括号弹出栈看是否匹配，只不过刚开始时可以直接排除一些结果：1）如果字符串的长度为奇数，必然False；2）如果最后一个字符是‘（’‘[’‘{’，必然false；3）第一个字符为‘）’‘]’‘}’必然False等。代码如下：

class Solution:
    # @return a boolean
    def isValid(self, s):
        if len(s)%2 != 0 or s[-1] == '(' or s[-1] =='[' or s[-1] =='{':
            return(False)
        result = True
        a = []
        for i in range(len(s)):
            if s[i] =='(' or s[i] =='[' or s[i] =='{':
                a.append(s[i])
            else:
                if len(a) == 0:
                    result = False
                    break
                if s[i] == ')':
                    if a.pop() != '(':
                        result = False
                        break
                if s[i] == ']':
                    if a.pop() != '[':
                        result = False
                        break
                if s[i] == '}':
                    if a.pop() != '{':
                        result = False
                        break
        return(result)