LeetCode Cookbook 双指针 下篇 难点1

LeetCode Cookbook 双指针 下篇 难点1

   双指针下篇 hard 难度，这次题不多，整理出来，最近要开始找工作了，可能刷题和更新就不能那么频繁了，不过还是要学习继续参加周赛，往前看，迈步走，继续，努力，奋斗！

76. 最小覆盖子串

题目链接：76. 最小覆盖子串
题目大意：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

例如：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
1
2
3
4
5
6

解题思路：也不知道这道题是什么模板了，不是很容易想到。右面的指针一直移动，当字串所包含的元素已经涵盖 t 后，缩短左指针。动态维护数组与中间量。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        counter = collections.Counter(t)
        min_L, ans = float('inf'), ""
        n, cnt = len(s), len(t)
        L = R = 0
        #------------------------------
        while R < n:
            if counter[s[R]] > 0:
                cnt -= 1
            counter[s[R]] -= 1
            R += 1
            while cnt == 0:
                if min_L > R - L:
                    min_L = R - L
                    ans = s[L:R]
                if counter[s[L]] == 0:
                    cnt += 1
                counter[s[L]] += 1
                L += 1 
        #-------------------------------------
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

480. 滑动窗口中位数 （model-I）

题目链接：480. 滑动窗口中位数
题目大意：中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。例如：

• [2,3,4]，中位数是 3
• [2,3]，中位数是 (2 + 3) / 2 = 2.5
• 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

例如:

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
1
2
3
4
5
6
7
8
9
10
11
12

解题思路：巧用二分查找模块 bisect（）

array.insert(i, x)
Insert a new item with value x in the array before position i. 
Negative values are treated as being relative to the end of the array.

array.pop([i])
Removes the item with the index i from the array and returns it. 
The optional argument defaults to -1, so that by default the last item is removed and returned.

array.remove(x)
Remove the first occurrence of x from the array.
1
2
3
4
5
6
7
8
9
10

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        arr = []
        L,n = 0,len(nums)
        ans = []
        for R in range(n):
            # 动态维护含有k个元素的有序数组
            bisect.insort_left(arr, nums[R])
            while len(arr) > k:
                # 吐出原数组移动后吐出的左边界元素
                arr.pop(bisect.bisect_left(arr, nums[L]))
                L += 1
            if len(arr) == k:
                # 这一招委实厉害 不用再去判断奇偶数
                ans.append((arr[k // 2] + arr[(k - 1) // 2]) / 2.0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

992. K 个不同整数的子数组（model-I）

题目链接：992. K 个不同整数的子数组
题目大意：给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。子数组 是数组的 连续 部分。

例如：

输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
1
2
3
4
5
6
7

解题思路：关键点 self.atMostK(arr, K) - self.atMostK(arr, K - 1)

class Solution(object):
    def subarraysWithKDistinct(self, arr:List[int], K:int) -> int:
        return self.atMostK(arr, K) - self.atMostK(arr, K - 1)
    
    def atMostK(self, arr, K):
        n = len(arr)
        L,R = 0, 0
        counter = collections.Counter()
        cnt,ans = 0,0
        for R in range(n):
            if counter[arr[R]] == 0:
                cnt += 1
            counter[arr[R]] += 1
            while cnt > K:
                counter[arr[L]] -= 1
                if counter[arr[L]] == 0:
                    cnt -= 1
                L += 1
            ans += R-L+ 1
            # print(L, R, ans)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

995. K 连续位的最小翻转次数 （model-I)

题目链接：995. K 连续位的最小翻转次数
题目大意：给定一个二进制数组 nums 和一个整数 k 。k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。子数组 是数组的 连续 部分。

例如：

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解题思路：

1. q 内的元素个数代表翻转的次数
2. 0 翻转偶数次 1 翻转计数次
3. 翻转不完全，即使退出 返回 -1

class Solution(object):
    def minKBitFlips(self, arr:List[int], K:int) -> int:
        n = len(arr)
        q = collections.deque()
        ans = 0
        for i in range(n):
            # print(q)
            if q and i >= q[0] + K:
                q.popleft()
            if len(q) % 2 == arr[i]:
                if i +  K > n: return -1
                q.append(i)
                ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

363. 矩形区域不超过 K 的最大数值和（model-III）

题目链接：363. 矩形区域不超过 K 的最大数值和
题目大意： 给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。题目数据保证总会存在一个数值和不超过 k 的矩形区域。

例如：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
1
2
3

解题思路： 三分查找 三条边确定 一条边摇摆

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        res = -sys.maxsize
        for up in range(rows):
            arr = [0] * cols
            for down in range(up, rows):
                for c in range(cols):
                    arr[c] += matrix[down][c]
                prefix = [0]
                cur = 0
                for i in range(cols):
                    val = cur + arr[i]
                    if val == k:
                        return k 

                    index = bisect.bisect_left(prefix, val - k)
                    if index < len(prefix):
                        res = max(res, val - prefix[index])
                        # if index > 0:
                        #     res = max(res, val - prefix[index-1])
                    cur = val
                    bisect.insort_left(prefix, cur)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1074. 元素和为目标值的子矩阵数量（model-III）

题目链接：1074. 元素和为目标值的子矩阵数量
题目大意：给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

• 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
• 如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同（如：x1 != x1’），那么这两个子矩阵也不同。

例如：

输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
1
2
3

解题思路 ：比较 363. 矩形区域不超过 K 的最大数值和 少些细节，思路一致。

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(1, n + 1):
            presum = [0] * (m + 1)
            for j in range(i, n + 1):
                a = 0
                d = {0:1}
                for fixed in range(1, m + 1):
                    presum[fixed] += matrix[fixed-1][j-1]
                    a += presum[fixed]
                    if a - target in d:
                        ans += d[a - target]
                    if a in d:
                        d[a] += 1
                    else:
                        d[a] = 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

  滑动窗口或双指针这一块难题不少，尽力去理解出一种适用于自己的思考的逻辑套路，背模板肯定是不行的，它的难点在于与 图形、数九结构（哈希表、字典、双头链表）等内容融合后的循环内部条件的设定，还需要i多做几遍，多思考一下，像堆、栈、队列这些非常好用的数据结构一定要多多学习和熟悉。