# 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 = Noneclass 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 = Noneclass 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))`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.