Day 3. 02/10/20

[tech-cow]

• 278 First Bad Version
• 349/350. Intersection of Two Arrays II (Check 350 Follow up questions)
• 491. Increasing Subsequences

[tech-cow]

278. First Bad Version

'''
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

[7:20] START

Problem Solving:
Linear Scan -> Binary Search
[7:24] Bug-free
'''
class Solution(object):
    def firstBadVersion(self, n):
        left , right = 1, n
        while left + 1 < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid
        
        if isBadVersion(left): return left
        return right'''
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

[7:20] START

Problem Solving:
Linear Scan -> Binary Search
[7:24] Bug-free
'''
class Solution(object):
    def firstBadVersion(self, n):
        left , right = 1, n
        while left + 1 < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid
        
        if isBadVersion(left): return left
        return right

[tech-cow]

491. Increasing Subsequences

'''
Bug 1: 这里如果 == base case底端，很多过程中的case都不会被记录
if index == len(nums) and len(temp) >= 2:

疑问：
为什么会有[4,7,7]这个output，set不会把第二个7去重么？

答:
每层递归的都会开一次新的set，而不是globalSet。所以只会针对当前层的duplicate
比如arr = [4,7,7]
    arr[1]是第二层的
    arr[2]是第三层的，到达第三层的时候，新开辟的set里面不会有第二层的7
'''
    
class Solution(object):
    def findSubsequences(self, nums):
        res = []
        self.dfsHelper(nums, [], 0, res)
        return res
    
    
    def dfsHelper(self, nums, temp, index, res):
        # Bug 1
        if index <= len(nums) and len(temp) >= 2:
            res.append(temp[:])

        visited = set()
        for i in range(index, len(nums)):
            if temp and temp[-1] > nums[i]: continue
            if nums[i] in visited: continue
            visited.add(nums[i])
            
            temp.append(nums[i])
            self.dfsHelper(nums, temp, i + 1, res)
            temp.pop()
        

[tech-cow]

349. Intersection of Two Arrays

class Solution(object):
    def intersection(self, nums1, nums2):
        nums1 = set(nums1)
        nums2 = set(nums2)
        res = []
        
        for num in nums1:
            if num in nums2:
                res.append(num)
        return res

Follow up

350 Intersection of Two Arrays II

Bugfree in 3 mins using 2 pointers. Pretend the arrays are sorted.
Time: O(N) if array given are sorted
Space: O(1)

class Solution(object):
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        
        i, j = 0, 0
        m, n = len(nums1), len(nums2)
        res = []
        
        while i < m and j < n:
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1; j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return res

350 Intersection of Two Arrays II -> Binary Search

class Solution(object):
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        
        if len(nums1) < len(nums2):
            shortNums = nums1 ; longNums = nums2
        else:
            shortNums = nums2 ; longNums = nums1
            
        res = []
        left, right = 0, len(longNums)
        for ele in shortNums:
            index = self.binarySearch(longNums, res, left, right, ele)
            if index != -1:
                left = index + 1
                res.append(longNums[index])
        return res

    
    def binarySearch(self, longNums, res, left, right, target):
        while left + 1 < right:
            mid = (left + right) // 2
            if longNums[mid] == target:
                right = mid
            elif longNums[mid] < target:
                left = mid
            else:
                right = mid
        
        if left < len(longNums) and longNums[left] == target:
            return left
        if right < len(longNums) and longNums[right] == target:
            return right
        return -1