算法工程师的日常
0%

二分和查找

发表于 更新于 分类于 ，

二分和查找类

基础思路

在二分查找中，需要注意的是边界的问题，其中很多小的点，很容易出现问题，一般的解法如下所示：注意哈，写的时候，要hihg = len(nums) - 1, 不要忘了写成len(nums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# 查找具体的数值
# 方案1
def binary_search(nums, target):
    low = 0
    high = len(nums) - 1 
    while low <= high: #注意
        mid = low + (high - low) // 2 # 注意
        # 不要使用else,要使用elif，不然有些情况会报错
        if nums[mid] < target:
            low = mid + 1 # 注意
        elif nums[mid] > target:
            high = mid - 1 # 这里
        elif nums[mid] == target: 
            return mid
 # 方案2
 def binary_search(nums, target):
    low = 0
    high = len(nums)  # 这里不能改成-1，不然有些值查不到
    while low < high: #注意
        mid = low + (high - low) // 2 # 注意
        # 不要使用else,要使用elif，不然有些情况会报错
        if nums[mid] < target:
            low = mid + 1 # 注意
        elif nums[mid] > target:
            high = mid # 这里
        elif nums[mid] == target: 
            return mid


# 查找左边界
# 方案1
def left_bound(nums, target):
    low = 0
    high = len(nums) - 1
    ans = -1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        elif nums[mid] > target: # 右边界往里
            high = mid - 1
        elif nums[mid]==target:
            ans = mid
            high = mid - 1
    return ans
    
# 方案2
def left_bound(nums, target):
    low = 0
    high = len(nums)
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        elif nums[mid] > target: # 右边界往里
            high = mid
        elif nums[mid]==target:
            ans = mid
            high = mid
    return ans
    

# 查找右边界
# 方案1
def right_bound(nums, target):
    low = 0
    high = len(nums) - 1
    ans = -1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] <  target: # 左边界往里
            low = mid + 1
        elif nums[mid] > target: 
            high = mid - 1
        elif nums[mid] == target:
            low = mid + 1
            ans = mid
    return ans
# 方案2
def right_bound(nums, target):
    low = 0
    high = len(nums)
    ans = -1
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] < target: # 左边界往里
            low = mid + 1
        elif nums[mid] > target:
            high = mid
        elif nums[mid] == target:
            low = mid + 1
            ans = mid
    return ans


nums = [1, 2, 3, 4, 4, 5, 6, 7, 8]

target = 4
print(binary_search(nums, 5))
print(left_bound(nums, target))
print(left_bound2(nums, target))
print(right_bound(nums, target))
print(right_bound2(nums, target))

建议方案1，另外看如下的两个例子，明确下为啥low不能=mid，而需要=mid+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def search_correct(nums, target):
    low, high = 0, len(nums)
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid


def search_error(nums, target):
    low, high = 0, len(nums)
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid # 这里不更新会导致mid在经过（low+high）取值后，一直停留在mid
        else:
            high = mid - 1


nums = [1, 3, 4, 5, 6]
target = 8
print(search_correct(nums, target))  # None
print(search_error(nums, target))  # 循环
target = -1
print(search_correct(nums, target))  # None
print(search_error(nums, target))  # None

可以看到不同的参数设置，会导致不同的运行结果。

为什么二分查找中用一些特别的+1或者<=,看个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(nums, target):
    low = 0
    high = len(nums) 
    while low <= high: #注意
        mid = low + (high - low) // 2 # 注意
        # 不要使用else,要使用elif，不然有些情况会报错
        if nums[mid] < target:
            low = mid  # 注意
        elif nums[mid] > target:
            high = mid # 这里
        elif nums[mid] == target: 
            return mid
binary_search(【1,2,3,4,5,6,7,8】, 9)

上面自己调一下就知道了， 从参考的文献来看的话，建议使用左闭右闭的的方式，也就是《=的基础方式的。但是对于一些需要旋转数组这些题，因为不知道要找的数最终是什么，所以一般用low<high， 然后结合low=mid+1, high=mid来 实现。对于一些寻找旋转数组中值的情况，因为是确切找值的，所以的话，一般用while low<=high, 然后结合 low=mid+1, high=mid-1 来实现。

