Problem: 3474. 字典序最小的生成字符串

[TOC]

思路

处理 T

如果str1[i] == T，那就可以确定res[i:i+m]上的字母，很划算，所以优先处理T，如果有冲突就直接return ""

        n,m = len(str1),len(str2)  
        N = m+n-1      
        # 先处理T
        res = [''] * N
        for i in range(n):
            if str1[i] == 'F':
                continue
            
            for j in range(m):
                if res[i+j] == str2[j]:
                    continue
                
                if res[i+j] == '':
                    res[i+j] = str2[j]                    
                    continue
                # 有冲突
                return ""

处理 F

滚动哈希

假设dfs(i-1)满足题意，然后往res[i]中填入新的字母w，那么：
如果str1[i-m+1] == F时，需要判断res[i-m+1:i+1]是否等于str2，如果不等于才能满足题意F。

为了快速判断res[i-m+1:i+1]是否等于str2，也就是经典字符串匹配，这里就直接用滚动哈希了：

• pre数组，滚动哈希"前缀和"
• tgt: str2的字符串哈希值
• pow_m = pow(base,m,mod)：base的m次方
• res：填入结果数组

        # 回溯处理 F，并 贪心 获取结果
        global ans
        ans = ""
        # 滚动哈希
        pre = [0]
        base, mod = 1331, 10**9 + 7
        # base 的 m 次方
        pow_m = pow(base,m,mod)             
        tgt = 0
        for w in str2:
            tgt = (tgt * base + ord(w)) % mod 

回溯 + 贪心

在贪心填入新字母的过程中，需要同步更新与回溯：

• pre 哈希前缀和
• res 结果数组

        # 到第i位
        def dfs(i):
            # 第一次构造成功后，赋值给 ans
            global ans
            if i == len(res):
                ans = ''.join(res)
                return True
            
            # 当前值由于预处理`T`时已经填好了
            if res[i] != '':
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(res[i])) % mod)
                # 判断 F
                if i >= m - 1 and str1[i-m+1] == 'F' and (pre[-1] - pre[i+1-m] * pow_m) % mod == tgt:
                    # 回溯
                    pre.pop() 
                    return False
                if dfs(i+1):
                    return True
                # 回溯
                pre.pop() 
                return False
            
            # 贪心 填入新字母
            for w in ascii_lowercase:
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(w)) % mod)
                # 同步更新 res 结果集
                res[i] = w
                if i < m - 1:
                    if dfs(i+1):                        
                        return True
                # 判断 F 符合题意
                elif (pre[-1] - pre[i+1-m] * pow_m) % mod != tgt:
                    if dfs(i+1):                        
                        return True
                # 回溯
                pre.pop() 
                res[i] = ''              
            # 均不满足题意
            return False

预校验 F

周赛没时间看这题，被T3卡常卡吐了，赛后看了下，也没多少思路，就试试暴力回溯能不能过吧，竟然过了，我也不知道时间复杂度是多少，快倒是挺快的：

感觉不是正确做法，~有没有新样例能卡一下？~
找到个新增样例①卡了：

"FFFFFFFFFFFFFFFFFFFFFFFFTTFFT
"fff"

超时了，原因是str1后面加粗的部分是不满足题意的，因此在处理 T后，先预校验 F

        # 预校验 F
        for i in range(n):
            if str1[i] == 'F':
                for j in range(m):
                    # 只要存在一个字母不等即可
                    if res[i+j] != str2[j]:
                        break
                else:
                    # 字符串相等了，不满足 F
                    return ""

如果这个预校验 F通过了，那回溯部分肯定能获取结果。
加了这个预处理后，没超时了，但感觉还是有问题，暂时找不到新样例卡回溯

更多题目模板总结，请参考2024年度总结与题目分享

Code

