德惠网站,营销宣传策划方案,网站开发与,wordpress 工业主题2024.1.7 题目来源我的题解方法一 哈希表方法二 数组 题目来源
力扣每日一题#xff1b;题序#xff1a;383
我的题解
方法一 哈希表 使用哈希表记录ransomNote中所需字符的数量#xff0c;然后遍历magazine并将哈希表中存在的对应的数量减一 时间复杂度#xff1a;O(nm… 2024.1.7 题目来源我的题解方法一 哈希表方法二 数组 题目来源
力扣每日一题题序383
我的题解
方法一 哈希表 使用哈希表记录ransomNote中所需字符的数量然后遍历magazine并将哈希表中存在的对应的数量减一 时间复杂度O(nm)。n表示ransomNote的长度m表示magazine的长度 空间复杂度O(n)。 public boolean canConstruct(String ransomNote, String magazine) {MapCharacter,Integer neednew HashMap();for(Character ch:ransomNote.toCharArray()){need.put(ch,need.getOrDefault(ch,0)1);}for(Character ch:magazine.toCharArray()){if(need.containsKey(ch))need.put(ch,need.get(ch)-1);}for(Character key:need.keySet()){if(need.get(key)0)return false;}return true;
}方法二 数组 由于都是小写字母所以可以使用数组代替哈希表 这里采用先求magazine中的各个字母的数量然后去匹配ransomNote这样可以在匹配的过程中判断magazine某个字符不存在或者该字符的数量不足以组成ransomNote可以提前结束后续的计算。 时间复杂度O(nm) 空间复杂度O(|S|)。|S|26 public boolean canConstruct(String ransomNote, String magazine) {int[] ransnew int[26];for(int i0;imagazine.length();i){char chmagazine.charAt(i);rans[ch-a];}for(int i0;iransomNote.length();i){char chransomNote.charAt(i);rans[ch-a]--;if(rans[ch-a]0)return false;}return true;}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
