Review List 4

3. Longest Substring Without Repeating Characters

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

33. Search in Rotated Sorted Array

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

978. Longest Turbulent Subarray

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

A more concise one

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

1099. Two Sum Less Than K

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

1214. Two Sum BSTs

# 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)

490. The Maze

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()

11. Container With Most Water

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

449. Serialize and Deserialize BST

# 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))