目录
构造最小位运算数组 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