力扣第 168 场双周赛

558
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3722. 反转后字典序最小的字符串 - 力扣（LeetCode） ​

题目类型 ​

#枚举 #后缀数组

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def lexSmallest(self, s: str) -> str:
        ans = s
        for i in range(1, len(s) + 1):
            t = s[:i][::-1] + s[i:]
            ans = min(ans, t)
            t = s[:i] + s[i:][::-1]
            ans = min(ans, t)
        return ans

3723. 数位平方和的最大值 - 力扣（LeetCode） ​

题目类型 ​

#贪心 #枚举

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        ans = [0] * num
        for i in range(num):
            t = min(sum, 9)
            ans[i] = t
            sum -= t
        if sum:
            return ""
        return "".join(map(str, ans))

3724. 转换数组的最少操作次数 - 力扣（LeetCode） ​

题目类型 ​

#贪心 #分类讨论

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 1
        res = inf
        for x, y in zip(nums1, nums2[:-1]):
            ans += abs(x - y)
            if x <= nums2[-1] <= y or y <= nums2[-1] <= x:
                res = 0
            else:
                res = min(res, abs(x - nums2[-1]), abs(y - nums2[-1]))
        return ans + res

3725. 统计每一行选择互质整数的方案数 - 力扣（LeetCode） ​

题目类型 ​

#DP #倍数容斥

解题思路 ​

简单的多维 DP，基于 GCD 进行转移，查表法转移方程如下：

f[i+1][g]=∑j=0n−1f[i][gcd⁡(g,mat[i][j])]f[i + 1][g] = \sum_{j=0}^{n-1}f[i][\gcd(g, \text{mat}[i][j])]

刷表法转移方程如下：

f[i+1][gcd⁡(g,mat[i][j])]=f[i+1][gcd⁡(g,mat[i][j])]+f[i][g],(0<j<n)f[i + 1][\gcd(g, \text{mat}[i][j])] = f[i + 1][\gcd(g, \text{mat}[i][j])] + f[i][g], \quad (0 < j < n)

参考：两种方法：动态规划 / 倍数容斥（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def countCoprime(self, mat: List[List[int]]) -> int:
        MOD = 1_000_000_007
        n, m = len(mat), len(mat[0])
        f = [0] * 151
        for x in mat[0]:
            f[x] += 1
        for i in range(1, n):
            nf = [0] * 151
            for j in range(1, 151):
                for k in range(m):
                    g = gcd(j, mat[i][k])
                    nf[g] = (nf[g] + f[j]) % MOD
            f = nf[:]
        return f[1]
力扣第 473 场周赛
力扣第 167 场双周赛