力扣（LeetCode）双周赛#141题解

Q1.构造最小位运算数组Ⅰ

见 Q2。

Q2.构造最小位运算数组Ⅱ

位运算

题意

给定数组 nums，构造一个数组，满足 ans[i] OR (ans[i] + 1) = nums[i] 且 ans[i] 最小。若 ans[i] 不存在则为 。

题解

对于任意的 ， 其实就是把 的最后的 变为 ，如 。

要求 最小，最理想的情况是 末尾是一段连续的 ，然后加 和或运算。因此我们需要找出最后一个 的位置即可，方法有很多，可以用循环统计：

1
2
3
4
5
while((num&1) == 1) {
    cnt++;
    num >>= 1;
}
ans[i] = (((num << cnt)) | (1 << (cnt - 1))) - 1;

也可以不用循环，参考树状数组的 lowbit 函数直接得到最后一个 的位置：

1
2
3
int temp = ~x;
int lb = temp & -temp;
ans[i] ^= lb >> 1;

当然还有其他求出最后一个 的方法，这里不再过多赘述，请读者自行探索。

特别的，当且仅当 时不存在符合条件的 ans。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int[] ans = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i);
            if (num == 2) {
                ans[i] = -1;
            } else {
                int temp = ~num;
                int lb = temp & -temp;
                ans[i] ^= lb >> 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        for i, x in enumerate(nums):
            if x == 2:
                nums[i] = -1
            else :
                tmp = ~x
                lb = tmp & -tmp
                nums[i] ^= lb >> 1
        return nums
1
2
3
4
5
6
7
8
9
10
11
func minBitwiseArray(nums []int) []int {
    for i, x := range nums {
        if x == 2 {
            nums[i] = -1
        } else {
            t := ^x
            nums[i] ^= t & -t >> 1
        }
    }
    return nums
}

复杂度分析

  • 时间复杂度：，其中 是 nums 的长度。
  • 空间复杂度：。

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

动态规划

题意

给定两个字符串 source 和 pattern，从 source 中删除字符，其中删除的字符下标必须在 targetIndices 中出现过，要满足删除后 pattern 仍是 source 的子序列（子序列定义见题干），求最多的删除次数。

题解

本题思路和 LCS 类似。

从右向左遍历字符串，是求 source 的前 个字母和 pattern 前 个字母的问题， 和 分别是 source 和 pattern 的长度。有两种情况：

  1. 当 source[i] = pattern[j] 时，则这个字母不能被删除，问题变成 求 source 的前 个字母和 pattern 前 个字母的子问题；
  2. 否则，问题变成 求 source 的前 个字母和 pattern 前 个字母的子问题 。

可以发现问题和子问题都是相似的，因此可以用 递归（或 DFS） 解决。

定义 为 source 的前 个字母和 pattern 的前 个字母的状态，记录满足 pattern 是 source 的子序列最多的删除次数。

根据上面的思路定义状态转移方程：

其中 用来判断 source[i] 是否在 targetIndices 中，即：

在上述状态转移方程中，如果 source[i] = pattern[j]，字母匹配不能删除，继续求解子问题 。如果没有匹配上，则继续求解子问题 ，此时 source[i] 可被删除。

递归边界：当 时表示匹配完成。

递归入口：分别从两个字符串的最后一个位置开始匹配，即 。

剪枝优化：

  • 当 ，也就是待匹配的字符串长度小于模板字符串长度，不满足题意直接返回 。
  • 状态转移方程满足无后效性，因此可以记忆化，保存状态转移方程的结果，具体实现见下面的参考代码。

其他优化：

  • 我们需要知道 是否在 targetIndices 中，一种方法是将 targetIndices 转成集合，然后可以在 的时间复杂度求出；另一种方法是使用 指针，因为 targetIndices 是有序的，所以可以直接用一个变量来维护当前可删除的下标。
  • 在状态转移方程中， 只从 （这里忽略 ）转移而来，也就是不会从之前的状态转移过来，因此可以不写，类似 01背包 的滚动数组优化。

在下面的参考代码中，采用 递推 实现，一些实现细节略有差异，但思路与递归是一样的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxRemovals(String source, String pattern, int[] targetIndices) {
        char[] s = source.toCharArray();
        char[] p = pattern.toCharArray();

        int m = p.length;
        int[] f = new int[m + 1];
        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;

        int k = 0;
        for (int i = 0; i < s.length; i++) {
            if (k < targetIndices.length && targetIndices[k] < i) {
                k++;
            }
            int x = k < targetIndices.length && targetIndices[k] == i ? 1 : 0;
            for (int j = Math.min(i, m - 1); j >= 0; j--) {
                f[j + 1] += x;
                if (s[i] == p[j]) {
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
            }
            f[0] += x; // f[i + 1][0] = f[i][0] + x，因为遍历顺序所以要注意最后计算，防止状态被覆盖
        }
        return f[m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
        m = len(pattern)
        f = [0] + [-inf] * m
        k = 0
        for i, c in enumerate(source):
            if k < len(targetIndices) and targetIndices[k] < i:
                k += 1
            x = 1 if k < len(targetIndices) and targetIndices[k] == i else 0
            for j in range(min(i, m - 1), -1, -1):
                f[j + 1] += x
                if c == pattern[j] and f[j] > f[j + 1]:
                    f[j + 1] = f[j]
            f[0] += x
        return f[m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxRemovals(source string, pattern string, targetIndices []int) int {
    m := len(pattern)
    f := make([]int, m+1)
    for i := 1; i <= m; i++ {
        f[i] = math.MinInt
    }
    k := 0
    for i := range source {
        if k < len(targetIndices) && targetIndices[k] < i {
            k++
        }
        x := 0
        if k < len(targetIndices) && targetIndices[k] == i {
            x = 1
        }

        for j := min(i, m-1); j >= 0; j-- {
            f[j+1] += x
            if source[i] == pattern[j] {
                f[j+1] = max(f[j+1], f[j])
            }
        }
        f[0] += x
    }
    return f[m]
}

复杂度分析

  • 时间复杂度：，其中 为 source 的长度， 为 pattern 的长度。
  • 空间复杂度：。

Q4.安排活动的方案数

组合数学

题意

个被分到 个节目中，而节目可以没有人，对于有人表演的节目，会有一个 的分数。

对于两个方案，只要有一个人在不同的节目，或存在一个节目的分数不同，则认为这两个方案是不同的。

题解

首先，我们需要确定哪些节目是有人表演的。因为题目允许有节目是没有人表演的，很容易想到用 枚举。

枚举当前表演的节目个数为 ，不同的人在不同的节目视作不同的方案，因此是 有顺序的，即节目的方案数为 。

现在往这 个节目中塞人，可以把这些节目看成即可，也就是说 个人划分成 个非空集合的方案数，这个数在组合数学中称为 第二类斯特林数。

剩下的就简单了，对于每个节目有 种可能，即 。

最后根据乘法原理，总的方案数为：

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 1001;
    private static final int[][] s = new int[MX][MX];

    static {
        s[0][0] = 1;
        for (int i = 1; i < MX; i++) {
            for (int j = 1; j <= i; j++) {
                s[i][j] = (int) ((s[i - 1][j - 1] + (long) j * s[i - 1][j]) % MOD);
            }
        }
    }

    public int numberOfWays(int n, int x, int y) {
        long ans = 0;
        long perm = 1;
        long powY = 1;
        for (int i = 1; i <= Math.min(n, x); i++) {
            perm = perm * (x + 1 - i) % MOD;    //  x*(x-1)*(x-2)*...*2*1
            powY = powY * y % MOD;
            ans = (ans + perm * s[n][i] % MOD * powY) % MOD;
        }

        return (int) ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MOD = 1_000_000_007
MX = 1001

s = [[0] * MX for _ in range(MX)]
s[0][0] = 1
for i in range(1, MX):
    for j in range(1, i + 1):
        s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % MOD

class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:
        ans = 0
        perm = pow_y = 1
        for i in range (1, min(n, x) + 1):
            perm = perm * (x + 1 - i) % MOD
            pow_y = pow_y * y % MOD
            ans += perm * s[n][i] * pow_y
        return ans % MOD 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const mod = 1_000_000_007
const mx = 1001

var s [mx][mx]int

func init() {
	s[0][0] = 1
	for i := 1; i < mx; i++ {
		for j := 1; j <= i; j++ {
			s[i][j] = (s[i-1][j-1] + j*s[i-1][j]) % mod
		}
	}
}

func numberOfWays(n, x, y int) (ans int) {
	perm, powY := 1, 1
	for i := 1; i <= min(n, x); i++ {
		perm = perm * (x + 1 - i) % mod
		powY = powY * y % mod
		ans = (ans + perm*s[n][i]%mod*powY) % mod
	}
	return
}

复杂度分析

  • 时间复杂度：预处理的时间复杂度为 ，其中 是最多节目的个数。求方案数的时间复杂度为 ，其中 和 分别是节目个数和人数。
  • 空间复杂度：，主要用于存第二类斯特林数，其他均为常数的空间。