[LeetCode周赛复盘] 第 111 场双周赛20230819-Toy模板网

这篇具有很好参考价值的文章主要介绍了[LeetCode周赛复盘] 第 111 场双周赛20230819。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、本周周赛总结

T1 对向双指针。
T2 子序列/同向双指针。
T3 LIS/状态DP。
T4 数位DP。

2824. 统计和小于目标的下标对数目

1. 题目描述

[LeetCode周赛复盘] 第 111 场双周赛20230819,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

这里只讨论O(n)做法。

类似两数之和，由于顺序无关，把数据排序。
设置l,r=0,n-1。
若a[l]+a[r]<target,则a[l]+ 任意a[l+1…r]都<target。则这r-l个数都可以和l组队。

3. 代码实现

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = left = 0
        right = len(nums) - 1
        while left < right:
            if nums[left] + nums[right] < target:
                ans += right - left
                left += 1
            else:
                right -= 1
        return ans

2825. 循环增长使字符串子序列等于另一个字符串

1. 题目描述

[LeetCode周赛复盘] 第 111 场双周赛20230819,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

子序列问题，都有个贪心思想：当前能匹配就匹配，匹配不了再看下一个。
一般外层循环更长的那个，代码会好写一些。

3. 代码实现

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        n = len(str2)
        j = 0 
        for c in str1:
            if j < n:
                d = ord(c)+1
                if d > ord('z'):
                    d = ord('a')
                if c == str2[j] or chr(d) == str2[j]:
                    j += 1     
        return j == n

2826. 将三个组排序

1. 题目描述

[LeetCode周赛复盘] 第 111 场双周赛20230819,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

本质是LIS，如果k不是3而是更大的1e4，则只能LIS。
状态机DP可以用RMQ来优化，本身也是LIS的另一种做法。

3. 代码实现

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:        
        dp = []
        for v in nums:
            if not dp or v >=dp[-1]:
                dp.append(v)
            else:
                p = bisect_right(dp,v)
                dp[p] = v
        return len(nums)-len(dp)
        # n = len(nums)
        # f = [1]*n 
        # for i in range(1,n):
        #     for j in range(i):
        #         if nums[i] >= nums[j]:
        #             f[i] = max(f[i],f[j]+1)
        # return len(nums) - max(f)

2827. 范围中美丽整数的数目

1. 题目描述

[LeetCode周赛复盘] 第 111 场双周赛20230819,力扣周赛复盘,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-672417.html

2. 思路分析

 数位DP+前缀和作差

条件有两个：奇数偶数个数相同、被k整除。
第一个条件可以向后传递两个个数。
第二个条件可以用同余向后传递，即(p*10+j)%k
剩下的就是套板子。

注意这里is_num我省略了，因为可以用even和odd来检查。
灵神的写法是不省略is_num，但even和odd压缩成一个diff。差不多。

3. 代码实现

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:

        def f(s):
            n = len(s)

            @cache
            def f(i, p, even, odd, is_limit):
                if i == n:
                    return int(even+odd>0 and even == odd and p == 0)
                up = int(s[i]) if is_limit else 9
                down = 0 if even+odd else 1
                ans = 0
                if not even+odd:
                    ans += f(i + 1, 0, 0, 0, False)
                for j in range(down, up + 1):
                    ans += f(i + 1, (p * 10 + j) % k, even + (not j & 1), odd + (j & 1), is_limit and j == up)

                return ans

            return f(0, 0, 0, 0, True)

        return f(str(high)) - f(str(low - 1))