class Solution:
    def generateString(self, str1: str, str2: str) -> str: 
        n,m = len(str1),len(str2)  
        N = m+n-1      
        # 先处理T
        res = [''] * N
        for i in range(n):
            if str1[i] == 'F':
                continue
            
            for j in range(m):
                if res[i+j] == str2[j]:
                    continue
                
                if res[i+j] == '':
                    res[i+j] = str2[j]                    
                    continue
                # 有冲突
                return ""
        
        # 回溯处理 F，并 贪心 获取结果
        global ans
        ans = ""
        # 滚动哈希
        pre = [0]
        base, mod = 1331, 10**9 + 7
        # base 的 m 次方
        pow_m = pow(base,m,mod)             
        tgt = 0
        for w in str2:
            tgt = (tgt * base + ord(w)) % mod                    
         
        # 到第i位
        def dfs(i):
            # 第一次构造成功后，赋值给 ans
            global ans
            if i == len(res):
                ans = ''.join(res)
                return True
            
            # 当前值由于预处理`T`时已经填好了
            if res[i] != '':
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(res[i])) % mod)
                # 判断 F
                if i >= m - 1 and str1[i-m+1] == 'F' and (pre[-1] - pre[i+1-m] * pow_m) % mod == tgt:
                    # 回溯
                    pre.pop() 
                    return False
                if dfs(i+1):
                    return True
                # 回溯
                pre.pop() 
                return False
            
            # 贪心 填入新字母
            for w in ascii_lowercase:
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(w)) % mod)
                # 同步更新 res 结果集
                res[i] = w
                if i < m - 1:
                    if dfs(i+1):                        
                        return True
                # 判断 F 符合题意
                elif (pre[-1] - pre[i+1-m] * pow_m) % mod != tgt:
                    if dfs(i+1):                        
                        return True
                # 回溯
                pre.pop() 
                res[i] = ''              
            # 均不满足题意
            return False
        
        dfs(0)    
                
        return ans

class Solution:
    def generateString(self, str1: str, str2: str) -> str: 
        n,m = len(str1),len(str2)  
        N = m+n-1      
        # 先处理T
        res = [''] * N
        for i in range(n):
            if str1[i] == 'F':
                continue
            
            for j in range(m):
                if res[i+j] == str2[j]:
                    continue
                
                if res[i+j] == '':
                    res[i+j] = str2[j]
                    continue
                # 有冲突
                return ""
        
        # 预校验 F
        for i in range(n):
            if str1[i] == 'F':
                for j in range(m):
                    # 只要存在一个字母不等即可
                    if res[i+j] != str2[j]:
                        break
                else:
                    # 字符串相等了，不满足 F
                    return ""
                    
        # 回溯处理 F，并 贪心 获取结果
        # 滚动哈希
        pre = [0]
        base, mod = 1331, 10**9 + 7
        # base 的 m 次方
        pow_m = pow(base,m,mod)             
        tgt = 0
        for w in str2:
            tgt = (tgt * base + ord(w)) % mod                    
         
        # 到第i位
        def dfs(i):
            if i == len(res):
                return True
            
            # 当前值由于预处理`T`时已经填好了
            if res[i] != '':
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(res[i])) % mod)
                # 判断 F
                if i >= m - 1 and str1[i-m+1] == 'F' and (pre[-1] - pre[i+1-m] * pow_m) % mod == tgt:
                    # 回溯
                    pre.pop() 
                    return False
                if dfs(i+1):
                    return True
                # 回溯
                pre.pop() 
                return False
            
            # 贪心 填入新字母
            for w in ['a','b']:
                # 同步更新 pre 哈希前缀和
                pre.append((pre[-1] * base + ord(w)) % mod)
                # 同步更新 res 结果集
                res[i] = w
                if i < m - 1:
                    if dfs(i+1):                        
                        return True
                # 判断 F 符合题意
                elif (pre[-1] - pre[i+1-m] * pow_m) % mod != tgt:
                    if dfs(i+1):                        
                        return True
                # 回溯
                pre.pop() 
                res[i] = ''              
            # 均不满足题意
            return False

        dfs(0)
        return "".join(res)
        

Problem: 3666. 使二进制字符串全为 1 的最少操作次数

[TOC]

思路

公式推导

先计数，假设有a个0，则b = n - a，假设选取ta个0进行反转，ta范围推导如下：
$$
0 \le ta \le a \
ta \le k \
k - ta \le b \
k-b \le ta \
\Downarrow \

\max(0,k - b) \le ta \le \min(a,k)
$$

