[英雄星球七月集训LeetCode解题日报] 第5日 双指针

日报

• 第四题有点难。

题目

一、 392. 判断子序列

链接: 392. 判断子序列

1. 题目描述

2. 思路分析

• 单次询问的话就双指针。
• 如果是多次询问要上自动机。
• 之前写过模板[python刷题模板] 子序列自动机

3. 代码实现

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        j = 0
        n = len(t)
        for c in s:
            while j <n and t[j] != c:
                j += 1
            if j == n :
                return False
            j += 1
        return True
1
2
3
4
5
6
7
8
9
10
11

二、 541. 反转字符串 II

链接: 541. 反转字符串 II

1. 题目描述

2. 思路分析

python真香。

3. 代码实现

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        n = len(s)
        s = list(s)
        for i in range(0,n,2*k):
            s[i:min(n,i+k)] = reversed(s[i:min(n,i+k)])
        return ''.join(s)
1
2
3
4
5
6
7

三、 面试题 16.24. 数对和

链接: 面试题 16.24. 数对和

1. 题目描述

2. 思路分析

• 两数之和的扩展版，排序后对向双指针搜即可。

3. 代码实现

class Solution:
    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        l,r = 0,len(nums)-1
        ans = []
        while l<r:
            a = nums[l] + nums[r]
            if a == target:
                ans.append([nums[l],nums[r]])
                l+=1
                r-=1
            elif a < target:
                l+=1
            else:
                r-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、 696. 计数二进制子串

链接: 696. 计数二进制子串

1. 题目描述

2. 思路分析

DP。有点像回文串dp。

• 方程：令dp[i]为以i为终点的合法串的长度。
• 转移：
  • 如果一个字符和前边不相等，那这俩一定是合法串，长度2.
  • 如果相等，那前边数的管辖范围(长度d)之前，如果还有一个和它不同的字符，那它们可以一起组成一个长度d+2的串。
• 初始：一开始都是0
• 结果：不为0的串计数。

3. 代码实现

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        dp = [0] * n  # 以i为终点的合法子串长度
        for i in range(1,n):
            if s[i] != s[i-1]:
                dp[i] = 2
            else:
                l = i - dp[i-1] - 1
                if l >= 0 and s[l] != s[i]:
                    dp[i] = dp[i-1] + 2
        return sum(a>0 for a in dp)
1
2
3
4
5
6
7
8
9
10
11
12

参考链接

• [python刷题模板] 子序列自动机