Maximum Sum Circular Subarray:
class Solution(object):
def maxSubarraySumCircular(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def kadane(array):
max_sum = curr_max = array[0]
for num in array[1:]:
curr_max = max(num, curr_max + num)
max_sum = max(max_sum, curr_max)
return max_sum
total_sum = sum(nums)
max_kadane = kadane(nums)
min_kadane = kadane([-num for num in nums])
if max_kadane > 0:
return max(max_kadane, total_sum + min_kadane)
return max_kadane
Stamping The Sequence:
class Solution(object):
def movesToStamp(self, stamp, target):
stamp_len = len(stamp)
target_len = len(target)
target = list(target)
result = []
visited = [False] * target_len
stars = 0
def can_stamp(pos):
for i in range(stamp_len):
if target[pos + i] != '?' and target[pos + i] != stamp[i]:
return False
return True
def do_stamp(pos):
count = 0
for i in range(stamp_len):
if target[pos + i] != '?':
target[pos + i] = '?'
count += 1
return count
while stars < target_len:
stamped = False
for i in range(target_len - stamp_len + 1):
if not visited[i] and can_stamp(i):
stars += do_stamp(i)
visited[i] = True
[Link](i)
stamped = True
if stars == target_len:
break
if not stamped:
return []
return result[::-1]
Design Browser History:
class BrowserHistory(object):
def __init__(self, homepage):
"""
:type homepage: str
"""
[Link] = [homepage]
self.current_index = 0
def visit(self, url):
"""
:type url: str
:rtype: None
"""
[Link] = [Link][:self.current_index + 1]
[Link](url)
self.current_index += 1
def back(self, steps):
"""
:type steps: int
:rtype: str
"""
self.current_index = max(0, self.current_index - steps)
return [Link][self.current_index]
def forward(self, steps):
"""
:type steps: int
:rtype: str
"""
self.current_index = min(len([Link]) - 1, self.current_index + steps)
return [Link][self.current_index]
browserHistory = BrowserHistory("[Link]")
[Link]("[Link]")
[Link]("[Link]")
[Link]("[Link]")
print([Link](1))
print([Link](1))
print([Link](1))
[Link]("[Link]")
print([Link](2))
print([Link](2))
print([Link](7))
LRU Cache:
class Node:
"""Doubly linked list node."""
def __init__(self, key, value):
[Link] = key
[Link] = value
[Link] = None
[Link] = None
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
[Link] = capacity
[Link] = {}
[Link] = Node(0, 0)
[Link] = Node(0, 0)
[Link] = [Link]
[Link] = [Link]
def _remove(self, node):
"""Remove a node from the linked list."""
prev_node = [Link]
next_node = [Link]
prev_node.next = next_node
next_node.prev = prev_node
def _add_to_head(self, node):
"""Add a node right after the head."""
[Link] = [Link]
[Link] = [Link]
[Link] = node
[Link] = node
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in [Link]:
node = [Link][key]
self._remove(node)
self._add_to_head(node)
return [Link]
return -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in [Link]:
node = [Link][key]
self._remove(node)
elif len([Link]) >= [Link]:
lru_node = [Link]
self._remove(lru_node)
del [Link][lru_node.key]
new_node = Node(key, value)
self._add_to_head(new_node)
[Link][key] = new_node
lRUCache = LRUCache(2)
[Link](1, 1)
[Link](2, 2)
print([Link](1))
[Link](3, 3)
print([Link](2))
[Link](4, 4)
print([Link](1))
print([Link](3))
print([Link](4))