wordpress 下拉加载,北京seo专员,上饶市建设局培训网站,网站主体变更题目 给你两个字符串#xff1a;ransomNote 和 magazine #xff0c;判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以#xff0c;返回 true #xff1b;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1#xff1a; 输入ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以返回 true 否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1 输入ransomNote a, magazine b
输出false示例 2 输入ransomNote aa, magazine ab
输出false示例 3 输入ransomNote aa, magazine aab
输出true提示 1 ransomNote.length, magazine.length 105ransomNote 和 magazine 由小写英文字母组成 题目含义解析
赎金信歹徒为了要赎金并且防止字迹被认出所以从杂志或报纸中找对应的字母然后拼成一封信能不能拼成呢就要求杂志中的字符比赎金中的多。
这个问题的核心在于判断一个给定的字符串通常被视为“赎金信”或“目标字符串”是否完全可以由另一个字符串通常被视为“杂志”或“源字符串”中的字符且每个字符仅使用一次组成。
实际就是ransomNote中每个字符出现的次数要小于等于magazine中该字符出现的次数
比如ransomNoteabca ,a出现2次b,1次c1次magazineaabcda,a3次b:1次c:1次d:1次23,11,11,满足条件可以
思路
该问题可以用哈希表来解决
哈希表是根据关键码的值而直接进行访问的数据结构。例如数组可以根据下标来获取对应元素
哈希表能解决什么问题呢一般哈希表都是用来快速判断一个元素是否出现集合里
常见的三种哈希结构
数组set 集合map(映射)
该问题可以用一个哈希结构存储ransomNote每个字符出现次数然后遍历magazine当字符出现在哈希表中时次数减一如果次数已经是1那么再减一次就是0了直接移除掉该字符
如果次数大于1那么次数减一
结果判断map是否为空为空就说明都包含
代码
public boolean canConstruct(String ransomNote, String magazine) {int aransomNote.length();int bmagazine.length();MapCharacter,Integer map new HashMap();//将ransomNote中的字符放入到数组中键是字符值是字符次数for(int i0;ia;i){char c ransomNote.charAt(i);map.put(c,map.getOrDefault(c,0)1);}//for(int j0;jb;j){char d magazine.charAt(j);//map中包括当前字符if(map.containsKey(d)){//获取次数判断次数等于一再减掉一次就是0直接移除int time map.get(d);if(time1){map.remove(d);}else{//次数1map中该字符次数减一map.put(d,time-1);}}}//最后map是空就说明是可以否则就说明不可以return map.isEmpty();} 方法二使用数组当做哈希结构
由于题目中说明都是因为小写字符所以可以建立一个26个初始值为0的数组
数组下标就是当前字符-a,后的值数组的值存出当前字符出现次数
例如’c‘-a2,存储在下标为2的地方
遍历magazine存储当前字符出现次数
遍历ransomNote当前字符-’a‘ 位置处的值-1如果减掉之后已经小于0了那么就直接返回false
public static boolean canConstruct1(String ransomNote, String magazine) {//存储当前字符出现次数int[] numsnew int[26];//看magazine中每个字符出现次数for(char a:magazine.toCharArray()){nums[a-a];}//遍历ransomNotefor(char b :ransomNote.toCharArray()){//次数先-1nums[b-a]--;//次数小于0说明magazine中字符少直接返回falseif(nums[b-a]0){return false;}}return true;}
