LeetCode 刷题 2019.9.11

第225题 用队列实现栈

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q = collections.deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not len(self.q)

第276题 翻转二叉树

主体思路是用递归的翻转节点，只要节点不为空，便可以交换左右子节点：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root!= None:
            node = root
            node.left, node.right = self.invertTree(root.right), self.invertTree(root.left)
        else:
            return None
        return node

第231题 2的幂

这是做到现在最简单的一题：

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n==1:
            return True
        while n > 1:
            if n/2 == 1:
                return True
            else:
                n /=2
        return False

如果是2的幂的话，二进制只有最高位上是1，其他都是0.所以n-1应该除了最高位是0，其他都是1，所以n&（n-1）为0：

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n>0 and n &(n-1)==0

第232题 用栈实现队列

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        from collections import deque
        self.stack = deque()

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        tmp_stack=[]
        while self.stack:
            tmp_stack.append(self.stack.pop())
        self.stack.append(x)
        while tmp_stack:
            self.stack.append(tmp_stack.pop())

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.stack:
            return self.stack.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.stack:
            return self.stack[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not bool(self.stack)

第234题 回文链表

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        if fast:
            slow = slow.next
        prev = None
        cur = slow
        while cur:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        p1 = head
        p2 = prev
        while p1 and p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True

第235题 二叉树的最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val:
            p, q = q, p
        while True:
            if root.val > q.val:
                root = root.left
            elif root.val < p.val:
                root = root.right
            else:
                return root