贴纸拼词问题

贴纸,问题 · 浏览次数 : 44

小编点评

**算法和数据结构笔记** * 使用动态规划的缓存法来优化暴力递归。 * 数组存储目标字符串的最小贴纸数量。 * 缓存算法可以提高效率。 * 使用字符串数组存储目标字符串的最小贴纸数量。 **算法和数据结构笔记** * **动态规划**: * 优化暴力递归。 * 使用缓存法来提高效率。 * **数组**: * 存储目标字符串的最小贴纸数量。 * 数组存储目标字符串的最小贴纸数量。 **算法和数据结构笔记** * **Map**: * 存储目标字符串的最小贴纸数量。 * 使用Map来缓存目标字符串的最小贴纸数量。 **算法和数据结构笔记** * **字符串数组**: * 存储目标字符串的最小贴纸数量。 * 数组存储目标字符串的最小贴纸数量。 **一些优化技巧** * 使用缓存来优化暴力递归。 * 使用数组存储目标字符串的最小贴纸数量。 * 使用字符串数组存储目标字符串的最小贴纸数量。 * 使用Map来缓存目标字符串的最小贴纸数量。 * 使用字符串数组存储目标字符串的最小贴纸数量。

正文

贴纸拼词问题

作者:Grey

原文地址:

博客园:贴纸拼词问题

CSDN:贴纸拼词问题

题目描述

有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。以多次使用每个贴纸,每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能,则返回 -1 。

注意:在所有的测试用例中,所有的单词都是从 1000 个最常见的美国英语单词中随机选择的,并且 target 被选择为两个随机单词的连接。

题目链接:LeetCode 691. Stickers to Spell Word

暴力解法

定义递归函数

int process(String[] stickers, String target)

递归含义表示:stickers 作为贴纸数组,可以拼凑出 target 字符串的最小贴纸数量是多少。,如果无论如何都无法拼凑出 target,则返回无穷大,即:Integer.MAX_VALUE

接下来是 base case,如果 target 为空串,直接返回 0,表示无须任何贴纸就可以组成,即

        if (target.length() == 0) {
            // 目标是空串,只需要0张贴纸
            return 0;
        }

接下来是普遍情况,枚举 stickers 中每一个字符串 s,将 s 中包含的所有字符从 target 移除掉,然后看 target 剩下哪些字符,继续被 stickers 中的字符分解。

定义一个工具函数

String minus(String first, String target)

这个函数实现的功能就是:将 first 中包含的所有字符从 target 移除掉,然后看 target 剩下哪些字符,把剩下的字符按字典序排序后的结果字符串返回。

例如,first = "with", target = "thehat",target 移除掉 first 中的所有字符以后,得到 “aeht” (按字典序从小到大排序后)。

minus 方法如下

    private static String minus(String first, String target) {
        char[] s2 = target.toCharArray();
        char[] s1 = first.toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] dict = new int[26];
        for (char c : s2) {
            dict[c - 'a']++;
        }
        for (char c : s1) {
            dict[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            int times = dict[i];
            for (int m = 0; m < times; m++) {
                sb.append((char) (i + 'a'));
            }
        }
        return sb.toString();
    }

暴力解法完整代码如下

class Solution {
    public static int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length < 1 || target.length() < 1) {
            return 0;
        }
        int p = process(stickers, target);
        return p == Integer.MAX_VALUE ? -1 : p;
    }

    public static int process(String[] stickers, String target) {
        if (target.length() == 0) {
            // 目标是空串,只需要0张贴纸
            return 0;
        }
        int ways = Integer.MAX_VALUE;
        for (String s : stickers) {
            String rest = minus(s, target);
            if (target.length() != rest.length()) {
                // 有效
                ways = Math.min(process(stickers, rest), ways);
            }
        }
        return ways == Integer.MAX_VALUE ? Integer.MAX_VALUE : ways + 1;
    }

    private static String minus(String first, String target) {
        char[] s2 = target.toCharArray();
        char[] s1 = first.toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] dict = new int[26];
        for (char c : s2) {
            dict[c - 'a']++;
        }
        for (char c : s1) {
            dict[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            int times = dict[i];
            for (int m = 0; m < times; m++) {
                sb.append((char) (i + 'a'));
            }
        }
        return sb.toString();
    }
}

