Slide Window

Someone2022年4月27日大约 5 分钟

Slide Window

Abstract

双指针技术可以解决很多问题,在面试中往往能成为加分项。

Problems

LC2024 考试的最大困扰度

题目要求 输入:answerKey = "TFFT", k = 1

输出:3

解释:我们可以将最前面的 'T' 换成 'F' ,得到 answerKey = "FFFT" 。 或者,我们可以将第二个 'T' 换成 'F' ,得到 answerKey = "TFFF" 。 两种情况下,都有三个连续的 'F' 。

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximize-the-confusion-of-an-examopen in new window 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

剑指offer 57 和为 S 的连续正数序列

遇到连续序列,应当要想到双指针。

小明很喜欢数学,有一天他在做数学作业时,要求计算出 9~16 的和,他马上就写出了正确答案是 100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为 100 (至少包括两个数)。没多久,他就得到另一组连续正数和为 100 的序列: 18,19,20,21,22。

现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

这道题目在 leetcode 上也有类似的:

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9 输出:[[2, 3, 4],[4, 5]]

剑指 Offer 57 - II. 和为s的连续正数序列open in new window

其解法如下:

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        left = 1
        right = 2
        res = []
        while left < right:
            sums = (left + right) * (right - left + 1) / 2
            if sums == target:
                res.append(list(range(left, right + 1)))
                right += 1
                sums += right
            elif sums < target:
                right += 1
                sums += right
            else:
                left += 1
                sums -= left
        return res

注意到一个细节:在相等判断以后应当右移,以免陷入死循环。

sum1 我们套入了区间求和公式:

sum=(l+r)(rl+1)/2 sum = (l + r) * (r - l + 1) / 2

公式的含义是,在 [l, r] 区间内的区间和,(首项 + 尾项) * 项数 / 2 的原理。

我们起始的 right 从 2 开始,当区间和的值比较小的时候,我们把 right 指针右移,如果区间和比较大的时候,我们把 left 指针左移。

来一个看不懂的解法,可以慢慢理解:

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        if target <= 2: # 最小的target应该是3 -> [1, 2]
            return []
        res = []
        for n in range(2, (target+1)//2): # 观察最大值为(target+1)//2,比如15最大值为8,
            temp = target - n*(n-1)//2
            if temp <= 0:
                break
            if not temp % n: # 胜哥强
                res.append([temp // n + i for i in range(n)])
        return res[::-1]

和为 S 的两个数

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        l = 0
        r = len(array) - 1
        while l < r:
            sum1 = array[l] + array[r]
            if sum1 == tsum:
                break
            elif sum1 > tsum:
                r -= 1
            else:
                l += 1
        if l >= r:
            return []
        return [array[l], array[r]]

LC1513 仅含 1 的子串数

给你一个二进制字符串 s(仅由 '0' 和 '1' 组成的字符串)。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

示例 1:

输入:s = "0110111" 输出:9 解释:共有 9 个子字符串仅由 '1' 组成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-substrings-with-only-1s 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这个题目可以用滑动窗口,但是也存在其他巧妙的方法。

面试题17.18 最短超串

假设你有两个数组,一个长一个短,短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组,其出现顺序无关紧要。 返回最短子数组的左端点和右端点,如有多个满足条件的子数组,返回左端点最小的一个。若不存在,返回空数组。

示例 1:

输入:

big = [7, 5, 9, 0, 2, 1, 3, 5, 7, 9, 1, 1, 5, 8, 8, 9, 7]

small = [1, 5, 9]

输出: [7, 10]

来源:力扣(LeetCode) 链接:<https://leetcode-cn.com/problems/shortest-supersequence-lcciopen in new window> 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

求解思路:

  1. 设置右指针,然后不停滑动右指针直到满足题目的条件,右指针滑动到最右边则不存在结果

  2. 右指针位置确定后,滑动左指针,直到不满足要求

  3. 使用一个 hash_map 来记录窗口中数字出现的次数

LC905 按奇偶排序数组

给你一个整数数组 nums,将 nums 中的的所有偶数元素移动到数组的前面,后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1:

输入:nums = [3, 1, 2, 4] 输出:[2, 4, 3, 1] 解释:[4, 2, 3, 1]、[2 ,4, 1, 3] 和 [4, 2, 1, 3] 也会被视作正确答案。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-array-by-parityopen in new window 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题目是需要我们把所有的偶数移到奇数前面, 很容易想到双指针的解法:

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        while left < right:
            while left < right and nums[left] % 2 == 0:
                left += 1
            while left < right and nums[right] % 2 != 0:
                right -= 1
            if left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return nums

在实现这个解法的时候,需要注意以下几点:

  1. 考虑到边界条件,如果 nums = [0] 这种情况下,双指针的适用性。我们的条件是符合的。
  2. 考虑到每次需要 left +=1 或者 right -= 1, 再加上 while 的判断,我们需要在每次判断的时候判断下是否越界,这点很容易忽视。
  3. 在代码第 5 行,我们判断了 nums[left] % 2 == 0, 也就是说,left 指针指向的到第 9 行代码的时候已经必然是一个奇数了,我们可以放心交换!
Loading...