参考如下：
[1] https://blog.csdn.net/qq_38235017/article/details/115177238?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1.pc_relevant_paycolumn_v2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1.pc_relevant_paycolumn_v2&utm_relevant_index=1
[2] https://www.cnblogs.com/mxj961116/p/11945444.html
[3] https://leetcode.cn/circle/discuss/ooxfo8/ 这里说的很好，说道了上面讲述的为何要<问题，以及循环的问题。

单数组

排序数组中查找元素的第一个和最后一个位置[34]

位于 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1  # 闭区间 [left, right]
            while left <= right:  # 区间不为空
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1  # 范围缩小到 [mid+1, right]
                else:
                    right = mid - 1  # 范围缩小到 [left, mid-1]
            return left  # 或者 right+1

        start = lower_bound(nums, target)  # 选择其中一种写法即可
        if start == len(nums) or nums[start] != target:
            return [-1, -1]        
        end = lower_bound(nums, target + 1) - 1 # 如果 start 存在，那么 end 必定存在
        return [start, end]

H 指数[274]

位于 https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

1
2
3
4
5
6
7
8
9
10
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        import bisect
        citations.sort()
        res = 0
        for i in range(1, len(citations)+1):
            index = bisect.bisect_left(citations, i)
            if len(citations) - index >= i:
                res = max(res, i)
        return res

山脉数组的峰顶索引

题目见 https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/， 题解入下面的那道题

寻找峰值

题目见 https://leetcode-cn.com/problems/find-peak-element/ ，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 不知道确切的值是啥，所以用low<high，当然这里也可以用都闭合的方式。
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        nums = [-float("inf")] + nums + [-float("inf")] # 这里加一下，方便操作
        low = 0
        high = len(nums) - 1 # attention
        while low < high:
            mid = low + (high - low)//2
            if nums[mid+1] >= nums[mid]: # attention
                low = mid + 1
            else:
                high = mid
        return low - 1

有序数组中的单一元素[540]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 不知道这个数是啥，用low<high
def singleNonDuplicate(nums):
    low = 0
    high = len(nums) - 1
    while low < high:
        mid = (high + low) >> 1
        halvesAreEven = (high - mid) % 2 == 0
        if nums[mid] == nums[mid + 1]:
            if halvesAreEven:
                low = low + 2
            else:
                high = mid - 1 # 注意不是high=mid
        elif nums[mid] == nums[mid - 1]:
            if halvesAreEven:
                high = mid - 2
            else:
                low = mid + 1
        else:
            return nums[mid]
    return nums[low]

寻找旋转排序数组中的最小值[153]

1
2
3
4
5
6
7
8
9
10
11
#  不知道最小数是啥，用low<high
class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            pivot = low + (high - low) // 2
            if nums[pivot] < nums[high]:# 这里high改为len(nums)-1也可以
                high = pivot
            else:
                low = pivot + 1
        return nums[low]

寻找旋转排序数组中的最小值 II[154]

1
2
3
4
5
6
7
8
9
10
11
12
13
#  不知道最小数是啥，用low<high
class Solution:
    def findMin(self, nums: List[int]) -> int:
        while len(nums)>1 and nums[0]==nums[-1]: # 注意
            nums.pop()
        low, high = 0, len(nums) - 1
        while low < high:
            pivot = low + (high - low) // 2
            if nums[pivot] < nums[high]:
                high = pivot
            else:
                low = pivot + 1
        return nums[low]

搜索旋转排序数组[33]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 知道搜的是啥，用low<=high
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]: # 这里是>= 不是>
                if nums[0] <= target < nums[mid]: # 注意：是小于不是小于等于
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]: # 左边是开，右边是闭
                    l = mid + 1
                else:
                    r = mid -1 
        return -1

搜索旋转排序数组II[81]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 知道搜的是啥，用low<=high
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        while len(nums)>1 and nums[0]==nums[-1]: # 加这段代码处理一下重复的问题
            nums.pop()
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = low + (high -low)//2
            if nums[mid]==target:
                return True           
            if nums[mid] >= nums[0]:
                if nums[0]<=target<nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            elif nums[mid]<nums[0]:
                if nums[mid]<target<=nums[-1]:
                    low =mid+1
                else:
                    high=mid-1
        return False

