Day 5 | 7/2 about leetcode

[tech-cow]

热身，重刷Leetcode

658. Find K Closest Elements

继续重刷，BUG出的太多。

162. Find Peak Element

类型：考虑边界
Time Complexity (logN)
Time Spent on this question: 5 mins

用了新的模板针对这一类可能过界的题:

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

153. Find Minimum in Rotated Sorted Array

类型：考虑边界
Time Complexity (logN)

nums[mid] > nums[r] 这个边界选择真的好酷。。因为这样L的位置永远是在最小的边界处。

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

[tech-cow]

Lintcode

462. Total Occurrence of Target

类型：考虑边界
Time Complexity (logN)
Time Spent on this question: 10 mins

找到左右bound的Index值，然后计算。

class Solution:
    def totalOccurrence(self, nums, target):
        if len(nums) < 2:
            return 0
        l = self.findLeft(nums, target)
        r = self.findRight(nums, target)
        return r-l+1
        
    def findLeft(self, nums, target):
        l, mid, r = 0, 0, len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l
        
            
    def findRight(self, nums, target):
        l, mid, r = 0, 0, len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid - 1
        return r

459. Closest Number in Sorted Array

类型：考虑边界
Time Complexity (logN)
Time Spent on this question: 15 mins

这道题的解题思路基本和Find Closest K Element一样。先找到Insertion Point，然后比对左右大小

class Solution:
    """
    @param: A: an integer array sorted in ascending order
    @param: target: An integer
    @return: an integer
    """
    def closestNumber(self, nums , target):
        # write your code here
        l = r = self.binarySearch(nums, target)
        if l == 0 : return r
        if r == len(nums): return l - 1
        if target - nums[l-1] > nums[r] - target:
            return r
        else:
            return l - 1



    def binarySearch(self, nums, target):
        l, mid, r = 0, 0, len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

[tech-cow]

Leetcode

34. Search for a Range

类型：考虑边界
Time Complexity (logN)
Time Spent on this question: 25 mins

处理边界的时候只要利用l 最终会过界的原理就行，因为只要返回的值在列表里面，l的返回值就不会过界，l就不会比r要大。
对l 和 r 坐标有疑惑的朋友可以通过这个网站去模拟一下l 和 r在方程结束后的坐标： http://pythontutor.com/visualize.html#mode=display

class Solution:
    def searchRange(self, nums, target):
        l = self.findLeft(nums, target)
        r = self.findRight(nums, target)
        return [l, r] if l <= r else [-1, -1]
    
    
    def findLeft(self, nums, target):
        l, mid, r = 0, 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l    

        
    def findRight(self, nums, target):
        l, mid, r = 0, 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid - 1
        return r

74. Search a 2D Matrix

类型：考虑边界
Time Complexity (logN)
Time Spent on this question: 40 mins

这题的诀窍就是把二维数组当成一维数组来处理。我们先来看看普通的二分是怎么实现的:

def binarySearch(arr, target):
    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

在看看这道题是怎么实现的：

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or target is None: return False
        m = len(matrix)
        n = len(matrix[0])
        l, r = 0, m * n - 1
        while l <= r:
            mid = l + (r-l)//2
            row, col = mid // n , mid % n
            if matrix[row][col] == target:
                return True
            if matrix[row][col] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

老铁没毛病，框架都是一样的。第一次看别人写这个答案，r 的取值为 m * n - 1 一脸懵逼，仔细想想发现，其实和普通二分里面的 len(arr) - 1 相对应的数组最后一个数的下标是一个道理：
打个比方我们有个3x3的矩阵，那么 len(matrix) * len(matrix[0] - 1) 正是这个矩阵最后一个数的下标。

这个矩阵如果换成一维的话，那就是一个含有9个数的array
array定义按照 l , r = 0, len(arr) - 1 , l = 0, r = 8 然后mid = 4
然后对比我们二维的处理，其实完全一样
l, r = 0, m * n - 1 , l = 0, r = 8 然后 mid = 4

接下来要做的是如何在二维数组里面表达我们要找的 mid = 4 的下标， 我们思考下，这个下标其实就是矩阵第二排的第一个数。也就是 matrix[1][0] 的位置。

下标在那一个row，可以用 mid // n 来表示，比如我们要找的是下标分别为 3 4 5， 他们的row都会在第二排，因为 3//3 | 4//3 | 5//3 都会得到1，这里的1相对应的row就是2
下标在这个row的哪一个位置，可以用 mid % n 表示，这个就是rollover的概念，不多说啦。

写这么长，主要是第一次看答案，看了半天没看懂，我比较菜

下面对代码进行一些格式上的优化：

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or target is None: return False
        l, r = 0, len(matrix) * len(matrix[0]) - 1
        while l <= r:
            mid = l + (r-l)//2
            row, col = mid//len(matrix[0]), mid%(len(matrix[0]))
            if matrix[row][col] == target:
                return True
            if matrix[row][col] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False