算法leetcode

leetcode第241场周赛：状态定义不变，优化状态转移方式

字数统计: 4k字   |   阅读时长: 17分
, ,

摘要: 本文是 leetcode 第 241 周赛的记录。主要涉及的算法包括枚举子集、分类讨论、设计、动态规划、组合数学。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

这是 leetcode 第 241 场周赛，本场比赛的赞助公司是蓝湖，前 1000 名可获得简历内推机会：

蓝湖成立于2016年，是国内第一款为互联网团队打造的产品设计协作平台。为产品经理，设计师，工程师解决产品文档，设计图的管理和云端交付，生产资料的相关切图，标注和代码的自动生成。

蓝湖致力于帮助产研团队降低沟通成本、提高工作效率、优化工作流程。2021 年蓝湖完成 10 亿元 C+ 轮融资，称为 SaaS 赛道新晋独角兽。

详细信息可以参考官网：

1
https://lanhuapp.com/

本场比赛，依然是前 3 题完成时间很快但是 D 题没解决，最终成绩如下：

本场比赛考查的算法点都比较常规，包括枚举子集、分类讨论、哈希表、设计、动态规划。亮点是 D 题有两个点值得注意，一个是在状态定义不变的情况下，通过观察状态转移方程，找到另一种更高效的状态转移方式，从而对动态规划进行优化。第二个是该问题的状态转移方程实际上就是第一类斯特林数的递推公式。

各题的算法点以及参考文章如下：

A 题

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

1
2
3
提示：
1 <= nums.length <= 12
1 <= nums[i] <= 20

示例 1：
输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：

  • 空子集的异或总和是 0 。
  • [1] 的异或总和为 1 。
  • [3] 的异或总和为 3 。
  • [1,3] 的异或总和为 1 XOR 3 = 2 。
    0 + 1 + 3 + 2 = 6

示例 2：
输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：

  • 空子集的异或总和是 0 。
  • [5] 的异或总和为 5 。
  • [1] 的异或总和为 1 。
  • [6] 的异或总和为 6 。
  • [5,1] 的异或总和为 5 XOR 1 = 4 。
  • [5,6] 的异或总和为 5 XOR 6 = 3 。
  • [1,6] 的异或总和为 1 XOR 6 = 7 。
  • [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
    0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：
输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

算法: 枚举子集

首先我们枚举 n 个元素的所有 $2^{n}$ 个子集，然后枚举所有 n 个元素，判断枚举到的元素是否在当前子集中，如果在当前子集中，则更新当前子集的异或和。

其中枚举子集这个需求可以通过位运算的方式实现，代码如下:

1
2
3
4
for(i = 0; i <= (1 << n) - 1; ++i)
{
    ...
}

总时间复杂度 $O(N \times 2^{N})$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i <= (1 << n) - 1; ++i)
        {
            int sum = 0;
            for(int j = 0; j < n; ++j)
                if(i >> j & 1)
                    sum ^= nums[j];
            ans += sum;
        }
        return ans;
    }
};

B 题

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 “010” 和 “1010” 属于交替字符串，但 “0100” 不是。

任意两个字符都可以进行交换，不必相邻 。

示例 1：
输入：s = “111000”
输出：1
解释：交换位置 1 和 4：”111000” -> “101010” ，字符串变为交替字符串。

示例 2：
输入：s = “010”
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：
输入：s = “1110”
输出：-1

1
2
3
4
提示：

1 <= s.length <= 1000
s[i] 的值为 '0' 或 '1'

算法: 分类讨论

首先判断输入字符串能否变成交替字符串: 枚举所有字母，记录 0 的个数 n0, 1 的个数 n1。如果 abs(n1 - n0) > 1 则不可能转换为交替字符串，返回 -1。

下面就要看当原字符串可以转换成交替字符串的时候，具体如何转换。按照 n 的奇偶性讨论

(1) 如果 n 为奇数

n 为奇数则有两种情况

第一种是 n1 = n0 + 1, 此时统计类似于 “10101” 的形式的目标串与原串中有多少个字符不一样，记为 diff。

第二种是 n0 = n1 + 1, 此时统计类似于 “01011” 的形式的目标串与原串中有多少个字符不一样，记为 diff。

最终 diff / 2 就是答案。

(2) 如果 n 为偶数

统计类似于 “101010” 的形式的目标串与原串中有多少个字符不一样，记为 diff1。

统计类似于 “010101” 的形式的目标串与原串中有多少个字符不一样，记为 diff2。

