【05-14】力扣每日一题

  • Post author:
  • Post category:其他


最近事情比较多,所以就简单写一下

本文首发于馆主君晓的博客,

05-14



题目内容

题目链接如,

691. 贴纸拼词

,题目截图如下:

image-20220515162443530



题目分析

这道题题目难度困难,最近事情比较多,我也没有仔细想,所以就拿的官方的代码,然后自己理解了一下。这里可以简化成动态规划的问题,首先是长度为

m

的字符串,拼接成该字符串,其需要的最少便签数目其实是从长度为

m-1

的字符串拼接成该字符串需要的最小便签数目转化而来。以下这段话来自力扣官方题解:

在本题中,定义函数



d

p

(

m

a

s

k

)

dp(mask)






d


p


(


m


a


s


k


)





,来求解不同状态的最小贴纸数,输入是某个子序列



m

a

s

k

mask






m


a


s


k





,输出是拼出该子序列的最小贴纸数。计算拼出



m

a

s

k

mask






m


a


s


k





,所需的最小贴纸数时,需要选取最优的



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





,让其贡献部分字符,未被



s

t

i

k

c

e

r

stikcer






s


t


i


k


c


e


r





覆盖的其他字符



l

e

f

t

left






l


e


f


t





,需要用动态规划继续计算。在选取最优的



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





,时,需要遍历所有



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





,遍历到某个



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





时,计算



m

a

s

k

mask






m


a


s


k









s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





字符的最大交集(非空),



m

a

s

k

mask






m


a


s


k





中这部分交集由



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





贡献,,剩余部分的最小贴纸数由动态规划继续计算,而



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





中不属于最大交集的剩下部分会被舍弃,不会产生任何贡献。遍历完所有



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





后,选取出所有贴纸数的最小值作为本次规划的结果,这一遍历



s

t

i

c

k

e

r

sticker






s


t


i


c


k


e


r





并根据剩余部分的最小贴纸数来计算当前



m

a

s

k

mask






m


a


s


k





的最小贴纸数的步骤完成了状态转移。边界情况是,如果



m

a

s

k

mask






m


a


s


k





为空集,则贴纸数为 0。

在动态规划时,子序列可以用一个二进制数来表示。从低位到高位,某位为 0则表示在



t

a

r

g

e

t

target






t


a


r


g


e


t





中这一位不选取,为 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;
    }
};



结语

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



版权声明:本文为qq_40401866原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。