数组中的k-diff数对[532]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        import bisect
        from collections import Counter

        nums_set = Counter(nums)
        if k == 0:
            return sum([i>1 for i in nums_set.values()]) # 注意这里

        nums.sort()
        diff_min, diff_max = nums[0], nums[-1]
        cnt = 0
        
        for j in nums_set.keys():
            index = bisect.bisect_left(nums, j+k)
            if index < len(nums):
                if nums[index] == j+k:
                    cnt += 1
  
        return cnt

注意，对于k=0是需要单独计算的，因此需要分开。

数组中的逆序对[LCR 170]

题目见 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reversePairs(self, record: List[int]) -> int:
        import bisect
        record = record[::-1] # 这步很重要
        res = []
        s = 0
        for i in record:
            index = bisect.bisect_left(res, i)
            res[index:index] = [i] # bisect.insort(res, i)也可以
            s = s + index
        return s

通过二分查找排序的方法来做的话，更快。看下面这道题是一样的

翻转对[493]

题目见 https://leetcode-cn.com/problems/reverse-pairs/ 和上面的题目是一样的，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        import bisect
        nums = nums[::-1]
        res = []
        sums = 0
        for i in nums:
            index = bisect.bisect_left(res, i) # 查看插入的位置，就是数量
            sums = sums + index # 累加
            index2 = bisect.bisect_left(res, 2*i) # 实际要对res进行处理，加入2*i这个数
            res[index2:index2] = [2*i] # 加入数
        return sums

计算右侧小于当前元素的个数[315]

题目见 https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/ 一看题目是没法使用二分查找的，但是只要转换下思路就可以了。
题解如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        import bisect
        data = []
        res = []
        for i in nums[::-1]:
            index = bisect.bisect_left(data, i)
            data[index:index] = [i] #bisect.insort(data, i)也行
            res.append(index)
        return res[::-1]

马戏团人塔[面试题 17.08]

这道题其实就是求最长上升子序列而已，题目见 https://leetcode-cn.com/problems/circus-tower-lcci/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 解法1
class Solution:
    import bisect
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       
       dp=[]
       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):
           pos = bisect.bisect_left(dp,b)
           dp[pos:pos+1] = [b]
       return len(dp)
# 解法2
class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        hw = list(zip(height, weight))
        hw.sort(key=lambda x:(x[0],-x[1]))
        v = [j[1] for j in hw]
        stk = []
        for x in v:
            if stk and x <= stk[-1]:
                idx = bisect_left(stk, x)
                stk[idx] = x
            else:
                stk.append(x)
        return len(stk)
# 解法3，DP
class Solution:
    import bisect
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       
        t = sorted(zip(height, weight),key=lambda x:(x[0],-x[1]))
        new_height = [x[0] for x in t]
        new_weight = [x[1] for x in t]
        dp = [1] * len(new_weight)
        for i in range(1,len(dp)):
            for j in range(i):
                if new_weight[i] > new_weight[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

注意这里是[pos:pos+1]和上面的是不一样的

绝对差值和[1818]

位于 https://leetcode.cn/problems/minimum-absolute-sum-difference/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        diff = sum(abs(nums1[i] - nums2[i]) for i in range(len(nums1)))
        if not diff: return 0
        ans = float("inf")
        nums1_sort = sorted(nums1)
        import bisect
        for i, num in enumerate(nums2):
            idx = bisect.bisect_left(nums1_sort, num)
            if idx == len(nums1):
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx-1] - nums2[i]))
            if idx == 0:
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx] - nums2[i]))
            if idx<len(nums1) and idx>0:
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx-1] - nums2[i]))
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx] - nums2[i]))
        return ans%(10**9+7)

简化为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        diff = sum(abs(nums1[i] - nums2[i]) for i in range(len(nums1)))
        if not diff: return 0
        ans = float("inf")
        nums1_sort = sorted(nums1)
        import bisect
        for i, num in enumerate(nums2):
            idx = bisect.bisect_left(nums1_sort, num)
            if idx:
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx-1] - nums2[i]))
            if idx<len(nums1):
                ans = min(ans, diff - abs(nums1[i] - nums2[i]) + abs(nums1_sort[idx] - nums2[i]))
        return ans%(10**9+7)

