头像

acwing_827




离线:4个月前



acwing_827
2019-09-04 11:48
class Solution:
    def verifySequenceOfBST(self, sequence):
        """
        :type sequence: List[int]
        :rtype: bool
        """
        if len(sequence) <2:
            return True

        for i in range(len(sequence)-1):
            if sequence[i] > sequence[-1]:
                for j in range(i,len(sequence)-1):
                    if sequence[j] < sequence[-1]:
                        return False
                return self.verifySequenceOfBST(sequence[:i]) and self.verifySequenceOfBST(sequence[i:-1])
        return True #别忘记这句



acwing_827
2019-09-04 09:41
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        row, res = [], []
        if not root: return []
        q = [root]
        i = 1
        while q:
            node = q.pop(0)
            i-=1
            row.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            if i == 0:
                res.append(row)
                row=[]
                i = len(q)
        return res        



acwing_827
2019-09-04 09:35
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root: return []
        q = [root]
        while q:
            node = q.pop(0)
            res.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        return res



acwing_827
2019-09-04 08:32
class Solution(object):
    def printMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # 方法一:通过旋转矩阵不断输出第一行
        if matrix:
            top_row = list(matrix[0])
            array = list(zip(*matrix[1:]))[::-1]
            return top_row + self.printMatrix(array)
        return []

        #方法二:顺时针对矩阵 pop()
        res = []
        while matrix:
            res += matrix.pop(0)
            if matrix and matrix[0]:
                for row in matrix:
                    res.append(row.pop())
            if matrix:
                res += matrix.pop()[::-1]
            if matrix and matrix[0]:
                for row in matrix[::-1]:
                    res.append(row.pop(0))
        return res



acwing_827
2019-09-04 07:38
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True
        return self.isMirror(root.left, root.right)

    def isMirror(self, l, r):
        if not l and not r: return True
        if not l or not r or l.val!=r.val: return False
        return self.isMirror(l.left, r.right) and self.isMirror(l.right, r.left)




acwing_827
2019-09-04 07:24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def mirror(self, root):
        """
        :type root: TreeNode
        :rtype: void
        """
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.mirror(root.left)
        self.mirror(root.right)




acwing_827
2019-09-04 06:15
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def merge(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1: 
            return l2
        if not l2: 
            return l1

        if l1.val < l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l1, l2.next)
            return l2





acwing_827
2019-09-04 06:02
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head

        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node



acwing_827
2019-09-04 03:58
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def entryNodeOfLoop(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None

        #进入环内
        h = head.next
        t = head
        while h and t and h!=t:
            if not h.next:
                return None
            h = h.next.next
            t = t.next
        if not h or not t:
            return None

        #算环长
        k=1
        h = h.next
        while h!=t:
            h = h.next
            k+=1
        # print(k)

        #找入口
        h, t= head, head
        for i in range(k):
            h = h.next
        while h!=t:
            h = h.next
            t = t.next

        return h




acwing_827
2019-09-04 03:07
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#递归返回
class Solution(object):
    p = 0
    def findKthToTail(self, pListHead, k):
        """
        :type pListHead: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not pListHead:
            return None
        node = self.findKthToTail(pListHead.next, k)
        if node:
            return node

        self.p+=1
        if self.p == k:
            return pListHead
        return None