当前位置:   article > 正文

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

贴纸拼词 力扣

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

题目内容

  题目链接如,691. 贴纸拼词,题目截图如下:

image-20220515162443530

题目分析

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

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

  在动态规划时,子序列可以用一个二进制数来表示。从低位到高位,某位为 0则表示在 t a r g e t target 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

结语

  杀人放火厉飞宇,救苦救难韩天尊!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/810943
推荐阅读
相关标签
  

闽ICP备14008679号