最终 min(diff1, diff2) / 2 是答案。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    int minSwaps(string s) {
        int n = s.size();
        int n0 = 0, n1 = 0;
        for(const char& ch: s)
        {
            if(ch == '0')
                ++n0;
            else
                ++n1;
        }
        if(abs(n1 - n0) > 1)
            return -1;
        if(n & 1)
        {
            int diff = 0;
            if(n1 > n0)
            {
                // 10101 形式
                for(int i = 0; i < n; ++i)
                {
                    if(i & 1)
                        diff += s[i] != '0';
                    else
                        diff += s[i] != '1';
                }
            }
            else
            {
                // 01010 形式
                for(int i = 0; i < n; ++i)
                {
                    if(i & 1)
                        diff += s[i] != '1';
                    else
                        diff += s[i] != '0';
                }
            }
            return diff / 2;
        }
        else
        {
            int diff1 = 0; // 101010 形式
            int diff2 = 0; // 010101 形式
            for(int i = 0; i < n; ++i)
            {
                if(i & 1)
                {
                    diff1 += s[i] != '0';
                    diff2 += s[i] != '1';
                }
                else
                {
                    diff1 += s[i] != '1';
                    diff2 += s[i] != '0';
                }
            }
            return min(diff1, diff2) / 2;
        }
    }
};

C 题

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
  • void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
  • int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

提示：

1
2
3
4
5
6
7
8
1 <= nums1.length <= 1000
1 <= nums2.length <= 1e5
1 <= nums1[i] <= 1e9
1 <= nums2[i] <= 1e5
0 <= index < nums2.length
1 <= val <= 1e5
1 <= tot <= 1e9
最多调用 add 和 count 函数各 1000 次

算法: 基于哈希表的设计

FindSumPairs 内部数据结构设计：

1
2
3
unordered_map<int, int> mapping1;
unordered_map<int, int> mapping2;
vector<int> nums2;

其中 nums2 即为构造时传入的 nums2。mapping1 为 nums2 中各个数字出现的次数，mapping2 为 nums1 中各个数字出现的次数。

add(index, val) 接口要将 nums2[index] 的元素加 val，而做这个操作的时候，内部数据结构也要进行相应的修改。首先将 mapping2 中 nums2[index] 的次数减 1，然后将 nums2[index] 增加 val。然后将新的 nums2[index] 在 mapping2 中加 1，时间复杂度 $O(1)$。

对于 count(tot) 接口，枚举 nums1 中的所有元素 x，x 的个数为 mapping1[x]，问 nums1 中有多少个 tot - x，也就是 mapping2[tot - x]，mapping2[tot - x] * mapping1[x] 就是当前枚举的 nums1 中的元素 x 对答案的贡献。将 nums1 中所有元素的贡献加起来就是结果。时间复杂度 $O(N_{1})$。

注意由于 nums1 长度为 1e3，nums2 长度为 1e5，枚举元素必须是枚举短的，也就是 nums1 的元素，查询长的，也就是 mapping2。

代码 (C++)

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
28
29
30
31
32
33
34
35
class FindSumPairs {
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this -> nums2 = nums2;
        for(int x: nums1)
            ++mapping1[x];
        for(int x: nums2)
            ++mapping2[x];
    }

    void add(int index, int val) {
        --mapping2[nums2[index]];
        nums2[index] += val;
        ++mapping2[nums2[index]];
    }

    int count(int tot) {
        int ans = 0;
        for(auto item: mapping1)
        {
            int x = item.first, nx = item.second;
            int y = tot - x;
            if(mapping2.count(y) == 0)
                continue;
            int ny = mapping2[y];
            ans += nx * ny;
        }
        return ans;
    }

private:
    unordered_map<int, int> mapping1;
    unordered_map<int, int> mapping2;
    vector<int> nums2;
};

D 题

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。

例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。
给你 n 和 k ，返回符合题目要求的排列 数目 。由于答案可能很大，请返回对 1e9 + 7 取余 的结果。

1
2
3
提示：
1 <= n <= 1000
1 <= k <= n

示例 1：
输入：n = 3, k = 2
输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 2：
输入：n = 5, k = 5
输出：1
解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 3：
输入：n = 20, k = 11
输出：647427950
解释：总共有 647427950 (mod 1e9 + 7) 种能满足恰好有 11 根木棍可以看到的排列。

算法1: 动态规划 (超时)

定义 dp[i][k] 表示一共有 i 根棍子，重排列后从左侧可以恰好看见 k 根的方案数。

对于 n 根根子，要求 dp[n][K], 我们考虑最长的那根棍子所在的位置，加入它在位置 p，则 [p+1..n-1] 这些棍子怎么排对结果都没有影响，可以随便排，同时 [0..p-1] 这些棍子需要排成恰好可以看见 K - 1 根棍子的情形。问题变成了 dp[p][K - 1]。

