Leetcode 每日一题 383.赎金信
目录
问题描述
输入输出格式
示例
算法思路
通过图片
算法步骤
代码实现
复杂度分析
题目链接
结论
问题描述
给定两个字符串ransomNote和magazine，我们需要判断ransomNote是否可以完全由magazine中的字符构成。这里的“构成”意味着magazine中的每个字符只能在ransomNote中使用一次。
输入输出格式
- 输入：两个字符串
ransomNote和magazine。 - 输出：一个布尔值，如果
ransomNote能由magazine构成，则返回true；否则返回false。
示例
-
输入：
ransomNote = "a",magazine = "b"
输出：false -
输入：
ransomNote = "aa",magazine = "ab"
输出：false -
输入：
ransomNote = "aa",magazine = "aab"
输出：true
算法思路
这个问题可以通过使用哈希表（HashMap）来解决。我们的目标是统计ransomNote中每个字符出现的次数，并检查magazine中是否有足够的相同字符来构成ransomNote。
通过图片
算法步骤
- 创建一个
HashMap<Character, Integer>来存储字符及其在ransomNote中出现的次数。 - 遍历
ransomNote，对于每个字符，如果它已经在HashMap中，则增加其计数；否则，将其添加到HashMap中，并设置计数为1。 - 遍历
magazine，对于每个字符，如果它已经在HashMap中，则减少其计数；否则，将其添加到HashMap中，并设置计数为-1。 - 再次遍历
HashMap，检查每个字符的计数是否大于0。如果有任何字符的计数大于0，则说明ransomNote不能由magazine构成，返回false。 - 如果所有字符的计数都不大于0，则说明
ransomNote可以由magazine构成，返回true。
代码实现
java
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> map = new HashMap<>();
// 统计ransomNote中每个字符的出现次数
for (int i = 0; i < ransomNote.length(); i++) {
char ch = ransomNote.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// 从magazine中减去字符的出现次数
for (int i = 0; i < magazine.length(); i++) {
char ch = magazine.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) - 1);
}
// 检查是否有字符的计数大于0
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue() > 0) {
return false;
}
}
return true;
}
}复杂度分析
- 时间复杂度：O(n + m)，其中n是
ransomNote的长度，m是magazine的长度。我们需要遍历两个字符串各一次。 - 空间复杂度：O(1)，因为我们只使用了一个固定大小的
HashMap来存储字符计数，而字符集的大小是固定的（小写英文字母）。
题目链接
383. 赎金信 - 力扣（LeetCode）
结论
通过使用哈希表，我们可以高效地解决这个问题，时间复杂度为线性，空间复杂度为常数。这种方法简单且有效，适用于处理大规模数据。
哈希表（HashMap）是Java中非常常用的数据结构，它提供了快速的插入、删除和查找操作。以下是一些哈希表的常用方法：
-
put(K key, V value)：
- 将指定的值与此映射中的指定键关联。
- 如果映射之前包含键的映射关系，则值会被更新。
- 返回旧值，如果没有旧值则返回
null。
-
get(Object key)：
- 返回指定键所映射的值。
- 如果没有找到键，则返回
null。
-
remove(Object key)：
- 如果存在一个键的映射关系，则将其从映射中移除。
- 返回该键的值，如果没有找到键，则返回
null。
-
clear()：
- 移除映射中的所有键值对。等等