【刷题篇】贴纸拼词

2023-10-19 23:10
文章标签 刷题 贴纸 拼词

本文主要是介绍【刷题篇】贴纸拼词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、题目
  • 二、题解
    • 2.1 方法一:递归尝试
    • 2.2方法二:剪枝
    • 2.3 方法三:缓存表

一、题目

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

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

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

二、题解

2.1 方法一:递归尝试

递归函数:
stickers :表示已有的贴纸
target:目标字符串
终止条件:
当target.length==0时,意味着目标字符串长度为0,那么直接返回0张贴纸

先假设每张贴张都作为第一张贴纸,使用minus函数剪掉target中的和first中的共有的字符,得到的rest作为下一次调用的target
如果rest的长度和target的长度相同,说明target中和当前的first中不存在重复的字符,就去尝试下一张贴纸作为第一张提位置的情况

返回需要的最少的贴纸时,如果是有效的解,需要加上使用的第一张贴纸
在这里插入图片描述
源码:
👿

   public static int minStickers1(String[] stickers, String target) {if(target==null||target.length()==0){return 0;}int ans=process1(stickers,target);return ans==Integer.MAX_VALUE?-1:ans;}public  static int process1(String[] stickers,String target){if(target.length()==0){return 0;}int min=Integer.MAX_VALUE;for (String first:stickers) {String rest=minus(target,first);if(target.length()!=rest.length()){min=Math.min(min,process1(stickers,rest));}}return  min+(min==Integer.MAX_VALUE?0:1);}public static String minus(String s1,String s2){char[] str1=s1.toCharArray();char[] str2=s2.toCharArray();int[] count=new int[26];for (char ch:str1) {count[ch-'a']++;}for (char ch:str2) {count[ch-'a']--;}StringBuilder sb=new StringBuilder();for (int i = 0; i <count.length ; i++) {if(count[i]>0){while(count[i]>0){sb.append(i+'a');count[i]--;}}}return sb.toString();}

2.2方法二:剪枝

思路:

  1. 用一个二维数组来存储所有的贴纸
    在这里插入图片描述
  2. 在方法一中,依次使用每一张贴纸都作为第一张贴纸去尝试,该方法的优化是选所有贴纸中具有目标贴纸的第一个字符的贴纸作为第一张贴纸去往下尝试,因为对于目标贴纸中的第一个字符在后续中总是要消掉的,放在前面先消掉,不会对结果有影响。(这样就实现了剪枝)
    在这里插入图片描述

源码:
😇