1
dp[n][K] = comb(n - 1, p) * fab(n - 1 - p) * dp[p][K - 1]

基于这个思路我们可以写出基础动态规划算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义
dp[i][k] := 有 i 根根子，能看见 k 个的方案数

初始化
dp[0][1..] = 0 
dp[0][0] = 1
dp[1][1] = 1

答案 dp[n][K]

状态转移
dp[i][k] = sum(Comb(i - 1, p) * fab(i - 1 - p) * dp[j][k - 1])
    p 为最高棍子左侧的棍子数
    i - 1 - p 为最高棍子右侧的棍子数
    0 <= p <= i - 1

可以将 comb(0~n, 0~n) 和 fab(0~n-1) 的结果预处理出来。状态转移时 comb(i - 1, p) 和 fab(i - 1 - p) 这两步查询可以用了。

预处理的时间复杂度为 $O(n^{2})$，由于转移时间复杂度时间复杂度 $O(n)$，所以总时间复杂度 $O(n^{2}K)$。

代码(超时)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using ll = long long;
const int MOD = 1e9 + 7;

class Solution {
public:
    int rearrangeSticks(int n, int K) {
        fac = vector<int>(n, 1);
        fac[0] = 1;
        for(int i = 1; i < n; ++i)
            fac[i] = (fac[i - 1] * (ll)i) % MOD;

        comb = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
        for(int i = 0; i <= n; ++i)
            comb[i][0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= min(i, n); ++j)
                comb[i][j] = (comb[i - 1][j] + (ll)comb[i - 1][j - 1]) % MOD;

        dp = vector<vector<int>>(n + 1, vector<int>(K + 1, -1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            dp[i][0] = 0;
            dp[i][1] = fac[i - 1];
        }
        return solve(n, K);
    }

private:
    vector<vector<int>> dp;
    vector<vector<int>> comb;
    vector<int> fac;

    int solve(int n, int K)
    {
        if(dp[n][K] != -1)
            return dp[n][K];
        if(K > n)
            return dp[n][K] = 0;
        // 1 <= K <= n
        dp[n][K] = 0;
        for(int p = K - 1; p <= n - 1; ++p)
        {
            // p: 最高棍子左侧的棍子数
            // n - 1 - p: 最高棍子右侧的棍子数
            dp[n][K] = ((ll)dp[n][K] + ((comb[n - 1][p] * (ll)fac[n - 1 - p]) % MOD) * (ll)solve(p, K - 1)) % MOD;
        }
        return dp[n][K];
    }
};

算法2: 动态规划(改变状态转移方式)

考虑 dp[i][k] 的转移时，不是向算法 1 那样考虑最高的那根棍子在重排后放置在哪个位置，而是考虑最后一根棍子重排后可不可见。

  • 如果可见: 则最后一根棍子放的是最高的拿一根，问题变成了 dp[i - 1][k - 1]。
  • 如果不可见: 则记最后一根棍子放的是 x，则剩下的 i - 1 根棍子重排后需要见到 k 根，而无论怎么排，x 都对最终可以看到几根无影响，因此对于 i - 1 种 x 的选择，问题都会变成 dp[i - 1][k]。

根据以上思路，改变转移方式后的动态规划算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
状态定义
dp[i][k] := 有 i 根根子，能看见 k 个的方案数

初始化
dp[0][1..] = 0 
dp[0][0] = 1
dp[1][1] = 1

答案 dp[n][K]

状态转移
dp[i][k] = dp[i - 1][k - 1] + (i - 1) * dp[i - 1][k]

总时间复杂度 $O(nK)$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rearrangeSticks(int n, int K) {
        using ll = long long;
        const int MOD = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(K + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int k = 1; k <= K; ++k)
                dp[i][k] = (((i - 1) * (ll)dp[i - 1][k]) % MOD + (ll)dp[i - 1][k - 1]) % MOD;
        return dp[n][K];
    }
};

算法3: 第一类斯特林数

参考: 组合数学3-特殊计数序列,指数型母函数

第一类斯特林数问题描述

n 个人排成一个环，分成 m 个环，环内元素的顺序要保持原有顺序，有多少种方法。

等价问题：圆周上有 n 个点，能画出多少个不同的圈(一个点也算是圈)

递推公式

记答案为 $S(n, m)$

$S(n, 0) = 0, S(n, 1) = 1$

考虑从 n-1 到 n，新增的第 n 个元素有两种方案:

  1. n 自己是一个圈，其余 n - 1 形成 m - 1 个圈
  2. n 加入一个已有的圈，因为有序，有 n - 1 个位置可以插入，其余 n - 1 形成 m 个圈

因此可以写出递推公式

可以看出本题的 DP 转移方程与第一类斯特林数是一样的。

Share