Day 4 | 7/1

[tech-cow]

今天任务以下题目：

今日任务 (Binary Search)

• 巩固新的模板。
• 用番茄工作法限制刷题时间。

刷题任务

热身，重刷Leetcode

• 278 First Bad Version
• 441. Arranging Coins
• 69. Sqrt(x)

Lintcode

• 458. Last Position of Target
• 585. Maximum Number in Mountain Sequence
• 447. Search in a Big Sorted Array

Leetcode

• 658. Find K Closest Elements
• 162. Find Peak Element
• 153. Find Minimum in Rotated Sorted Array

[tech-cow]

Lintcode

458. Last Position of Target

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

记得缩减左边重复的位置，讲Left移到中介线的位置。

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

585. Maximum Number in Mountain Sequence

类型：直接找值
Time Complexity (logN)
Time Spent on this question: 5 mins

class Solution:
    def mountainSequence(self, nums):
        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

447. Search in a Big Sorted Array

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

写个While循环寻找End的边界。返回时候，分界线左边为不满足条件，右边为满足条件，返回第一个满足条件的数，也就是分界线的右边：返回"L"

class Solution:
    def searchBigSortedArray(self, reader, target):
        up_bound = 1
        while reader.get(up_bound) < target:
            up_bound *= 2
            
        l , r = 0, up_bound
        while l <= r:
            mid = l + (r-l)//2
            if reader.get(mid) < target:
                l = mid + 1
            else:
                r = mid - 1
        if reader.get(l) == target:
            return l
        return -1

[tech-cow]

Leetcode

658. Find K Closest Elements

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

high level思路：这道题可以理解为 Leetcode 35. Search Insert Position 的Follow Up。首先先写一个和35题一模一样的辅助方程，用来寻找插入的位置。位置锁定以后，比对该位置的左边和右边的值。

实践：关于比对值，我之前的思路是开辟一个Array，然后在对比完大小后，往这个Array一个一个的加，后来选择用Two Pointer来表示L和R的指针，然后运用Python的Indexing节省了一小部分的空间。另外要注意的一个细节就是，我们找到的这个插入点，并不代表我们找到和题目中x一样的值，所以在比对的时候，我们一定要记住用x和插入点的值比对:

if x - arr[l-1] <= arr[r] - x:

这里我并没有写arr[r + 1] 就是这个原因。还有一个细节就是我之前定义l 和r的时候用的以下代码:

l, r = index - 1, index

遇到的问题就是过不了当arr等于1的Edge case，理由是因为提前处理index会导致while循环进不去。因为当arr长度和k等于1的时候，r-l就等于k了。所以我最终没有提前修改l的位置，是在循环里面处理的这个Edge:

if x - arr[l-1] <= arr[r] - x:

class Solution:
    def findClosestElements(self, arr, k, x):
        index = self.findIndex(arr, x)
        l, r = index, index

        while r - l < k:
            if l == 0: return arr[:k]
            if r == len(arr): return arr[-k:]
            if x - arr[l-1] <= arr[r] - x: 
                l -= 1
            else: 
                r += 1
        return arr[l:r]
            

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

162. Find Peak Element

类型：考虑边界
Time Complexity (logN )
Time Spent on this question: 50 mins | 重刷

这题套惯用的模板要考虑Edge Case，因为判定条件是:

上坡：nums[mid-1] < nums[mid]
下坡： nums[mid] > nums[mid+1]

然后这里mid + 1 和 mid - 1在数组大小为 1 或者 2的时候，很容易就越界了，所以在大小范围假如最小值和最大值。得到：
if (mid == 0 or nums[mid-1] < nums[mid]) and (mid == len(nums) - 1 or nums[mid] > nums[mid+1]):

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

这道题目也可以套另外一个模板，可以不用考虑越界的问题：

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

153. Find Minimum in Rotated Sorted Array

类型：考虑边界
Time Complexity (logN )
Time Spent on this question: 1 hour | 重刷

重刷。

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