leetcode 383赎金信 C语言

题目要求判断一个字符串（赎金信）中的字符是否可以由另一个字符串（杂志）中的字符组成，即赎金信中的每个字符都必须在杂志中至少出现相同次数。

解题思路：

1. 计数法：

   • 首先统计杂志中每个字符的出现次数，可以使用数组来记录每个字符的频率。
   • 然后遍历赎金信中的每个字符，对应减少杂志中该字符的计数，如果杂志中对应字符的计数小于赎金信中的需要，则说明无法满足条件。

2. 具体步骤：

   • 使用一个大小为26的数组 count 来统计杂志中每个字符的频率，其中下标表示字符（例如 'a' 对应索引0，'b' 对应索引1，以此类推）。
   • 第一次遍历杂志字符串，增加对应字符的计数。
   • 第二次遍历赎金信字符串，减少对应字符的计数，并判断计数是否小于零（即赎金信需要的字符在杂志中没有足够的数量）。

3. 代码实现：

c
复制代码
#include <stdio.h>
#include <stdbool.h>

bool canConstruct(char * ransomNote, char * magazine){
    int count[26] = {0}; // 数组用于统计杂志中每个字符的出现次数
    
    // 统计杂志中每个字符的频率
    for (int i = 0; magazine[i] != '\0'; ++i) {
        count[magazine[i] - 'a']++;
    }
    
    // 检查赎金信中的字符是否可以由杂志中的字符组成
    for (int i = 0; ransomNote[i] != '\0'; ++i) {
        count[ransomNote[i] - 'a']--;
        if (count[ransomNote[i] - 'a'] < 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char ransomNote[] = "aa";
    char magazine[] = "aab";
    
    if (canConstruct(ransomNote, magazine)) {
        printf("Yes, you can construct the ransom note.\n");
    } else {
        printf("No, you cannot construct the ransom note.\n");
    }
    
    return 0;
}

解析：

• count 数组用于记录每个字符出现的次数，初始化为0。
• 第一个循环遍历杂志字符串 magazine，增加对应字符的计数。
• 第二个循环遍历赎金信字符串 ransomNote，减少对应字符的计数，如果计数小于零则返回 false。
• 如果所有字符都能满足条件，则返回 true。

这种解法的时间复杂度为 O(m + n)，其中 m 是杂志字符串的长度，n 是赎金信字符串的长度。空间复杂度为 O(1)，因为数组 count 的大小是固定的（26个字母）。

这样的算法能够有效地判断赎金信是否可以由杂志中的字符构成，并且性能较为优秀。