又因为 tb = k - ta，即选取tb个1进行反转
因此a可以扩展为[mn_a,mx_a]:
$$
a + tb - ta = a + k - ta * 2 \
mn_a = a + k - mx_ta * 2 \
mx_a = a + k - mn_ta * 2
$$

        # 扩展区间
        def getExArea(a):
            b = n - a
            # max(0,k - b) <= ta <= min(a,k)
            mn_ta = max(0,k - b) 
            mx_ta = min(a,k)

            #  a + k - ta - ta
            mn_a = a + k - mx_ta * 2
            mx_a = a + k - mn_ta * 2
            
            return mn_a,mx_a

上面是第一次扩展，那下一次扩展 $a ∈ [mn_a,mx_a] $ 呢？遍历区间内的值肯定超时。
其实，对于每一个a值，就是一个滑动窗口的过程，得到的区间是具有单调性的，因此我们只需要关注区间的边界值即可，因此每一次都对区间边界值进行扩展，得到一个更大的区间即可

区间扩展出口

当满足以下两个条件即可终止扩展：

• $k ∈ [mn_a,mx_a] $
• $ k\ &\ 1 = mn_a\ &\ 1 $

第一个条件很容易理解，a可以满足等于k，那下一次操作直接把k个0转化成1就好了。

第二个条件就是奇偶性相等，为何要满足这个条件呢？其实模拟一下操作就知道了，假设
a = 9, b = 11, k = 5

虽然扩展后，k ∈ [4,14] ，但很明显这个区间范围内的值是公差为2的等差数列，得不到a = k = 5，因此要满足与k奇偶性相等才行。

那如何判断满足不了题意呢？扩展区间过程中，如果还没达到扩展出口条件，且出现扩展区间重复，那就满足不了题意了，return -1

        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1

        res = 0
        la,ra = a,a
        dt = set()
        dt.add((la,ra))
        while la:
            if la <= k <= ra and la&1 == k&1:
                res += 1
                break
            mn_la,mx_la = getExArea(la)
            mn_ra,mx_ra = getExArea(ra)

            nla = min(mn_la,mn_ra)
            nra = max(mx_la,mx_ra)
            # 扩展过了
            if (nla,nra) in dt:
                return -1
            
            la,ra = nla,nra
            dt.add((la,ra))
            res += 1
        
        return res

贪心优化

• 如果 a >= 2 * k，可以贪心的a -= k，且操作结果+1
• 如果 b >= 2 * k，可以贪心的b -= k

        n = len(s)
        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1
        b = n - a
        # 贪心优化
        res = 0
        while a >= 2 * k:
            res += 1
            a -= k
            b += k
        
        while b >= 2 * k:
            b -= k
        n = a + b

更多题目模板总结，请参考2024年度总结与题目分享

Code

###Python3

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        '''
        计数：
        a,b 分别为 0,1的数目
        0 的数目区间扩展 区间扩展
        若 k 为偶数
        (a,b)

        左扩展
        ta <= a
        ta <= k
        k - ta <= b
        max(0,k - b) <= ta <= min(a,k)
        tb = k - ta

        a = a + tb - ta
        a = a + k - ta - ta
        b = n - a

        求出 a,b 对应最小值，最大值
        '''
        n = len(s)
        # 获取 0 的个数
        a = 0
        for w in s:
            if w == '0':
                a += 1
        b = n - a
        # 贪心优化
        res = 0
        while a >= 2 * k:
            res += 1
            a -= k
            b += k
        
        while b >= 2 * k:
            b -= k
        n = a + b
        
        # 扩展区间
        def getExArea(a):
            b = n - a
            # max(0,k - b) <= ta <= min(a,k)
            mn_ta = max(0,k - b) 
            mx_ta = min(a,k)

            #  a + k - ta - ta
            mn_a = a + k - mx_ta * 2
            mx_a = a + k - mn_ta * 2
            
            return mn_a,mx_a


        la,ra = a,a
        dt = set()
        dt.add((la,ra))
        while la:
            if la <= k <= ra and la&1 == k&1:
                res += 1
                break
            mn_la,mx_la = getExArea(la)
            mn_ra,mx_ra = getExArea(ra)

            nla = min(mn_la,mn_ra)
            nra = max(mx_la,mx_ra)
            # 扩展过了
            if (nla,nra) in dt:
                return -1
            
            la,ra = nla,nra
            dt.add((la,ra))
            res += 1
        
        return res