【05-14】力扣每日一题_贴纸拼词 力扣

最近事情比较多，所以就简单写一下
本文首发于馆主君晓的博客，05-14

题目内容

  题目链接如，691. 贴纸拼词，题目截图如下：

题目分析

  这道题题目难度困难，最近事情比较多，我也没有仔细想，所以就拿的官方的代码，然后自己理解了一下。这里可以简化成动态规划的问题，首先是长度为m的字符串，拼接成该字符串，其需要的最少便签数目其实是从长度为m-1的字符串拼接成该字符串需要的最小便签数目转化而来。以下这段话来自力扣官方题解：

  在本题中，定义函数 $dp(mask)$，来求解不同状态的最小贴纸数，输入是某个子序列$mask$，输出是拼出该子序列的最小贴纸数。计算拼出$mask$，所需的最小贴纸数时，需要选取最优的 $sticker$，让其贡献部分字符，未被$stikcer$覆盖的其他字符$left$，需要用动态规划继续计算。在选取最优的$sticker$，时，需要遍历所有$sticker$，遍历到某个$sticker$时，计算$mask$和$sticker$字符的最大交集（非空），$mask$中这部分交集由$sticker$贡献，，剩余部分的最小贴纸数由动态规划继续计算，而$sticker$中不属于最大交集的剩下部分会被舍弃，不会产生任何贡献。遍历完所有$sticker$后，选取出所有贴纸数的最小值作为本次规划的结果，这一遍历$sticker$并根据剩余部分的最小贴纸数来计算当前$mask$的最小贴纸数的步骤完成了状态转移。边界情况是，如果$mask$为空集，则贴纸数为 0。

  在动态规划时，子序列可以用一个二进制数来表示。从低位到高位，某位为 0则表示在$target$ 中这一位不选取，为 1 则表示选取这一位，从而完成状态压缩的过程。代码实现上，本题解选择了记忆化搜索的方式。

代码实现

  c++代码实现如下：

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        // 获取目标字符串的长度
        int m = target.size();
        // 初始化dp数组 赋值为-1 这里1右移m位得到的是 2^m 表示长度为m的字符串 其子集有2^m个
        vector<int> dp(1 << m, -1);
        // 长度为0的字符串 需要的便签数目自然是0个
        dp[0] = 0;
        function<int(int)> helper = [&](int mask) {
            // 一旦dp数组的值发生改变 我们就直接返回这个就好 不用计算了 因为已经计算了
            if (dp[mask] != -1) {
                return dp[mask];
            }
            // 这里很关键 m+1表示 一个不可能的值 因为长度为m 那么最坏的情况 一个便签一个字符 也需要m个 这里m+1个表示不可能的情况
            dp[mask] = m + 1;
            for (auto & sticker : stickers) {
                // 遍历每一个便签
                int left = mask;
                // 记录当前便签 每一个字符出现的情况
                vector<int> cnt(26);
                for (char & c : sticker) {
                    cnt[c - 'a']++;
                }
                // 遍历目标字符串的每一个字符
                for (int i = 0; i < m; i++) {
                    // mask>>i & 1表示的是 字符串的第i位字符还存在 这里表示如果第i位字符还存在并且 字符表里存在该字符 那么就消耗掉
                    if ((mask >> i & 1) && cnt[target[i] - 'a'] > 0) {
                        cnt[target[i] - 'a']--;
                        // 因为消耗掉了 所以对应的位数置0 这里使用异或实现 相同为0 不同为1
                        left ^= 1 << i;
                    }
                }
                if (left < mask) {
                    // 如果一轮下来 有消耗 长度为mask的字符串中 需要消耗的最小便签数为 min(dp[mask], helper(left) + 1)
                    dp[mask] = min(dp[mask], helper(left) + 1);
                }
            }
            // 返回结果
            return dp[mask];
        };
        // 调用上面编写的函数
        int res = helper((1 << m) - 1);
        // 结果如果是m+1 就表示没有消耗 自然也就-1了
        return res > m ? -1 : res;
    }
};
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

结语

  杀人放火厉飞宇，救苦救难韩天尊！