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) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
'''
网友评论