一、本周周賽總結

• 這場可惜了。
• T1 模擬。
• T2 模擬。
• T3 倒序計算。
• T4 同時限制上下界的數位DP。
  

6462. 最小化字符串長度

6462. 最小化字符串長度

1. 題目描述

2. 思路分析

題意仔細想一下就會發(fā)現，其實會將每個字符僅留1個。

3. 代碼實現

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return  len(set(s))

6424. 半有序排列

6424. 半有序排列

1. 題目描述

2. 思路分析

• 由于只能相鄰交換來移動，因此每次只能移動1步。
• 那么分別找到1和n的位置，計算他們移動距離。
  • 額外的，若1在n的右邊，移動路徑交叉，那么可以1向左時，n會免費向右一下，因此答案-1。

3. 代碼實現

class Solution:
    def semiOrderedPermutation(self, a: List[int]) -> int:
        n = len(a)
        x,y = a.index(1),a.index(n)
        return x + n-y-1-(x>y)
     

6472. 查詢后矩陣的和

6472. 查詢后矩陣的和

1. 題目描述

2. 思路分析

你就記住，最小化最大值=二分、覆蓋求整體=逆序

• 逆序處理后，每次格子的貢獻是確定的，只需要記錄每次操作有多少個格子被修改即可。
• 那么用哈希表儲存已被修改的行/列，若這行/列已被改過，那這次操作可以跳過。
  • 否則記錄操作這行時，有多少個空位。即 n - len(ys)。

3. 代碼實現

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        ans = 0
        xs = set()
        ys = set()
        for t,i,val in queries[::-1]:          
            if t == 0:
                if i not in xs:
                    ans += val * (n-len(ys))
                    xs.add(i)                 
            else:
                if i not in ys:
                    ans += val *(n-len(xs))
                    ys.add(i)
        return ans

6396. 統(tǒng)計整數數目

6396. 統(tǒng)計整數數目

1. 題目描述

文章來源地址http://www.zghlxwxcb.cn/news/detail-475012.html

2. 思路分析

• 套數位DP板子即可，這題同時限制了上下界，那么不用考慮前邊填沒填數的事（省去is_num參數）。
• 除了上下界限制，同時傳一個s作為數字求和進去。當i遍歷到n時，判斷方案是否合法，返回1/0。
• 另外中途s已經超過上限的話可以提前退出。

• 參見[python刷題模板] 數位DP
• 加餐，同時限制上下界的數位dp1742. 盒子中小球的最大數量

3. 代碼實現

MOD = 10**9 + 7
class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        m,n = len(num1),len(num2)
        num1 = '0'*(n-m) + num1
        @cache
        def f(i,s,up_limit,down_limit):
            if i == n:
                if   min_sum<=s<=max_sum:
                    return 1
                else:
                    return 0
            if s > max_sum:
                return 0
            up = int(num2[i]) if up_limit else 9 
            down = int(num1[i]) if down_limit else 0 
            ans = 0
            
            for j in range(down,up+1):
                ans += f(i+1,s+j,up_limit and j==up,down_limit and j == down)
                ans %= MOD 
            return ans 
        return f(0,0,True,True)                       

參考鏈接

到了這里，關于[LeetCode周賽復盤] 第 348場周賽20230604的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！