当前位置：首页 > article >正文

力扣: 赎金信

article 2025/1/19 19:43:57

文章目录

需求
分析及编码
结尾

在这里插入图片描述

需求

给你两个字符串：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 <= 105
ransomNote 和 magazine 由小写英文字母组成

分析及编码

感觉这个题目和题意没有一点的关联啊…

判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。ransomNote 和 magazine 由小写英文字母组成

提示里说都是小写字母组成的, 第一反应是用数组:

public boolean canConstruct(String ransomNote, String magazine) {
    int[] ransomNoteCount = new int[26];
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        int index = ransomNote.charAt(i) -'a';
        ransomNoteCount[index]++;
    }
    for (int i = 0; i < magazine.length(); i++) {
        int index = magazine.charAt(i) -'a';
        ransomNoteCount[index]--;
    }
    for (int i = 0; i < ransomNoteCount.length; i++) {
        if (ransomNoteCount[i] > 0) {
            return false;
        }
    }
    return true;
}

代码解释:
初始化字符计数数组:

int[] ransomNoteCount = new int[26];

创建一个长度为26的整数数组 ransomNoteCount，用于记录 ransomNote 中每个字母的出现次数。这里假设输入的字符都是小写字母（a-z），因此数组的长度是26。
统计 ransomNote 中的字符出现次数:

for (int i = 0; i < ransomNote.length(); i++) {
    char c = ransomNote.charAt(i);
    int index = ransomNote.charAt(i) - 'a';
    ransomNoteCount[index]++;
}

通过循环遍历 ransomNote 的每个字符，计算每个字符出现的次数：
char c = ransomNote.charAt(i); 获取当前字符。
int index = ransomNote.charAt(i) - 'a'; 计算当前字符在 ransomNoteCount 数组中的索引。这个计算基于 ASCII 值，例如字符 a 的 ASCII 值是97，b 是98，依此类推。
ransomNoteCount[index]++; 增加对应索引的计数。
减少 magazine 中的字符出现次数:

for (int i = 0; i < magazine.length(); i++) {
    int index = magazine.charAt(i) - 'a';
    ransomNoteCount[index]--;
}

接着，遍历 magazine 的每个字符：
计算当前字符的索引并减少 ransomNoteCount 中对应索引的计数。这表示 magazine 中的字符可以“消费”掉相应数量的 ransomNote 中的字符。
检查 ransomNoteCount 中的计数:

for (int i = 0; i < ransomNoteCount.length; i++) {
    if (ransomNoteCount[i] > 0) {
        return false;
    }
}

最后，遍历 ransomNoteCount 数组，检查是否还有剩余的字符：
如果发现任何索引的值大于0，意味着 ransomNote 中的某个字符数量超过了 magazine 中的字符数量，返回 false。
如果所有索引的值都小于或等于0，说明 magazine 中的字符足够用来构造 ransomNote，返回 true。
返回结果:
return true;
如果通过了上述检查，返回 true，表示可以构造 ransomNote。

执行结果:

在这里插入图片描述