网站建设高级 上海查询网域名查询
一、题目描述
给你两个字符串：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 <= 10^5ransomNote和magazine由小写英文字母组成
二、解题思路
- 首先，我们需要统计
magazine中每个字符出现的次数。 - 然后，遍历
ransomNote中的每个字符，并检查magazine中是否有足够的该字符来构成ransomNote。 - 如果在
ransomNote中发现一个字符，而magazine中没有足够的该字符，那么返回false。 - 如果
ransomNote中的所有字符都能在magazine中找到足够的数量，返回true。
三、具体代码
class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 使用一个数组来统计magazine中每个字符的出现次数int[] count = new int[26]; // 因为只有小写字母，所以大小为26// 遍历magazine，统计每个字符的出现次数for (char c : magazine.toCharArray()) {count[c - 'a']++;}// 遍历ransomNote，检查是否有足够的字符for (char c : ransomNote.toCharArray()) {// 如果magazine中没有足够的字符c，返回falseif (--count[c - 'a'] < 0) {return false;}}// 如果所有字符都检查通过，返回truereturn true;}
}
在这段代码中，我们使用了一个长度为26的数组 count 来存储每个字符出现的次数，因为英文字母一共有26个。数组中的索引 i 对应字符 'a' + i。通过这种方式，我们可以快速定位并更新字符的出现次数。当遍历 ransomNote 时，我们只需要检查对应的计数是否大于0，如果是，则表示可以构成，否则返回 false。
四、时间复杂度和空间复杂度
1. 时间复杂度
- 遍历
magazine字符串统计字符出现次数：这个操作的时间复杂度是 O(n)，其中 n 是magazine字符串的长度。 - 遍历
ransomNote字符串检查字符是否足够：这个操作的时间复杂度是 O(m)，其中 m 是ransomNote字符串的长度。
因为这两个操作是顺序执行的，所以总的时间复杂度是两个操作的和，即 O(n + m)。
2. 空间复杂度
- 使用了一个固定大小的数组
count来存储每个字符的出现次数，该数组的大小为26，不随输入字符串的长度变化。因此，这个操作的空间复杂度是 O(1)。
综上所述，该算法的时间复杂度是 O(n + m)，空间复杂度是 O(1)。其中 n 是 magazine 的长度，m 是 ransomNote 的长度。
五、总结知识点
-
数组的声明与初始化：使用
int[] count = new int[26];声明并初始化了一个长度为26的整型数组，用于存储每个小写字母出现的次数。 -
字符与整型的转换：通过表达式
c - 'a'将字符转换为对应的整型索引。这是因为字符在Java中是以整数形式存储的，且小写字母 ‘a’ 到 ‘z’ 在ASCII表中的值是连续的。 -
增强型for循环：使用增强型for循环
for (char c : magazine.toCharArray())来遍历字符串中的每个字符。 -
数组的索引访问：使用数组索引
count[c - 'a']来访问和更新数组中对应字符的计数。 -
前缀自增和自减操作：使用
++和--操作符来增加和减少数组中字符的计数。 -
条件判断：使用
if语句来检查数组中字符的计数是否小于0，以确定是否可以由magazine中的字符构成ransomNote。 -
返回值：使用
return语句来返回布尔值true或false，表示ransomNote是否可以由magazine中的字符构成。 -
字符串到字符数组的转换：使用
toCharArray()方法将字符串转换为字符数组，以便能够遍历字符串中的每个字符。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。