public static int process2(int[][] stickers,String target){if(target.length()==0) {return 0;}char[] t=target.toCharArray();int[] tcounts=new int[26];for (char ch:t) {tcounts[ch-'a']++;}int N=stickers.length;int min=Integer.MAX_VALUE;for (int i = 0; i < N; i++) {int[] sticker=stickers[i];//剪枝if(sticker[t[0]-'a']>0){StringBuilder builder=new StringBuilder();for (int j = 0; j <26 ; j++) {if(tcounts[j]>0){int nums=tcounts[j]-sticker[j];for (int k = 0; k < nums; k++) {builder.append((char)(j+'a'));}}}String rest=builder.toString();min=Math.min(min,process2(stickers,rest));}}return  min+(min==Integer.MAX_VALUE?0:1);}public static int minStickers2(String[] stickers, String target) {int  N=stickers.length;int[][] counts=new int[N][26];//生成所有贴纸的词频统计for (int i = 0; i < N; i++) {char[] str=stickers[i].toCharArray();for (char ch:str) {counts[i][ch-'a']++;}}int ans=process2(counts,target);return ans==Integer.MAX_VALUE?-1:ans;}

2.3 方法三:缓存表

在方法二的基础上多添加了一个缓存表

源码:
😐

public static int process3(int[][] stickers, String target, HashMap<String,Integer> dp) {if(dp.containsKey(target)){return dp.get(target);}if (target.length() == 0) {return 0;}char[] t=target.toCharArray();int[] tcounts=new int[26];for (char ch:t) {tcounts[ch-'a']++;}int N=stickers.length;int min=Integer.MAX_VALUE;for (int i = 0; i < N; i++) {int[] sticker=stickers[i];//剪枝if(sticker[t[0]-'a']>0){StringBuilder builder=new StringBuilder();for (int j = 0; j <26 ; j++) {if(tcounts[j]>0){int nums=tcounts[j]-sticker[j];for (int k = 0; k < nums; k++) {builder.append((char)(j+'a'));}}}String rest=builder.toString();min=Math.min(min,process3(stickers,rest,dp));}}int ans=min+(min==Integer.MAX_VALUE?0:1);dp.put(target,ans);return  ans;}public static int minStickers3(String[] stickers, String target) {int  N=stickers.length;int[][] counts=new int[N][26];//生成所有贴纸的词频统计for (int i = 0; i < N; i++) {char[] str=stickers[i].toCharArray();for (char ch:str) {counts[i][ch-'a']++;}}HashMap<String,Integer> dp=new HashMap<>();dp.put("",0);int ans=process3(counts,target,dp);return ans==Integer.MAX_VALUE?-1:ans;}

这篇关于【刷题篇】贴纸拼词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/242968

相关文章

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8

【笔记】数据结构刷题09

快速排序 215. 数组中的第K个最大元素 class Solution {public:int findKthLargest(vector<int>& nums, int k) {return divide(nums,0,nums.size()-1,nums.size()-k);}int divide(vector<int>& nums,int left,int right,int k)

C语言:刷题日志(1)

一.阶乘计算升级版 本题要求实现一个打印非负整数阶乘的函数。 其中n是用户传入的参数,其值不超过1000。如果n是非负整数,则该函数必须在一行中打印出n!的值,否则打印“Invalid input”。 首先,知道阶乘是所有小于及等于该数的正整数的积,并且0的阶乘为1。那么我们先来个简单的阶乘计算吧。 #include<stdio.h>int Fact(int n){if (n <=

【每日刷题】Day112

【每日刷题】Day112 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 1137. 第 N 个泰波那契数 - 力扣(LeetCode) 2. 面试题 08.01. 三步问题 - 力扣(LeetCode) 3. LCR 088. 使用最小花费爬楼梯 - 力扣(LeetCode) 1. 1137. 第 N 个泰波那契数 - 力扣(LeetCo

【数据结构】【java】leetcode刷题记录--链表

简介 链表是一种常见的基础数据结构,它由一系列节点组成,每个节点包含数据域和指向下一个节点的指针。在Java中,链表通常用于实现动态数据结构,因为它可以根据需要动态地增加或减少节点。 链表简介: 节点结构:链表中的每个元素称为节点(Node),每个节点包含两部分:数据域(存储数据)和指针域(存储下一个节点的地址)动态性:链表的长度不是固定的,可以根据需要动态地增减节点。内存分配:链表中的节点

代码随想录 刷题记录-28 图论 (5)最短路径

一、dijkstra(朴素版)精讲 47. 参加科学大会 思路 本题就是求最短路,最短路是图论中的经典问题即:给出一个有向图,一个起点,一个终点,问起点到终点的最短路径。 接下来讲解最短路算法中的 dijkstra 算法。 dijkstra算法:在有权图(权值非负数)中求从起点到其他节点的最短路径算法。 需要注意两点: dijkstra 算法可以同时求 起点到所有节点的最短路径权值不

【Hot100算法刷题集】哈希-01-两数之和(暴力枚举再优化,也不是哈希表的对手)

🏠关于专栏:专栏用于记录LeetCode中Hot100专题的所有题目 🎯每日努力一点点,技术变化看得见 题目转载 题目描述 🔒link->题目跳转链接 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那 两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任