【2019-08-21】leetcode(141-150)

141、环形链表

'''
环形链表
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 
如果 pos 是 -1，则在该链表中没有环。

输入：head = [3,2,0,-4], pos = 1
输出：true

哈希
没完成循环的时候碰到空值，则无环
否则有环
'''
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        while  head.next and head.val !=None:
            head.val=None
            head=head.next
        if not head.next:
            return False
        return True

#快慢指针
#慢指针一次一步，快指针一次两步，快慢指针能相遇则有环，否则无
class Solution(object):
    def hasCycle(self, head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return True
        return False

142、环形链表II

'''
环形链表
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

'''
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#哈希表
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        visited = set()

        node = head
        while node is not None:
            if node in visited:
                return node
            else:
                visited.add(node)
                node = node.next
        return None


#Floyd 算法
class Solution(object):
    def getIntersect(self, head):
        tortoise = head
        hare = head

        # A fast pointer will either loop around a cycle and meet the slow
        # pointer or reach the `null` at the end of a non-cyclic list.
        while hare is not None and hare.next is not None:
            tortoise = tortoise.next
            hare = hare.next.next
            if tortoise == hare:
                return tortoise

        return None

    def detectCycle(self, head):
        if head is None:
            return None

        # If there is a cycle, the fast/slow pointers will intersect at some
        # node. Otherwise, there is no cycle, so we cannot find an e***ance to
        # a cycle.
        intersect = self.getIntersect(head)
        if intersect is None:
            return None

        # To find the e***ance to the cycle, we have two pointers traverse at
        # the same speed -- one from the front of the list, and the other from
        # the point of intersection.
        ptr1 = head
        ptr2 = intersect
        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next

        return ptr1

143、重排链表

'''
重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

栈
'''
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        p=head
        stack=[]
        while p:
            stack.append(p)
            p=p.next
        n=len(stack)
        count=(n-1)//2
        p=head
        while count:
            tmp=stack.pop()
            tmp.next=p.next
            p.next=tmp
            count-=1
        stack.pop().next = None


'''
双指针
(1)找中点
(2)翻转
(3)拼接
'''
class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return head
        fast=head
        pre_mid=head
        while fast.next and fast.next.next:
            pre_mid=pre_mid.next
            fast=fast.next.next
        pre=None
        cur=pre_mid.next
        while cur:
            tmp=cur.next
            cur.next=pre
            pre=cur
            cur=tmp
        pre_mid.next=pre
        p1=head
        p2=pre_mid.next
        while p1!=pre_mid:
            pre_mid.next=p2.next
            p2.next=p1.next
            p1.next=p2
            p1=p2.next
            p2=pre_mid.next

144、二叉树的前序遍历

'''
二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。

根--左--右


'''
# 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 preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def helper(root):
            if not root:
                return
            res.append(root.val)
            helper(root.left)
            helper(root.right)
        helper(root)
        return res
        
'''
迭代
'''
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        p=root
        stack=[]
        while p or stack:
            while p:
                res.append(p.val)
                stack.append(p)
                p=p.left
            p=stack.pop().right
        return res

145、二叉树后序遍历

'''
二叉树后序遍历

左--右--根

深度优先搜索（DFS）

'''
# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack,output=[root,],[]
        while stack:
            root=stack.pop()
            output.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
        return output[::-1]

146、LRU缓存机制

'''
运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
'''