Day 2 | 6/25

[tech-cow]

今日任务 (Binary Search)

• 继续熟练Binary Search的模板
• 网上搜集类似的资源，看看有没有更加底层的架势。

Leetcode Easy

35 Search Insert Position 40.0% Easy
278 First Bad Version
367 Valid Perfect Square 38.8% Easy
374 Guess Number Higher or Lower 37.1% Easy
441 Arranging Coins 36.6% Easy
69 Sqrt(x) 29.2% Easy

以下没做出来，Roll Over
475 Heaters 29.8% Easy

[tech-cow]

35. Search Insert Position
Time: O(logn)
Space: O(1)

经典的Binary Search变种，最后如果没有找到结果，会返回lower bound，原因是，while loop break的条件是在lower bound超过upper bound，l = r + 1，用下面的Case举例：

Case: [1,3,5,6] Target = 2
在while loop break出来的时候， l = 1 , r = 0 。 这个时候返回 l，就是Target = 2 应该插入的index位置，这里巧妙的运用到了lower bound超过upper bound的这个特性。

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

278. First Bad Version
Time: O(logn)
Space: O(1)

和楼上原理一致。

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l , r = 0 , n
        while l <= r:
            mid = l + (r-l)//2
            if not isBadVersion(mid):
                l = mid + 1
            else:
                r = mid - 1
        return l

[tech-cow]

367. Valid Perfect Square
Time: O(logn)
Space: O(1)

这题可以没啥多说的，模板套套，人生巅峰

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        l, r = 0, num
        while l <= r:
            mid = l + (r-l)//2
            if mid ** 2 == num:
                return True
            if num > mid ** 2:
                l = mid + 1
            else:
                r = mid - 1
        return False

374. Guess Number Higher or Lower
Time: O(logn)
Space: O(1)

这题除了套了个所谓的API，其他基本和模板一样

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l , r = 0 , n
        while l <= r :
            mid = l + (r-l)//2
            toggle = guess(mid)
            if toggle == 0:
                return mid
            if toggle == 1:
                l = mid + 1
            else:
                r = mid - 1

[tech-cow]

重刷: Upper Bound 和 Lower Bound的概念还是很模糊。

441. Arranging Coins
Time: O(logn)
Space: O(1)

思路：从0到n进行binary search，如果当前mid之前的所有sum总和 == target，则返回mid，最终返回的是upper bound r,

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 0, n
        while l <= r :
            mid = l + (r-l)//2
            if mid * (mid+1) / 2 == n:
                return mid
            if mid * (mid+1) / 2 < n:
                l = mid + 1
            else:
                r = mid - 1
        return r

69. Sqrt(x)
Time: O(logn)
Space: O(1)

和上面一题极度类似，思考这里的Upper Bound来源

class Solution(object):
    def mySqrt(self, n):
        """
        :type x: int
        :rtype: int
        """
        l, r = 0 , n
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid == n:
                return mid
            if mid * mid < n:
                l = mid + 1
            else:
                r = mid - 1
        return r