专业做律师网站的公司,企业网站seo实,最快的wordpress,服务质量好的网站设计制作作者#xff1a;前端小王hs 阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主 题库#xff1a;力扣 题目序号#xff1a;383#xff08;简单#xff09; 题目#xff1a;赎金信
给你两个字符串ransomNote 和 magazine#xff0c;判断ran… 作者前端小王hs 阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主 题库力扣 题目序号383简单 题目赎金信
给你两个字符串ransomNote 和 magazine判断ransomNote能不能由magazine里面的字符构成。 如果可以返回true否则返回false。magazine中的每个字符只能在ransomNote中使用一次。
示例1 输入ransomNote “a”, magazine “b” 输出false
示例2 输入ransomNote “aa”, magazine “aab” 输出true
解题思路 通过两道示例可以得知该题就是判断ransomNote的值是否包含在magazine中 解题的思路采取的是哈希表
可能有读者会问为什么采取哈希表采取这种方法的理由是什么 ①题目提到了magazine中的每个字符只能在ransomNote中使用一次这是一个计算题我们需要计算每个字符出现的次数那么哈希表刚好可以满足这个需求 ②如果对比使用数组那可能需要采取二维数组的形式去记录字符出现的字数如[[a,2],[b,1]]提高了复杂度
其实有个最简单的判断思路就是如果需要统计字符那么可以首选哈希表
下面来看一下具体的实现过程 ①先计算出magazine 中每个字符出现的次数那么在JS或者TS中就是以对象的形式去模拟哈希表也就是定义一个对象对象的属性包括每个字符属性值则是字符出现的数字
②遍历ransomNote字符串通过下标获取字符如果该字符不存在那么return反之在哈希表中的对应的字符的数字减1
这么说可能有些抽象以这个示例2为例 可以得到如下的哈希表
let magazineCounts {a:2b:1
}这是第一步
然后就遍历ransomNote字符串 遍历第一次的时候magazineCounts.a的数量从2变为1 遍历第二次的时候magazineCounts.a的数量从1变为0 遍历结束return true
解题代码
function canConstruct(ransomNote: string, magazine: string): boolean {// 使用对象来记录 magazine 中字符的出现次数const magazineCounts: { [char: string]: number } {};// 遍历 magazine 字符串更新字符计数for (let i 0; i magazine.length; i) {const char magazine[i];magazineCounts[char] (magazineCounts[char] || 0) 1;}// 遍历 ransomNote 字符串减去字符计数for (let i 0; i ransomNote.length; i) {const char ransomNote[i]; // 如果字符计数小于 0说明字符不够if (!magazineCounts[char] || magazineCounts[char] 1) {return false;}// 字符计数减1magazineCounts[char]--}return true;
};解题过程示例 略