最小差[面试题 16.06]

题目见 https://leetcode-cn.com/problems/smallest-difference-lcci/ 这道题和
绝对差值和 一样，需要判断插入点的位置，然后再进行判断。
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 自己解法
class Solution(object):
    def smallestDifference(self, a, b):
        """
        :type a: List[int]
        :type b: List[int]
        :rtype: int
        """
        import bisect
        a.sort()
        b.sort()

        res = float("inf")
        for i in a:
            index = bisect.bisect_left(b, i)
            if index==len(b):
                diff = abs(i-b[index-1])
            elif index == 0:
                diff = abs(i - b[0])
            elif index>0:
                diff = min(abs(i-b[index-1]), abs(i-b[index]))
            res = min(diff, res)
        return res

两球之间的磁力[1552][SKIP]

这道题看起来没啥意思，但是却考差了基本的问题的分析能力，以及对二分的应用的能力，题目见 https://leetcode-cn.com/problems/magnetic-force-between-two-balls/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 错误
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        low, high = 1, position[-1]- position[0]
        ans = -1
        def check(mid):
            pre = position[0]
            cnt = 1
            for i in range(1, len(position)):
                if position[i] - pre >= mid:
                    pre = position[i]
                    cnt = cnt + 1
            return cnt >= m
        while low < high:
            mid = low + (high - low) // 2
            if check(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid
        return ans
# 正确
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        low, high = 1, position[-1]- position[0]
        ans = -1
        def check(mid):
            pre = position[0]
            cnt = 1
            for i in range(1, len(position)):
                if position[i] - pre >= mid:
                    pre = position[i]
                    cnt = cnt + 1
            return cnt >= m
        while low <= high: #这里
            mid = low + (high - low) // 2
            if check(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1 # 这类
        return ans
# 或者将错误的那个地方换一下
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        low, high = 1, position[-1]- position[0] + 1 # 这里

        ans = -1

        def check(mid):
            pre = position[0]
            cnt = 1
            for i in range(1, len(position)):
                if position[i] - pre >= mid:
                    pre = position[i]
                    cnt = cnt + 1
            return cnt >= m


        while low < high:
            mid = low + (high - low) // 2
            if check(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid
        return ans

主要的思路就是一个一个试试，看看哪个间隔比较适合，最大的间隔就是position[-1] -position[0],最小的是0，我们一个一个来试一下就可以了。

单数组前缀和

在 D 天内送达包裹的能力[1011]

这道题相当给一个数组划分为k份，每份的和加起来最小数，题目见 https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/ ，题目是很好理解的，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def get_shop_times(weights, v):
            need = 1
            cur = 0
            for i in weights:
                if cur + i > v:
                    need += 1
                    cur = 0
                cur += i
            return need

        low = max(weights)
        high = sum(weights)

        while low < high: # 注意的
            mid = (high+low)//2
            t = get_shop_times(weights, mid)
            if t <= days: # 压缩右边的
                high = mid # 注意的
            else:
                low = mid + 1
        return low
        或者 low<=high 然后 high=mid-1也可以的

最高频元素的频数[1838]

题目在这里 https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/ 这里我自己做了一种基于二分的，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        low = 0
        high = len(nums)
        res = 0
        prefix = [0]
        for i in nums:
            prefix.append(prefix[-1] + i)
        for i in range(len(nums)):
            low = 0
            high = i
            while low < high:
                mid = (low + high) >> 1
                if nums[i] * (i - mid + 1) - prefix[i + 1] + prefix[mid] <= k:
                    high = mid
                else:
                    low = mid + 1
            res = max(res, i - low + 1)
        return res

还有双指针的做法，具体如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        i = ans = 0
        # 问题转化一下，排序后 nums[j] * (j - i + 1) <= k + presum[j + 1] - presum[i]
        for j, num in enumerate(nums):
            k += num
            while k < num * (j - i + 1):
                k -= nums[i]
                i += 1
            # 对于当前j最远的i
            ans = max(ans, j - i + 1)
        return ans

其中就是老的思路而已，没有新的变化的，还是注意端点移动的条件。

转变数组后最接近目标值的数组和[1300]

题目见 https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/ 主要的思路是用二分来做，其实主要是找到一个值，让插入后后值全部变成这个值，比如[1,2,3,4,8,9], 我们设置为7，那么在后面的8和9就变成7。还需要注意的是，这里的prefix开始的值要为0，然后进行append才可以。
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        import bisect
        n = len(arr)
        arr.sort()
        prefix = [0]
        for i in arr:
            prefix.append(prefix[-1] + i)
        res = 0
        min_diff = float("inf")
        for i in range(arr[-1]+1):
            index = bisect.bisect_left(arr, i)
            sums = prefix[index] + (n-index)*i
            if abs(sums - target) < min_diff:
                min_diff = abs(sums - target)
                res = i
        return res

区间和的个数[327][SKIP]

题目见 https://leetcode-cn.com/problems/count-of-range-sum/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 暴力
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        import bisect
        prefix = [0]
        for i in nums:
            prefix.append(i + prefix[-1])
        cnt = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if (prefix[j + 1] - prefix[i]) >= lower and (prefix[j + 1] - prefix[i]) <= upper:
                    cnt += 1
        return cnt
# 通过
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        res, pre, now = 0, [0], 0
        for n in nums:
            now += n
            res += bisect.bisect_right(pre, now - lower) - bisect.bisect_left(pre, now - upper)
            bisect.insort(pre, now)
        return res
# AC [通俗版]
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        sl = []
        res = 0
        pre_sum = [0]
        for i in nums:
            pre_sum.append(pre_sum[-1] + i)
        for x in pre_sum:
            res += bisect.bisect_right(sl, x - lower) - bisect.bisect_left(sl, x - upper)
            bisect.insort(sl, x)
        return res

乍一想前缀和不是单调的，没法进行插入排序，但这里的思路在于每个循环考虑以该index为结尾的符合条件的数量。这里的解法非常 https://leetcode.cn/problems/count-of-range-sum/solutions/2417725/sortedlist-da-fa-hao-a-bu-dao-shi-xing-d-7yyh/

将 x 减到 0 的最小操作数[1658]

题目见 https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/ ，解法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 我的解法
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        def get_prefix_sum(nums):
            prefix = []
            for i in nums:
                val = prefix[-1] if prefix else 0
                prefix.append(i+val)
            return prefix

        res = float("inf")
        for i in range(len(nums)):
            nums2 = nums[0:i][::-1] + nums[i:][::-1]
            prefix = get_prefix_sum(nums2)
            print(prefix)
            if x in prefix:
                res = min(res, prefix.index(x)+1)
        return -1 if res==float("inf") else res
# 正确的
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        diff = sum(nums) - x
        if diff < 0:
            return -1
        left = 0
        right = 0
        sm = 0
        res = -1
        while right < len(nums):
            sm += nums[right]
            while sm > diff:
                sm -= nums[left]
                left += 1
            if sm == diff:
                res = max(res,right - left + 1)
            right += 1
        return -1 if res==-1 else len(nums)-res

和大于等于 target 的最短子数组[LCR 008]

链接为：https://leetcode.cn/problems/2VG8Kg/description/ 题解如下，注意一下边界的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        import bisect
        prefix = [0]
        for i in nums:
            prefix.append(prefix[-1] + i)
        if prefix[-1]<target:
            return 0
        res = float("inf")
        for i in range(len(prefix)):
            index = bisect.bisect_left(prefix, prefix[i] + target)
            if index != len(prefix):           
                res = min(index - i, res)
        return 0 if res==len(prefix) else res

也可以使用滑窗解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        ans = n + 1
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        
        return 0 if ans == n + 1 else ans

和至少为k的最短子数组[862]

题目见 https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/ 题解用滑窗如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 超时
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = float("inf")
        for left in range(len(nums)):
            right = left
            sm =0
            while right < n:
                sm += nums[right]
                while sm >= k:
                    res = min(res, right - left + 1)
                    sm -= nums[left] 
                    left += 1
                right += 1
        return -1 if res==float("inf") else res
# 超时2：这个思路要弄懂 模仿区间和的个数区间和的个数来的
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        import bisect
        res = float("inf")
        cnt = 0
        pre_sum = [[0, cnt]]
        for i in range(1, len(nums) + 1):
            pre_sum.append([pre_sum[-1][0] + nums[i - 1], i])
        pre_sum.sort()
        for i in pre_sum:
            cur_val = i[0]
            index = bisect.bisect_left(pre_sum, [cur_val + k, 0])
            for j in range(index, len(pre_sum)):
                if j <= len(nums) and pre_sum[j][0] >= cur_val + k and pre_sum[j][1] - i[1] >= 0:
                    res = min(res, pre_sum[j][1] - i[1])
        if res==float("inf"):
            return -1
        return res
# 超时的原因在于有多个循环，其实看下面的结果也是有多个循环，  也就是1个for里面加了两个while, 不过计算的时候，是通过单调队列来做的，减少了滑窗计算的时间而已。这里和滑窗窗口的最大值是一样的。
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        import collections
        prefix = [0]
        for i in nums:
            prefix.append(prefix[-1] + i)
        stack = collections.deque()
        ans = len(nums) + 1
        for x, y in enumerate(prefix):
            while stack and y <= prefix[stack[-1]]:
                stack.pop()
            while stack and y - prefix[stack[0]] >= k:
                ans = min(ans, x - stack.popleft()) 
            stack.append(x)
        return ans if ans < len(nums) + 1 else -1

这道题和上面的那道题不一样，在于这道题有负数，导致前缀和非单调，无法用滑窗以及直接用二分来做。

双数组

寻找两个正序数组的中位数[4]

题目见 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ ，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# 解法1，使用双指针
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        lens = m + n
        prev = -1
        now = -1
        num1_index = 0
        num2_index = 0
        for i in range(lens//2+1):
            prev = now
            if num1_index<m and (num2_index>=n or nums1[num1_index]<nums2[num2_index]):
                now = nums1[num1_index]
                num1_index += 1
            else:
                now = nums2[num2_index]
                num2_index += 1
        if lens & 1 == 0:
            return (prev + now)/2
        else:
            return now
# 解法2：使用二分查找
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 > n2:
            return self.findMedianSortedArrays(nums2, nums1)

        k = (n1 + n2 + 1) // 2
        left = 0
        right = n1
        while left < right:
            m1 = left + (right - left) // 2    
            m2 = k - m1                        # 
            if nums1[m1] < nums2[m2 - 1]:      # 注意
                left = m1 + 1
            else:
                right = m1

        m1 = left # 算出的m是第2个数，如果是&1=1的话，直接取m-1，不是的话，取m-1和m的均值
        m2 = k - m1
        
        c1 = max(float('-inf') if m1 <= 0 else nums1[m1 - 1], float('-inf') if m2 <= 0 else nums2[m2 - 1]) # 情况1,容易写错为m1
        if (n1 + n2) % 2 == 1:
            return c1

        c2 = min(float('inf') if m1 >= n1 else nums1[m1], float('inf') if m2 >= n2 else nums2[m2]) # 情况2

        return (c1 + c2) / 2
# 自己做法
A = [1]
B = [2]
nums = []
left, right = 0, 0
while left < len(A) and right < len(B):
    if A[left] < B[right]:
        nums.append(A[left])
        left += 1
    else:
        nums.append(B[right])
        right += 1
if left >= len(A):
    nums.extend(B[right:])
if right >= len(B):
    nums.extend(A[left:])
print(nums)

可以从 https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/8999/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/ 查看。二分的思路在 https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/3983/shuang-zhi-zhen-by-powcai/

尽可能使字符串相等[1208]

题目见 https://leetcode-cn.com/problems/get-equal-substrings-within-budget/， 题解如下，建议使用双指针啊，比较快的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        diff = [abs(ord(i)-ord(j)) for i,j in zip(s,t)]
        start = end = res = 0
        ds = 0
        while end < len(diff):
            ds += diff[end]
            while ds > maxCost:
                ds -= diff[start]
                start += 1
            res = max(res, end - start + 1)
            end += 1
        return res

二分查找的思路也是比较简单的，主要如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        accDiff = [0] + list(accumulate(abs(ord(sc) - ord(tc)) for sc, tc in zip(s, t)))
        maxLength = 0

        for i in range(1, n + 1):
            start = bisect.bisect_left(accDiff, accDiff[i] - maxCost)
            maxLength = max(maxLength, i - start)
        
        return maxLength

水位上升的泳池中游泳[778]

题目见 https://leetcode-cn.com/problems/swim-in-rising-water/ 主要的思路就是找一个值，小于这个值的地方可以连通起来，最后能连通到最后的点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:

        def dfs(temp, x,y):
            if x<0 or x>=len(temp) or y<0 or y>=len(temp[0]):
                return False
            if temp[x][y]==0:
                return False
            if x==len(temp)-1 and y==len(temp[0])-1 and temp[x][y]==1:
                return True
            temp[x][y] = 0
            for i,j in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
                if dfs(temp,i,j):
                    return True
                #  dfs(temp,i,j): 直接这么写的话是错误的
            return False

        grid_list = sum(grid, [])
        grid_list = sum(grid, [])
        low = min(grid_list)
        high = max(grid_list)
        while low < high:
            mid = (low + high) >> 1
            temp = [[1 if j <= mid else 0 for j in i] for i in grid]
            if dfs(temp, 0, 0):
                high = mid
            else:
                low = mid + 1
        return low

绝对差值和

题目见 https://leetcode-cn.com/problems/minimum-absolute-sum-difference/submissions/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def minAbsoluteSumDiff(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        import bisect
        temp = [abs(nums1[i] - nums2[i]) for i in range(len(nums1))]
        abs_sum = sum(temp)

        nums11 = sorted(nums1)

        res = abs_sum

        for i, j in enumerate(nums2):
            index = bisect.bisect(nums11, j)
            if index < len(nums11):
                res = min(res, abs_sum - abs(nums1[i]-nums2[i]) + abs(nums11[index]-nums2[i]))
            if index > 0:
                res = min(res, abs_sum - abs(nums1[i]-nums2[i]) + abs(nums11[index-1]-nums2[i]))
        return res% (10**9+7)

这里需要注意的是，要查看需要插入数值的位置，查看其前后的位置，是不是有让绝对值更小的值。

交换和[面试题 16.21]

这道题和上面的是类似的，在得到index后需要判断位置，是不行越界了。题目在 https://leetcode-cn.com/problems/sum-swap-lcci/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def findSwapValues(self, array1, array2):
        """
        :type array1: List[int]
        :type array2: List[int]
        :rtype: List[int]
        """
        import bisect
        array1.sort()
        array2.sort()

        sum1 = sum(array1)
        sum2 = sum(array2)

        diff = sum2 - sum1

        if diff % 2 !=0:
            return []

        for i in array1:
            index = bisect.bisect_left(array2, i + diff // 2)
            index = min(len(array2)-1, index) #dasdsdsa
            if array2[index] == i + diff // 2:
                return [i, i + diff // 2]
        return []

得到子序列的最少操作次数[1713]

题目见 https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/ 这里的题目和最长上升子序列的思路基本上是一样的，可以看 https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/solution/mo-gu-qie-cha-cong-lcswen-ti-dao-liswen-xist8/ 的讲解，说的很清楚，总结来说就是一个如下的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        posTa = {}
        for i, t in enumerate(target):
            posTa[t] = i
        posAr = []
        for i, a in enumerate(arr):
            if a in posTa:
                posAr.append(posTa[a])
        # 算出来出现的索引就可以了，然后就是求解了
        stk = []
        for x in posAr:
            if stk and x <= stk[-1]:
                idx = bisect_left(stk, x)
                stk[idx] = x
            else:
                stk.append(x)
        return len(target) - len(stk)

矩阵

二维数组中的查找[LCR.121]

题目见 https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/ 题解如下：

1
2
3
4
5
6
7
8
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: i -= 1
            elif matrix[i][j] < target: j += 1
            else: return True
        return False

有个人总结的比较好，题解在 https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/yu-niang-niang-04er-wei-shu-zu-zhong-de-vpcs9/ 讲解了多个方法

搜索二维矩阵[74]

题目见 https://leetcode-cn.com/problems/search-a-2d-matrix/ 和上面的不一样，这个矩阵的展开收拾递增的，因此可以使用查找的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        low = 0
        m = len(matrix)
        n = len(matrix[0])
        high = m * n - 1 # 如果这里改成了m*n的话，那么后面的最好用low<high
        while low <= high:
            mid = low + (high-low)//2
            row = mid//n
            col = mid%n
            if matrix[row][col] > target:
                high = mid - 1
            elif matrix[row][col] < target:
                low = mid + 1
            else:
                return True
        return False

统计有序矩阵中的负数[1351]

题目见 https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        end = len(grid[0])
        i = 0
        res = 0
        while i < len(grid):
            if grid[i][-1]<0:
                index = bisect.bisect_right([-j for j in grid[i]],0)
                res += len(grid[0]) - index
            i = i + 1
        return res

螺旋矩阵[54]

题号为54，位于https://leetcode.cn/problems/spiral-matrix/description/ 题解如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix)==1:
            return matrix[0]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        row, col, direction_index = 0, 0, 0
        res = []
        m = len(matrix)
        n = len(matrix[1])
        for i in range(m * n):
            res.append(matrix[row][col])
            matrix[row][col] = -999999999
            next_row = row + directions[direction_index % 4][0]
            next_col = col + directions[direction_index % 4][1]
            if next_row < 0 or next_row >= m or next_col < 0 or next_col >= n or matrix[next_row][next_col] == -999999999:
                direction_index = direction_index + 1
                next_row = row + directions[direction_index % 4][0]
                next_col = col + directions[direction_index % 4][1]
            row, col = next_row, next_col
        return res

上下两道题用的是同样的思路，这样比较好统一

螺旋矩阵II[59]

题号为59，位于 https://leetcode.cn/problems/spiral-matrix-ii/description/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        matrix = [[-1]*n for _ in range(n)]
        row, col, direc_index = 0,0,0
        for i in range(n*n):
            matrix[row][col] = i + 1
            next_row = row + directions[direc_index%4][0]
            next_col = row + directions[direc_index%4][1]
            if next_row < 0 or next_row >= n or next_col < 0 or next_row >= n or matrix[next_row][next_col] > -1:
                direc_index = direc_index + 1
                next_row = row + directions[direc_index%4][0]
                next_col = row + directions[direc_index%4][1]
            row, col = next_row, next_col
        return matrix

注意具体的思路是先便利，然后换方向

螺旋矩阵III[885]

题号为885，位于 https://leetcode.cn/problems/spiral-matrix-iii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]: 
        visited_flag = [[False] * cols for _ in range(rows)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        direction_index = -1
        cnt = 0
        init_lens = 0
        res = []
        res.append([rStart, cStart])
        while cnt + 1 < rows * cols:
            init_lens = init_lens + 1

            direction_index = direction_index + 1
            for j1 in range(init_lens):
                next_r = rStart + directions[direction_index % 4][0]
                next_c = cStart + directions[direction_index % 4][1]
                if next_r < 0 or next_r >= rows or next_c < 0 or next_c >= cols or visited_flag[next_r][next_c]:
                    rStart = next_r
                    cStart = next_c
                else:
                    res.append([next_r, next_c])
                    rStart = next_r
                    cStart = next_c
                    visited_flag[next_r][next_c] = True
                    cnt = cnt + 1

            direction_index = direction_index + 1
            for j2 in range(init_lens):
                next_r = rStart + directions[direction_index % 4][0]
                next_c = cStart + directions[direction_index % 4][1]
                if next_r < 0 or next_r >= rows or next_c < 0 or next_c >= cols or visited_flag[next_r][next_c]:
                    rStart = next_r
                    cStart = next_c
                else:
                    res.append([next_r, next_c])
                    rStart = next_r
                    cStart = next_c
                    visited_flag[next_r][next_c] = True
                    cnt = cnt + 1
        return res

主要思路就是分析题目，其实每个固定的长度比如走1格子，其实是分为两个角度来走的，那么整体上就是1步往右，1步往下，2步往左，2步往上。依次这样来再结合判断条件。