超时

image

上述暴力过程,可以做一些优化,比如

stickers 数组是字符串数组,可以转换成整型二维数组来表示

        int[][] st = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            String sticker = stickers[i];
            char[] chars = sticker.toCharArray();
            for (char c : chars) {
                st[i][c - 'a']++;
            }
        }

其中st[i]就是一个一维数组,表示 stickers[i] 这个字符串,

st[i][x] 存的就是 stickers[i] 这个字符串在 x 号位置的字符减去'a'的 ASCII 码值。

比如 stickers[i] == "abbc",那么 st[i] = {0,1,1,2}。

经过上述初始化,递归过程中的循环枚举 stickers 中字符串的过程,就可以做剪枝

        for (int[] first : stickers) {
            if (first[cs[0] - 'a'] > 0) {
                // 包含target首字母的字符串才考虑尝试
                String rest = minus(first, cs);
                if (rest.length() != target.length()) {
                    ans = Math.min(p2(stickers, rest), ans);
                }
            }
        }

其中if (first[cs[0] - 'a'] > 0)这个条件就是只考虑包含 target 首字母的的字符串才做尝试,因为 target 的首字符一定要被消除,所以先消除和后消除没差别。

经过上述优化的完整代码如下

class Solution {
    public static int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length < 1 || target.length() < 1) {
            return 0;
        }
        int[][] st = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            String sticker = stickers[i];
            char[] chars = sticker.toCharArray();
            for (char c : chars) {
                st[i][c - 'a']++;
            }
        }
        int res = p2(st, target);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static int p2(int[][] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }
        char[] cs = target.toCharArray();
        int ans = Integer.MAX_VALUE;
        for (int[] first : stickers) {
            if (first[cs[0] - 'a'] > 0) {
                // 包含target首字母的字符串才考虑尝试
                String rest = minus(first, cs);
                if (rest.length() != target.length()) {
                    ans = Math.min(p2(stickers, rest), ans);
                }
            }
        }
        return ans == Integer.MAX_VALUE ? Integer.MAX_VALUE : ans + 1;
    }

    public static String minus(int[] first, char[] target) {
        int[] count = new int[first.length];
        System.arraycopy(first, 0, count, 0, first.length);
        StringBuilder sb = new StringBuilder();
        for (char c : target) {
            if (count[c - 'a'] > 0) {
                count[c - 'a']--;
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

超时

image

使用动态规划中的缓存法 (可 AC)

在暴力递归中,增加一个参数 Map<String, Integer> map, 其中 key 是 target 字符串,value 是组成这个 target 字符串要耗费的最少贴纸数量,在递归函数中,增加如下逻辑

        if (map.containsKey(target)) {
            return map.get(target);
        }
        if (target.length() == 0) {
            map.put(target, 0);
            return 0;
        }

遍历 stickers 得到最少字符串的时候,把结果加入这个哈希表,

 map.put(target, ways);

即可。

完整代码如下

class Solution {
    public static String minus(int[] first, char[] target) {
        int[] count = new int[first.length];
        System.arraycopy(first, 0, count, 0, first.length);
        StringBuilder sb = new StringBuilder();
        for (char c : target) {
            if (count[c - 'a'] > 0) {
                count[c - 'a']--;
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    // 将字符串数组转换成二维数组
    public static int[][] build2D(String[] stickers) {
        int n = stickers.length;
        int[][] s = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] line = stickers[i].toCharArray();
            for (char c : line) {
                s[i][c - 'a']++;
            }
        }
        return s;
    }

    // 增加缓存
    // 可以AC
    public static int minStickers(String[] stickers, String target) {
        if (target == null || target.length() < 1) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        map.put("", 0);
        int res = p3(build2D(stickers), target, map);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static int p3(int[][] stickers, String target, Map<String, Integer> map) {
        if (map.containsKey(target)) {
            return map.get(target);
        }
        if (target.length() == 0) {
            map.put(target, 0);
            return 0;
        }
        char[] t = target.toCharArray();
        int ways = Integer.MAX_VALUE;
        // 每一张贴纸作为第一张贴纸,搞定后续的方法数
        for (int[] first : stickers) {
            // 搞定第一个字符的的贴纸才考虑后续过程
            if (first[t[0] - 'a'] > 0) {
                String rest = minus(first, t);
                // rest长度==target长度,说明没有搞定任何情况
                if (rest.length() != target.length()) {
                    ways = Math.min(p3(stickers, rest, map), ways);
                }
            }
        }
        ways = ways == Integer.MAX_VALUE ? Integer.MAX_VALUE : ways + 1;
        map.put(target, ways);
        return ways;
    }
}

更多

算法和数据结构笔记

与贴纸拼词问题相似的内容:

贴纸拼词问题

贴纸拼词问题 作者:Grey 原文地址: 博客园:贴纸拼词问题 CSDN:贴纸拼词问题 题目描述 有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。以多次使用每个贴纸,每个贴纸的数量是无限的。 返回你需要拼

【FAQ】视频编辑服务常见问题及解答

Q1问题描述 1、 访问贴纸等素材的时候提示“网络异常,请重试”怎么办? 2、 使用AI能力时,提示“errorCode:20124 errorMsg:Method not Allowed”? 解决方案 请做以下检查: 1、 在代码中检查鉴权信息是否已设置。如果未设置,可以通过api_key或Acc

[百度贴吧]部分CPU的SPEC2006int 结果

这些测试成绩基本上是本人自己测试的结果。下表中有来自spec官网的两个成绩,因为测试年份较早,系统环境和编译器都较老,测试成绩本人实测的还差,所以仅作为参考。部分测试启用了自动并行和附加的优化库,是为了追求较好的测试成绩,体现的不是普通用户系统环境和常规应用软件的性能水平。国产CPU任重道远,从当前

vue上通过krpano.js实现360全景图

首先贴出一些XML对应的函数,文件内容都有注释说明, 前端代码读取xml文件代码 // 初始化 window.embedpano({ xml: 0, target: 'pano', html5: 'only', mobilescale: 1.0, passQueryParameters: 'star

oidc-client.js踩坑吐槽贴

前言 前面选用了IdentityServer4做为认证授权的基础框架,感兴趣的可以看上篇<微服务下认证授权框架的探讨>,已经初步完成了authorization-code与implicit的简易demo(html+js 在IIS部署的站点),并实现了SSO,本想着将Demo迁移到vue工程是轻而易举

快来给你的宠物视频加个表情特效吧

摘要:我们将给猫贴一张卡通脸,给 Elon Musk 贴上小胡子,给小狗贴上驯鹿角! 本文分享自华为云社区《视频AI,给你的宠物加个表情特效!》,作者:HWCloudAI。 GAN 监督学习是一种联合端到端学习判别模型及其 GAN 生成的训练数据的方法。GANgealing将框架应用于密集视觉对齐问

好事发生,全力以赴 

在附近的自习室学习时,看到粘满爱心贴的一面墙: 好事发生,全力以赴 一切皆值得 祝所有看到的人都能 万事胜意,一夜暴富,心想事成!!!

糟了糟了,总部被SD画完都Q了,这篇深入浅出贴助你早日实现Stable Diffusion自由

想知道精致的AI插画是如何实现的吗?接下来,我将结合这个案例带你走进 Stable Diffusion 的世界,帮你系统性地了解并掌握这神奇AI绘画魔法。

Axure 标记元件

快照:可以用来表示控件的截图功能 箭头:有了连线,基本很少用它 便签:相关于便利贴,写些说明、备注, 标记:标记好数字,对应数字的标记做解释说明

解读Redis常见命令

Redis数据结构介绍 Redis是一个key-value的数据库,key一般是String类型,不过value的类型多种多样: 贴心小建议:命令不要死记,学会查询就好啦 Redis为了方便我们学习,将操作不同数据类型的命令也做了分组,在官网:https://redis.io/commands 可以