141. Linked List Cycle (Easy)
Given head, the head of a linked list, determine if the linked list has a cycle in it.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head: return False
slow=head
fast=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return False
142. Linked List Cycle II (Medium)
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head: return head
fast=slow=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if fast==slow:
if fast==head: return head
fast = head
while fast:
fast=fast.next
slow=slow.next
if fast==slow:
return slow
return None
注意 if fastslow: 时候 if fasthead: return head 情况。
143. Reorder List (Medium)
You are given the head of a singly linked-list. The list can be represented as:0 1 2 3 4 ..n, reorder as 0 n 1 n-1 2 n-2 ...
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return None
if head and head.next and not head.next.next : return head
if head and not head.next: return head
cur=head
tail_pre=None
while cur.next:
tail_pre=cur
cur=cur.next
tail=cur
headnext = head.next
tail_pre.next=None
head.next=tail
tail.next=self.reorderList(headnext)
return head
# answer 思路 writing
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
def rev(head):
pre=None
while head:
headnext=head.next
head.next=pre
pre=head
head=headnext
return pre
slow=fast=head
pre_slow=None
while fast and fast.next:
pre_slow=slow
slow=slow.next
fast=fast.next.next
pre_mid = pre_slow
mid=slow
odd_head = rev(mid)
#merge two
first, second = head, odd_head
while second.next:
tmp=first.next
first.next=second
first=tmp
tmp=second.next
second.next=first
second=tmp
# using Stack, odd/even is solved by len(stack)//2
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return
stack = []
cur =head
while cur:
stack.append(cur)
cur =cur.next
cur = head
for i in range(len(stack)//2):
next = cur.next
endnode = stack.pop()
cur.next = endnode
endnode.next = next
cur = next
cur.next = None
第一次尝试，time limit exceeded，base case： node为空，2个node，一个node情况。 然后暴力求解即可.T（n）= T（n-2）+1 所以时间复杂度 1+2+3.。。+n = O（n*n）
第二次尝试放弃了， 思路： 找到mid， rev（mid）， merge 2个list。
144. Binary Tree Preorder Traversal （Easy）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res=[]
def pre(root):
if not root: return
res.append(root.val)
pre(root.left)
pre(root.right)
pre(root)
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res=[]
stack = []
while stack or root:
while root:
res.append(root.val)
stack.append(root)
root=root.left
node=stack.pop()
root=node.right
return res
145. Binary Tree Postorder Traversal （Easy）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res=[]
def post(root):
if not root:return
post(root.left)
post(root.right)
res.append(root.val)
post(root)
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack=[]
result=[]
stack.append(root)
while stack:
cur=stack.pop()
result.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
return result[::-1]
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
while root or stack:
while root:
stack.append(root)
res.append(root.val)
root =root.right
root = stack.pop()
root =root.left
return res[::-1]
左右子树颠倒的前序遍历取反向就是正常树的后序遍历。
146. LRU Cache （Medium）
class Node:
def __init__(self,key,val,next=None,pre=None):
self.key=key
self.val=val
self.next=next
self.pre=pre
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.n=0
self.map_key_node=dict()
self.head = Node(key='NULL',val='NULL')
self.tail = Node(key='NULL',val='NULL')
self.head.next = self.tail
self.tail.pre = self.head
def debug(self,disable=True):
if not disable:
cur=self.head
tmp=[]
while cur:
tmp.append('('+str(cur.key)+','+str(cur.val)+')')
cur=cur.next
print(','.join(tmp))
cur=self.tail
tmp=[]
while cur:
tmp.append('('+str(cur.key)+','+str(cur.val)+')')
cur=cur.pre
print(','.join(tmp[::-1]))
def get(self, key: int) -> int:
print('get',key)
if key in self.map_key_node:
#pop from linked list
node = self.map_key_node[key]
node.pre.next=node.next
node.next.pre = node.pre
#add from head
headnext=self.head.next
node.pre= self.head
self.head.next=node
node.next=headnext
headnext.pre=node
self.debug()
return self.map_key_node[key].val
else:
self.debug()
return -1
def put(self, key: int, value: int) -> None:
print('put',key,value)
if key in self.map_key_node:
#if key in cache, update value & move to top of linked list
self.map_key_node[key].val=value
self.get(key)
else:
#add key-val pair to cache
self.map_key_node[key]= Node(key=key,val=value)
self.n = self.n+1
if self.n > self.cap:
# evict least recently used key
# pop from tail
to_be_del = self.tail.pre
to_be_del.pre.next= self.tail
self.tail.pre= to_be_del.pre
del self.map_key_node[to_be_del.key]
#add from head
headnext = self.head.next
self.head.next=self.map_key_node[key]
self.map_key_node[key].pre=self.head
headnext.pre=self.map_key_node[key]
self.map_key_node[key].next=headnext
#update n
self.n = self.n-1
else:
#put <=cap append from head
headnext = self.head.next
self.head.next=self.map_key_node[key]
self.map_key_node[key].pre=self.head
headnext.pre = self.map_key_node[key]
self.map_key_node[key].next=headnext
self.debug()
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# double directed linkedlist
# dict key-> Node (put get update value)
# put
# <= cap just append to linked from head. head new old1 old2..
# > cap pop from tail put from head
# get pop() then put to head
class Node:
def __init__(self,key, val,next=None,pre=None):
self.val =val
self.next =next
self.pre = pre
self.key = key
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.n = 0
self.map = dict() #based on key find the node
self.head = Node('HEAD',"HEAD")
self.tail = Node('TAIL',"TAIL")
self.head.next = self.tail
self.tail.pre = self.head
def put2head(self,node):
headnext = self.head.next
self.head.next = node
node.pre = self.head
headnext.pre =node
node.next =headnext
def get(self, key: int) -> int:
if key in self.map:
node = self.map[key]
node.pre.next = node.next
node.next.pre = node.pre
self.put2head(node)
return node.val
else:
return -1
def remove_lru(self):
node = self.tail.pre
node.pre.next = self.tail
self.tail.pre = node.pre
del self.map[node.key]
def put(self, key: int, value: int) -> None:
if key in self.map:
self.map[key].val = value
self.get(key)
else:
self.map[key] = Node(key,value)
self.n+=1
if self.n>self.cap:
self.remove_lru()
self.n-=1
self.put2head(self.map[key])
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
思路： double linked list + map get：首先pop from linked list 然后 add 到head下一位。 put： 如果小于等于cap，从head开始append，如果大于cap， pop tail 然后add from head。
147. Insertion Sort List （Medium）
Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def insert(node):
pre=None
cur=head_sorted.next
FLAG=False
while cur:
# 6 1
if (pre and node.val<=cur.val and node.val>=pre.val) or (pre is None and cur.val>=node.val):
#do insert
if pre is None:
#insert after head_sorted
head_sorted_next=head_sorted.next
head_sorted.next=node
node.next= head_sorted_next
else:
#normal insertion
pre.next=node
node.next=cur
#after insertion break
FLAG=True
break
pre=cur
cur=cur.next
if not FLAG:
pre.next = node
cur=head.next
head.next=None
head_sorted = ListNode(val='NULL',next=head)
while cur:
curnext = cur.next
cur.next=None
insert(cur)
cur=curnext
return head_sorted.next
#ANSWER
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
dummy = ListNode()
curr = head
while curr:
# At each iteration, we insert an element into the resulting list.
prev = dummy
# find the position to insert the current node
while prev.next and prev.next.val <= curr.val:
prev = prev.next
next = curr.next
# insert the current node to the new list
curr.next = prev.next
prev.next = curr
# moving on to the next iteration
curr = next
return dummy.next
没啥难的，就是细心。 答案很优美。
148. Sort List （Medium）
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# nlogn compare method
# O(1) space
# merge sort
def merge(l1,l2):
#print('l1')
#print(l1)
#print('l2')
#print(l2)
dummy_head = ListNode(val='NULL')
cur=dummy_head
while l1 and l2:
if l1.val<l2.val:
cur.next=l1
l1=l1.next if l1 else None
else:
cur.next=l2
l2=l2.next if l2 else None
cur=cur.next
if l1:
cur.next=l1
if l2:
cur.next=l2
#print('res')
#print(dummy_head.next)
return dummy_head.next
def sort(head):
if (not head) or (not head.next): return head
slow=fast=head
pre=None
while fast and fast.next:
pre=slow
slow=slow.next
fast=fast.next.next
pre.next=None
mid =slow
l1=sort(mid)
l2=sort(head)
return merge(l1,l2)
return sort(head)
149. Max Points on a Line (Hard)
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
# p1 [x, ax+b]
# p2 [x',ax'+b]
# y1=ax1+b
# y2=ax2+b
# y1-y2=a(x1-x2)
# a = y1-y2/x1-x2
# b = y-ax
dic = collections.defaultdict(set)
n = len(points)
if n==1: return 1
for i in range(n-1):
for j in range(i+1,n):
p1=points[i]
p2=points[j]
a=(p1[1]-p2[1])/(p1[0]-p2[0]) if p1[0]!=p2[0] else None
b = p1[1]-a*p1[0] if a is not None else None
if a is not None:
key = str(a)+'-'+str(b)
else:
key = 'x=constant'+str(p1[0])
dic[key].add(i)
dic[key].add(j)
#print(dic)
return max(map(len,dic.values()))
150. Evaluate Reverse Polish Notation (Medium)
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
numstack = []
for t in tokens:
if t in '+-*/':
#op
num2=numstack.pop()
num1=numstack.pop()
print(t,num1,num2,end=' # ')
if t=='+':
numstack.append(num1+num2)
elif t=='-':
numstack.append(num1-num2)
elif t=='*':
numstack.append(num1*num2)
elif t=='/':
numstack.append(int(num1/num2) )
else:
print(error)
#print(numstack[-1])
else:
numstack.append(int(t))
#print(numstack)
return numstack[0]
注意 int(num1/num2)， int(1.8)=1 int(-1.8)=-1 但是 -2/1.1=-1.8181818181818181 -2//1.1=-2 取整后会更偏小，但是对负数希望的是偏大。对正数希望的是抹去小数偏小。 所以只能取int。