Review List 4

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = {}
start = 0
res = 0
for i,c in enumerate(s):
if c in used and used[c]>=start:
start = used[c]+1
else:
res=max(res, i-start+1)
used[c] = i
return res
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:return -1
l, r = 0, len(nums)-1
while l<=r:
m = (l+r)//2
if target==nums[m]:return m
if nums[l]<=nums[m]:
if nums[l]<=target<nums[m]:
r = m-1
else:
l = m+1
else: # nums[l]>=nums[m]
if nums[m]<target<=nums[r]:
l = m+1
else:
r = m-1
return -1
class Solution:
def maxTurbulenceSize(self, A: List[int]) -> int:
if not A:return 0
dp = [[0]*2 for i in range(len(A))]
for i in range(1, len(A)):
if A[i]>A[i-1]:
dp[i][0] = 1 if dp[i-1][1]==0 else dp[i-1][1]+1
elif A[i] < A[i-1]:
dp[i][1] = 1 if dp[i-1][0]==0 else dp[i-1][0]+1
return max([max(d) for d in dp])+1
class Solution:
def maxTurbulenceSize(self, A: List[int]) -> int:
if not A:return 0
if len(A)==1:return 1
best, best_sofa = 0, 0
if len(A)>=2:best_sofa=best= 1 if A[0]==A[1] else 2

for i in range(2, len(A)):
if (A[i-2] <A[i-1]> A[i]) or (A[i-2] > A[i-1] <A[i]):
best_sofa += 1
else:
if A[i-1]!=A[i]:
best_sofa = 2
else:
best_sofa = 1
best = max(best, best_sofa)
return best
class Solution:
def twoSumLessThanK(self, A: List[int], K: int) -> int:
A.sort()
l, r = 0 , len(A)-1
res = -1
while l<r:
a, b = A[l], A[r]
ab = a+b
if ab>=K:
while l<r and A[r-1]==A[r]:
r -= 1
r -= 1
else:
res = max(res, ab)
while l<r and A[l+1]==A[l]:
l += 1
l += 1
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
if not root1 or not root2:return False
a = set()
def collect_values(node):
if node is None:return
a.add(node.val)
collect_values(node.left)
collect_values(node.right)
collect_values(root1)
def check(node):
if node is None:return False
if target-node.val in a:return True
return check(node.left) or check(node.right)
return check(root2)
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
#seen = set()
if start==destination:return True
R, C = len(maze), len(maze[0])
def dfs():
open_list = [start]
seen = {tuple(start)}
while open_list:
i,j = open_list.pop()
for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
r, c = i+di, j+dj
while 0<=r<R and 0<=c<C and maze[r][c]!=1:
r, c = r+di, c+dj
r, c =r-di, c-dj
if (r,c) not in seen:
if [r,c]==destination:return True
seen.add((r,c))
open_list.append((r,c))
return False
return dfs()
class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height)<=1:return 0
res = 0
l, r = 0, len(height)-1
while l<r:
a, b = height[l], height[r]
res = max(res, (r-l)*min(a,b))
if a<b:
l+=1
else:
r-=1
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
"""
if root is None:return ""
nodes = []
def preorder(node):
if node is None:return
nodes.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
return ','.join(nodes)
def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.
"""
if not data:return None
vals = collections.deque(data.split(','))
def build(min_val=-float('inf'), max_val=float('inf')):
if vals and min_val<int(vals[0])<max_val:
val = int(vals.popleft())
root = TreeNode(val)
root.left = build(min_val, val)
root.right = build(val, max_val)
return root
return build()
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store