Skip to content
Misc problems
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
l = 0
r = len(nums)
ll = self.binaryLeftSearch(nums, target, l, r)
rr = self.binaryRightSearch(nums, target, l, r)
if ll < 0 or rr >= len(nums) or ll >= len(nums) or rr < 0 or nums[ll] != target:
return [-1, -1]
return [ll, rr]
def binaryRightSearch(self, nums, target, l, r):
m = 0
while l < r:
m = (l + r) // 2
if nums[m] > target:
r = m
else:
l = m + 1
return l - 1
def binaryLeftSearch(self, nums, target, l, r):
m = 0
while l < r:
m = (l + r) // 2
if nums[m] < target:
l = m + 1
else:
r = m
return r
"""
1 2 3 4 5 5 5 5 5 5 5 5 5 5. 5 5 5 5 5 5 5 5 5 5 5. 5 5 6 7 8
^
"""
class ListNode:
def __init__(self, val, key, next = None, prev = None):
self.val = val
self.key = key
self.next = next
self.prev = prev
class DoubleLinkedList:
def __init__(self):
self.head = None
self.tail = None
def add(self, node: ListNode):
if self.head is None:
self.head = node
self.tail = node
else:
prevHead = self.head
self.head.next = node
self.head = node
self.head.prev = prevHead
prevHead.next = self.head
def remove(self, node: ListNode):
if self.head == self.tail:
self.head = None
self.tail = None
elif node is self.tail:
node.next.prev = None
self.tail = node.next
node.prev = None
elif node is self.head:
node.prev.next = None
self.head = node.prev
else:
node.prev.next = node.next
node.next.prev = node.prev
return node
"""
prev node next
[a] -> [b] -> [d] -> [c] -> [d]
tail head
"""
class LRUCache:
def __init__(self, capacity: int):
self.m = {}
self.count = 0
self.capacity = capacity
self.list = DoubleLinkedList()
def get(self, key: int) -> int:
if key not in self.m:
return -1
node = self.m[key]
self.list.remove(node)
self.list.add(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.m:
self.list.remove(self.m[key])
else:
if self.count == self.capacity:
node = self.list.remove(self.list.tail)
del self.m[node.key]
else:
self.count += 1
node = ListNode(value, key)
self.m[key] = node
self.list.add(node)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ··· in the right corner or using a keyboard shortcut (
CtrlP
) instead.