2.算法-分治

二分模板

def search(arr, v)
{
    left = 0, right = len(arr) - 1 #左闭右闭 right是最右边数组下标
    while (left <= right):  # 左闭右闭 小于等于
        middle = left + (right-left) // 2;
        if (array[middle] > v):
             right = middle - 1;#左闭右闭 right = mid + 1
        elif (array[middle] < v):
             left = middle + 1;#左闭右闭 right = mid - 1
        else:
            return middle

经典例题

14. 最长公共前缀

def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length):
            str0, count = strs[0][:length], len(strs)
            for i in range(1,count):
                if str0 != strs[i][:length]:
                    return False
            return True 
            #python语法糖简洁写法
            #return all(strs[i][:length] == str0 for i in range(1, count))

        if not strs:
            return ""

        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

35题 - 搜索插入位置 == 实现 bisect.bisect_left

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

169. 多数元素

可以看到分治法的思路，但是效率确实一般，基本在100ms以上

def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        if(len(nums)==1):
            return nums[0]
        left = self.majorityElement(nums[:len(nums)//2])
        right = self.majorityElement(nums[len(nums)//2:])

        if(left==right):
            return left
        if(nums.count(left)>nums.count(right)):
            return left
        else:
            return right

如果用python自带的方法，可以发小基本在50ms左右，这是为啥呢？？

def majorityElement(self, nums: List[int]) -> int:
        return collections.Counter(nums).most_common()[0][0]

如果去查看most_common的源码，会发现用了堆

def most_common(self, n=None):
        if n is None:
            return sorted(self.items(), key=_itemgetter(1), reverse=True)
        return _heapq.nlargest(n, self.items(), key=_itemgetter(1))

nlargest和nsmallest可以帮助我们在某个集合中找出最大或最小的N个元素

>>> import heapq
>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]
>>> print(heapq.nlargest(3,nums))
[42, 37, 23]
>>> print(heapq.nsmallest(3,nums))
[-4, 1, 2]

53. 最大子序和

这道题之前做过，已经是O(n)的算法，

def maxSubArray(self, nums: List[int]) -> int:
        res, tmp = nums[0], 0
        for num in nums:
            tmp = max(num, tmp+num)
            res = max(res, tmp)
        return res

这里我们结合DW用更为巧妙的分治法

def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return None
        if(len(nums)==1):
            return nums[0]
        l,ltmp,rtmp = len(nums),0,0
        left = self.maxSubArray(nums[:l//2]) 
        right = self.maxSubArray(nums[l//2:])
        maxleft,maxright = nums[l//2-1],nums[l//2] #左区间最右值 和 右区间最左值
        for i in range(l//2-1,-1,-1):#从右向左遍历左区间
            ltmp += nums[i]
            maxleft = max(maxleft,ltmp)
        for j in range(l//2,l):#从左向右遍历右区间 
            rtmp += nums[j]
            maxright = max(maxright,rtmp)
        return max(left,right,maxleft+maxright)

不过分治法的速度好像是不太行啊，100ms以上

50. Pow(x, n)

这个分治法的效率还行，

def myPow(self, x: float, n: int) -> float:
        if(n==0):
            return 1
        if(n<0):
            x=1/x
            n=-n
        if (n%2==1):
            p = x*self.myPow(x, n-1)
            return p
        return self.myPow(x*x, n/2)

之前做过这道题，但是快速幂的方法是通过位运算实现的

def myPow(self, x: float, n: int) -> float:
        if x == 0.0: return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1 #这里位运算速度要更快
        return res

1. 287. 寻找重复数

def findDuplicate(self, nums: List[int]) -> int:
        l, r = 1, len(nums) - 1
        while l < r: 
            mid = (l+r)//2 
            count = 0
            for num in nums:
                if num <= mid:
                    count += 1
            #下面这块逻辑要注意下 原来少想了一种情况
            #count 是有可能比mid小的 比如 [1,2,4,4] 比4小的只有两个元素
            #所以这里其实条件是：小于等于mid的元素的数量小于或者等于mid 说明重复的元素在mid后面 
            #反过来理解就是 count > mid 说明重复元素一定在mid前面（包含mid）
            if count > mid:
                r = mid
            else: 
                l = mid + 1
        return l

2 .875. 爱吃香蕉的珂珂

还是二分查找的典型应用，

def minEatingSpeed(self, piles: List[int], H: int) -> int:
        if len(piles) >= H: 
            return max(piles)
        avg = sum(piles) // H
        l = 1 if not avg else avg #注意这里要对做0判断，最少为1
        r =  max(piles)
        while l < r:
            hour, mid = 0, (l+r)//2
            for pile in piles:
                if pile <= mid:
                    hour +=1 
                else:
                    hour += (pile//mid + 1)
            if hour <= H:  #这里注意下是小于等于，经过二分查找后low一直向右移动到了我们需要的位置，所以返回 low
                r = mid
            else:
                l = mid + 1 
        return l

6 . 69. x 的平方根

平方根的二分查找法

def mySqrt(self, x: int) -> int:
        l,r,ans = 0,x,-1
        while(l<=r):
            mid = (l+r)//2
            if mid*mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

3. 剑指 Offer 53 - II. 0～n-1中缺失的数字

这个题目要读懂题目的意思，搞清楚边界条件
用下面这种思路，考虑缺少首尾的情况

for i in range(0,len(nums)-1):
            if(nums[i+1]-nums[i]==2):
                return nums[i]+1
        return len(nums) if nums[0]==0 else 0

这个题目从官方给的思路，应该用二分法，任何排序中的查找问题，都要想到用二分法！！

def missingNumber(self, nums: List[int]) -> int:
        low, high = 0, len(nums)-1
        while(low<=high): #注意这里是小于等于不是小于，非常重要，在low和去high相等之后，再进入循环，目的是让low向前进1，拿到最后对应的元素值，因为返回的是low
            mid = (low+high)//2
            if(nums[mid]==mid):
                low = mid + 1
            else:
                high = mid - 1 
        return low