力扣面试经典——383题

💡 参考代码：

/**
 * 判断 ransomNote 能否由 magazine 中的字符构成
 * 
 * @param ransomNote 需要构建的字符串
 * @param magazine 提供字符的字符串
 * @return 如果可以构成返回 true，否则返回 false
 */
bool canConstruct(char * ransomNote, char * magazine) {
    // 使用数组统计字符频次（只包含小写字母，所以26个足够）
    int charCount[26] = {0};
    
    // 统计 magazine 中每个字符的出现次数
    for (int i = 0; magazine[i] != '\0'; i++) {
        charCount[magazine[i] - 'a']++;
    }
    
    // 检查 ransomNote 中的每个字符是否能在 magazine 中找到
    for (int i = 0; ransomNote[i] != '\0'; i++) {
        // 如果当前字符在 magazine 中的数量已经为0，说明不够用
        if (charCount[ransomNote[i] - 'a'] <= 0) {
            return false;
        }
        // 使用一个字符，对应数量减1
        charCount[ransomNote[i] - 'a']--;
    }
    
    return true;
}

📖 总结：

点击展开题目总结

🤔 赎金信

---

1️⃣ 题目核心信息

🎯 功能描述：判断是否可以用 magazine 字符串中的字符来构造 ransomNote 字符串，每个字符只能使用一次

📥 输入输出：

• 输入：ransomNote - 需要构造的字符串；magazine - 提供字符来源的字符串
• 输出：布尔值，如果可以构造返回 true，否则返回 false

---

2️⃣ 实现原理

💡 核心思路：使用字符频次统计方法，统计 magazine 中各字符数量，然后检查是否足够构造 ransomNote

📋 实现步骤：

1. 创建长度为26的数组统计 magazine 中每个字母的出现次数
2. 遍历 magazine 字符串，累计每个字符的频次
3. 遍历 ransomNote 字符串，检查每个字符在 magazine 中是否还有足够的数量
4. 如果字符数量不足返回 false，否则将对应字符数量减1，继续检查下一个字符

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用数组索引映射：通过 字符 - 'a' 将字符映射到 0-25 的数组索引
• 频次统计：先统计资源（magazine）再检查需求（ransomNote）
• 边检查边消耗：每使用一个字符就将对应计数减1

4️⃣ 使用场景

✅ 适用情况：

• 字符频率匹配问题
• 资源分配检查场景
• 字符串包含关系判断

⚠️ 前提条件：

• 输入字符串只包含小写英文字母
• 每个字符只能使用一次

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(m + n)，其中 m 是 magazine 的长度，n 是 ransomNote 的长度，需要遍历两个字符串各一次

• 💾 空间复杂度：O(1)，只使用了固定大小为26的数组来存储字符频次

6️⃣ 注意事项

🚩 边界情况：

• ransomNote 为空字符串时，应该返回 true
• magazine 为空字符串但 ransomNote 非空时，应该返回 false
• ransomNote 长度大于 magazine 时，可以直接返回 false

💥 易错点：

• 忘记在使用字符后将计数减1
• 字符到数组索引的转换错误
• 没有正确处理字符串结束符 '\0'

7️⃣ 补充说明

以 ransomNote = "aa" 和 magazine = "aab" 为例：

第一步：初始化字符计数数组

int charCount[26] = {0};  // 所有元素初始化为0

第二步：统计 magazine 中字符频次

遍历 magazine = "aab":

处理 'a'：charCount['a' - 'a']++ → charCount[0] = 1

处理 'a'：charCount['a' - 'a']++ → charCount[0] = 2

处理 'b'：charCount['b' - 'a']++ → charCount[1] = 1

此时 charCount 数组状态：

索引:  0  1  2  3  4  5  6  7  8  9  10 ... 25
值:    2  1  0  0  0  0  0  0  0  0  0  ...  0
       a  b  c  d  e  f  g  h  i  j  k  ...  z

第三步：检查 ransomNote 中字符需求

遍历 ransomNote = "aa":

处理第一个 'a'：

检查 charCount['a' - 'a'] 即 charCount[0] = 2 > 0，满足条件

将 charCount[0]-- → charCount[0] = 1 处理第二个 'a'：

检查 charCount['a' - 'a'] 即 charCount[0] = 1 > 0，满足条件

将 charCount[0]-- → charCount[0] = 0

第四步：返回结果

所有字符都满足需求，函数返回 true。

这个过程形象地展示了如何通过字符计数来判断一个字符串是否能由另一个字符串构造出来。

加载评论中...