Day 1 | 6/24

[tech-cow]

今日任务 (Binary Search)

• 总结基础Binary Search模板，Iterative 以及 Recursive
• 刷题

Leetcode Easy

852 Peak Index in a Mountain Array 70.1% Easy
349 Intersection of Two Arrays 48.5% Easy
167 Two Sum II - Input array is sorted 47.3% Easy
350 Intersection of Two Arrays II 44.2% Easy
744 Find Smallest Letter Greater Than Target 43.5% Easy

[tech-cow]

Iterative

Binary Search基础实现1，包括End区间，end inclusive

def binarySearch(arr, target):
    '''
    定义：在[l...r]的范围里寻找target, 因为这里定义是需要将r归入范围区间, inclusive，所以while循环的边界需要包含r
    '''
    l , r = 0, len(arr) - 1  
    while l <= r:            

        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1   # 明确区间的要求，只要使用过的，一律绕过。
        else:
            r = mid - 1   # 明确区间的要求，只要使用过的，一律绕过。
    return -1
            

Binary Search基础实现2，不包括End区间, end exclusive

def binarySearch(arr, target):
    '''
    定义：在[l...r)的范围里寻找target, 因为这里定义是不需要将end归入范围区间
    exclusive，所以while循环的边界小于End即可，因为length本身长度会比index大1
    相对应的，每次target的value小于arr[mid]的时候，我们在重新定义新的end时候，
    也选择exclusive的模式，r = mid即可
    '''
    l , r = 0, len(arr)
    while l < r:            
        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1  
        else:
            r = mid
    return -1
            

上述代码仍可能产生溢出的Bug，下面方法为无Bug的标准写法

溢出bug的解释: When you add two signed 32-bit integers, you always run the risk of overflow. You can try it yourself with low = 1 and high = Integer.MAX_VALUE. You'll notice however that the second way stops this overflow from occurring, and you get your expected result.

def binarySearch(arr, target):
    '''
    针对mid加法溢出bug的解决方案：将(l+r)/2 变成 l + (r-l)/2 来避免加法之后的除法
    '''
    l , r = 0, len(arr) - 1  
    while l <= r:            

        mid = l + (r - l) // 2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1   # 明确区间的要求，只要使用过的，一律绕过。
        else:
            r = mid - 1   # 明确区间的要求，只要使用过的，一律绕过。
    return -1

Recursive

class Solution:
    def findPosition(self, nums, target):
        return self.binarySearch(nums, 0, len(nums) - 1, target)
    
    def binarySearch(self, nums, start, end, target):
        if start > end: 
            return -1
        mid = start + (end - start)// 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            return self.binarySearch(nums, mid+1, end, target)
        else:
            return self.binarySearch(nums, start, mid-1 , target)

[tech-cow]

Leetcode 208: Move Zeroes

暴力解法:

时间O(N)
空间O(N)

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        zero = []
        for i, num in enumerate(nums):
            if nums[i] == 0:
                zero.append(i)
        for index in zero[::-1]:
            nums.pop(index) 
        for i in range(len(zero)):
            nums.append(0) 

Two Pointer Slow Runner解法

时间O(N)
空间O(1)

创建一个Slow Pointer记录0的位置，Fast Pointer遇到0的时候跳过，遇到非0的时候，Index对应的Value和之前Slow Pointer的Value对换，然后Slower Pointer++.

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        slow = 0
        for i , num in enumerate(nums):
            if num != 0:
                nums[i], nums[slow] = nums[slow], nums[i]
                slow += 1

[tech-cow]

852. Peak Index in a Mountain Array

Brute Force
Time O(N)
Space O(1)

class Solution:
    def peakIndexInMountainArray(self, arr):
        """
        :type A: List[int]
        :rtype: int
        """
        return arr.index(max(arr))

Binary Search
Time O(LOGN)
Space O(1)
这道题的数组在某种意义上是Sorted，我们要求的是Peak值。
三种可能：

• 如果mid的值比mid-1大，比mid+1小：

  • 证明mid的位置处在上升位置，这时候就将left更新为mid+1

