LeetCode 第141场双周赛个人题解

目录

构造最小位运算数组 I

原题链接

思路分析

AC代码

3315. 构造最小位运算数组 II

原题链接

思路分析

AC代码

3316. 从原字符串里进行删除操作的最多次数

原题链接

思路分析

AC代码

3317. 安排活动的方案数

原题链接

思路分析

AC代码

---

构造最小位运算数组 I

原题链接

构造最小位运算数组 I

思路分析

见Q2

AC代码

class Solution:def minBitwiseArray(self, nums: list[int]) -> list[int]:n = len(nums)ans = [-1] * nfor i, x in enumerate(nums):for b in range(x.bit_length() - 1, -1, -1):if (x >> b) & 1:t = x ^ (1 << b)if ((t + 1) | t) == x:ans[i] = tbreakreturn ans

3315. 构造最小位运算数组 II

原题链接

3315. 构造最小位运算数组 II

思路分析

考虑枚举二进制位

如果存在 的话，ans[i] 一定有一位为0 而原数该位为1，不可能存在两个位为0，因为我们+1最多贡献一个1

所以对于每个nums[i]，我们枚举二进制位为1的位b，令t = nums[i] ^ (1 << b)判断是否满足 t | (t + 1) = nums[i]，取最大的t即可

时间复杂度: O(NlogN)

AC代码

class Solution:def minBitwiseArray(self, nums: list[int]) -> list[int]:n = len(nums)ans = [-1] * nfor i, x in enumerate(nums):for b in range(x.bit_length() - 1, -1, -1):if (x >> b) & 1:t = x ^ (1 << b)if ((t + 1) | t) == x:ans[i] = tbreakreturn ans

3316. 从原字符串里进行删除操作的最多次数

原题链接

3316. 从原字符串里进行删除操作的最多次数

思路分析

编辑距离问题

很典的一类dp，我们定义 dp(i, j) 为 source 前 i 个字符 和 pattern 前 j 个字符匹配能够删除的最大字符数目

那么 枚举 i，j

如果 i - 1 在 target 内，可分为两种情况：

source[i - 1] == pattern[j - 1], dp[i][j] 可从 dp[i - 1][j - 1]转移，即不删除

然后dp[i][j] 可从 dp[i - 1][j] + 1转移，即删除

剩下的情况类似，无非就是 不+ 1 了，因为 i - 1不在target 内

时间复杂度：O(NM)

AC代码

class Solution:def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:n = len(source)  m = len(pattern)  st = set(targetIndices)  dp = [[-inf] * (m + 1) for _ in range(n + 1)]  dp[0][0] = 0cnt = 0for i in range(1, n + 1):  if (i - 1) in st:cnt += 1dp[i][0] = cntfor j in range(1, m + 1):  if i - 1 in st:dp[i][j] = dp[i - 1][j] + 1if source[i - 1] == pattern[j - 1]:  dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])  elif source[i - 1] == pattern[j - 1]:  dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j])else:  dp[i][j] = dp[i - 1][j]return max(dp[i][m] for i in range(n + 1))

3317. 安排活动的方案数

原题链接

3317. 安排活动的方案数

思路分析

第二类斯特林数

考虑 将 n 个人扔进 x 个集合，这是第二类斯特林数讨论的问题，即集合的分划

由于 集合互异，所以斯特林数应该乘上 factorial(x)

我们枚举 划分数目 i

那么划分方案就是 S(n, i) * fac(i)，此时打分可以随便打，即 y ^ i

时间复杂度：O(N^2)

AC代码

P = 1_000_000_007
N = 1000
memo = [[0] * (N + 1) for _ in range(N + 1)]
memo[0][0] = memo[1][1] = 1
for i in range(2, N + 1):memo[i][1] = 1for j in range(2, N + 1):memo[i][j] = memo[i - 1][j - 1] + j * memo[i - 1][j]
fac = [1] * (N + 1)
for i in range(2, N + 1):fac[i] = fac[i - 1] * i % P
comb = cache(comb)
class Solution:def numberOfWays(self, n: int, x: int, y: int) -> int:res = 0for i in range(1, min(n, x) + 1):res += memo[n][i] * comb(x, i) % P * pow(y, i, P) % P * fac[i] % Pif res >= P: res -= Preturn res