LeetCode 常用方法

简介: LeetCode 常用方法

二分查找:

二分查找模板_一只大鸽子的博客-CSDN博客

作者:labuladong

链接:https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/

来源:力扣(LeetCode)

原文解释的很好,推荐阅读。二分查找的细节就是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]<targe,压缩左边 lefht = 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

回溯

回溯算法入门级详解 + 练习(持续更新) - 全排列 - 力扣(LeetCode) (leetcode-cn.com)


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

  • 找到一个可能存在的正确的答案;
  • 在尝试了所有可能的分步方法后宣告该问题没有答案。

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

39. 组合总和 - 力扣(LeetCode) (leetcode-cn.com)

46. 全排列 - 力扣(LeetCode) (leetcode-cn.com)

#回溯  题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(选择后的状态)
    撤销选择
 
相关文章
|
5月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
|
5月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
5月前
|
SQL 算法 数据挖掘
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
|
5月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
5月前
|
存储 算法 数据可视化
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
|
5月前
|
存储 算法 数据可视化
|
5月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
5月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
5月前
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
|
5月前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)