LeetCode 常用方法-摩杜云开发者社区

记录下LeetCode中常用的方法。

目前有：二分，回溯。

二分查找：

作者：labuladong

原文解释的很好，推荐阅读。二分查找的细节就是while 条件是< 还是 <=,更新right=mid还是mid+1，可以用区间开闭来理解。

while left < right 意味着搜索区间是 [left,right)左闭右开，

while left <= right 意味着搜索区间是 [left,right]左闭右闭。

这个搜索空间也决定了后面的更新。以左边界为例，如果使用 left<=right闭区间形式，

初始化left,right = 0,len(nums)-1 对应[0,len(nums)-1]

那么 nums[mid] > target 时，right = mid-1，搜索区间变为[left,mid-1]
    nums[mid] == target时，right = mid-1，搜索区间为[left,mid-1],继续向左压缩。

    nums[mid] <   target时，left = mid+1,    搜索空间为[mid+1,right]。
而如果使用 left< right 左闭右开形式，初始化left,right = 0,len(nums) 对应[0,len(nums))

nums[mid] > target 时 , right = mid，搜索区间变为[left,mid)

nums[mid] == target时，right = mid，搜索区间为[left,mid),继续向左压缩。

nums[mid] < target时， left = mid+1, 搜索空间为[mid+1,right)。

二分查找模板

包括：二分查找目标值，左边界，右边界。（Python版本）

直接查找目标值很简单，

nums[mid]<target，压缩左边 left = mid +1

nums[mid]>target,压缩右边 right = mid -1

nums[mid]==target , 返回 mid

查找左边界的前两部分类似，但nums[mid]==target时要继续压缩右边界，锁定左边界，最后返回左边界。注意处理越界情况。

查找右边界同理。

class Solution:
    #二分查找目标值
    def binary_search(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                return mid
        return -1
    #左边界
    def left_bound(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                right = mid -1
        if left >= len(nums) or nums[left] != target:
            return -1
        return left
    #右边界
    def right_bound(self,nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] ==target:
                left = mid + 1
        if right < 0 or nums[right] != target:
            return -1
        return right

回溯

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案；

在尝试了所有可能的分步方法后宣告该问题没有答案。

简单来说，回溯法通过递归（深度优先遍历dfs）来分步解决问题。在每一步的尝试中，可能取消上一步的操作。

#回溯  题39
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(target,ans,combine,idx):
            if idx == n:
                return
            if target == 0:
                ans.append(list(combine))
                return
            #跳过idx
            dfs(target,ans,combine,idx+1)
            #选择idx
            if target-candidates[idx] >= 0:
                combine.append(candidates[idx])
                dfs(target-candidates[idx],ans,combine,idx)
                combine.pop()
      
        n = len(candidates)
        ans = []
        combine=[]
        dfs(target,ans,combine,0)
        return ans

可以抽象为：

def dfs(目标target,状态,临时答案tmpans,ans):
    if 终止条件:
        return #结束
    if 满足条件target:
        添加tmpans到ans
        return #结束

    做出选择
    dfs(选择后的状态)
    撤销选择