• 如果mid的值比mid-1小，比mid+1大：

  • 证明mid的位置处于下落位置，就将right的更新为mid-1

• 如果比左边大，又比右边大，那我们就抵达了封顶，从此人生巅峰不再需要刷题。

class Solution:
    def peakIndexInMountainArray(self, nums):
        """
        :type A: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        
        l , r = 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid-1] < nums[mid] > nums[mid+1]:
                return nums[mid]
            if nums[mid-1] < nums[mid] < nums[mid+1]:
                l = mid + 1
            else:
                r = mid - 1

[tech-cow]

349. Intersection of Two Arrays
Binary Search
Time O(NLOGN)
Space O(1)
这道题用Binary Search真的很勉强。。。

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1 = list(set(nums1))
        nums1.sort()
        set2 = set(nums2)
        self.res = []
        
        for num in set2:
            self.binarySearch(num, nums1)
        return self.res
        
    def binarySearch(self, target, arr):
        l , r = 0, len(arr) - 1
        while l <= r:
            mid = int(l + (r-l)/2)
            if target == arr[mid]:
                self.res.append(target)
            if target > arr[mid]:
                l = mid + 1
            else:
                r = mid - 1 

[tech-cow]

167. Two Sum II - Input array is sorted
Binary Search
Time O(NLOGN)
Space O(1)
Binary Search并不是最优解，这里需要注意的是去重，所以起始的Left区间不是从0开始，而是从i+1。

class Solution:
    def twoSum(self, nums, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i, num in enumerate(nums):
            l, r = i + 1, len(nums) - 1
            temp = target - num
            while l <= r:
                mid = l + (r-l)//2
                if temp == nums[mid]:
                    return [i+1, mid+1]
                if temp > nums[mid]:
                    l = mid + 1
                else:
                    r = mid - 1     

[gengwuli]

采用以下模板如何？

def binarySearch(arr: Array[Int], target: Int): Int = {
  var (start, end) = (0, arr.length - 1)
  while (start + 1 < end) {
    val mid = start + (end - start) / 2
    if (arr(mid) == target) {
      return mid
    } else if (arr(mid) < target) {
      start = mid
    } else {
      end = mid
    }
  }
  if (arr(start) == target) { return start }
  if (arr(end) == target) { return end }
  -1
}

[tech-cow]

350. Intersection of Two Arrays II
Binary Search
Time O(NLOGN)
Space O(1)

Binary Search依旧并不是最优解，这里需要注意的是，在对相应while loop里面数组操作的同时，不能更改数组，不然会出现区间错乱。所以这里在每次操作完Binary Search并且返回的时候，同时传回了一个Flag，然后在For Loop那一层再进行更改。

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        self.res = []
    
        for i, num in enumerate(nums1):
            flag, j = self.binarySearch(nums2, num)
            if flag:
                del nums2[j]
        return self.res
        
    
    def binarySearch(self, nums, target):
        l , r = 0 , len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                self.res.append(target)
                return True, mid
            if target > nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return False, 0

[gengwuli]

Move Zeroes 是leetcode 283
Two Pointer Slow Runner 的解法只有在nums[slow] = 0的时候才需要交换，可以把0理解为一个坑，fast走在前面，slow走在后面，每遇到一个坑的时候slow就停下来，直到fast往前走挖土来填slow的坑。最后slow的前面就都是坑了。

[tech-cow]

744. Find Smallest Letter Greater Than Target
Time O(LOGN)
Space O(1)

这题是Binary Search里面常见问题的第二套答题思路，具体见：Link
这道题和一般公式区别在于，对target和mid value比对的时候，加了一个 相等的情况，因为题目要求里面表明，假如两个string相等，也要下移一位。被这个Edge Case挂了10次我也是醉了。

class Solution:
    def nextGreatestLetter(self, arr, target):
        if target < arr[0]: return arr[0]
        if target >= arr[-1]: return arr[0]
        
        l, r = 0 , len(arr) - 1
        while l <= r :
            mid = l + (r-l)//2
            if target >= arr[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return arr[l]