LeetCode 349: 两个数组的交集 - C语言

问题描述

给定两个数组 ransomNote 和 magazine，你需要判断 ransomNote 是否可以由 magazine 里的字符构成。每个字符可以使用一次。

解题思路

通过统计 magazine 中每个字符的频次，并与 ransomNote 中字符的需求频次进行比对，最终判断 magazine 中的字符是否足够构建 ransomNote。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool canConstruct(char* ransomNote, char* magazine) {
    // 定义一个长度为26的数组，用来记录字符出现的频次
    int hasmap[26] = {0}; 

    // 遍历 ransomNote 字符串，减少对应字母的频次
    for (int i = 0; i < strlen(ransomNote); i++) {
        hasmap[ransomNote[i] - 'a'] -= 1;  // 对应字母的频次减1
    }

    // 遍历 magazine 字符串，增加对应字母的频次
    for (int i = 0; i < strlen(magazine); i++) {
        hasmap[magazine[i] - 'a'] += 1;  // 对应字母的频次加1
    }

    // 最后检查 hasmap 中每个位置的值，确保没有负值
    for (int i = 0; i < 26; i++) {
        if (hasmap[i] < 0) return false;  // 如果某个字母的频次小于0，返回false
    }
    
    return true;  // 所有检查通过，返回true
}

int main() {
    char ransomNote[] = "aabb";
    char magazine[] = "abbbcca";
    
    if (canConstruct(ransomNote, magazine)) {
        printf("可以构成\n");
    } else {
        printf("无法构成\n");
    }

    return 0;
}

逐行解释

1. 初始化字符频次数组

int hasmap[26] = {0};

这行代码定义了一个大小为 26 的整型数组 hasmap，用于记录每个字母出现的频次。hasmap[i] 表示字母 a + i 的频次。初始化时，所有字母的频次为 0。

2. 遍历 ransomNote 字符串，减少字符频次

for (int i = 0; i < strlen(ransomNote); i++) {
    hasmap[ransomNote[i] - 'a'] -= 1;
}

在这个循环中，我们遍历 ransomNote 中的每个字符，将相应字符的频次减少 1。通过 ransomNote[i] - 'a' 可以将字符转换为其对应的索引位置。例如，字符 'a' 对应 0，字符 'b' 对应 1，依此类推。

3. 遍历 magazine 字符串，增加字符频次

for (int i = 0; i < strlen(magazine); i++) {
    hasmap[magazine[i] - 'a'] += 1;
}

在这一步，我们遍历 magazine 中的每个字符，将相应字符的频次增加 1。这样，hasmap 数组会记录 magazine 中每个字母的出现次数。

4. 检查是否所有字符的频次都满足需求

for (int i = 0; i < 26; i++) {
    if (hasmap[i] < 0) return false;
}

此处，我们遍历 hasmap 数组，检查是否有任何字符的频次小于 0。如果存在这样的情况，说明 magazine 中的某个字母的数量不足以构建 ransomNote，因此返回 false。

5. 返回结果

return true;

如果所有字符的频次都满足需求，最终返回 true，表示 magazine 可以用来构建 ransomNote。

时间复杂度分析

• 遍历 ransomNote 和 magazine 的时间复杂度为 $O(n+m)$，其中 $n$ 和 $m$ 分别是 ransomNote 和 magazine 的长度。
• 遍历 hasmap 数组的时间复杂度为 $O(26)=O(1)$，因为数组的大小是固定的。

因此，总的时间复杂度是 $O(n+m)$，其中 $n$ 和 $m$ 是输入字符串的长度。

空间复杂度分析

• 使用了一个大小为 26 的数组来记录字符频次，空间复杂度为 $O(1)$，即常数空间。

测试用例

int main() {
    char ransomNote[] = "aabb";
    char magazine[] = "abbbcca";
    
    if (canConstruct(ransomNote, magazine)) {
        printf("可以构成\n");
    } else {
        printf("无法构成\n");
    }

    return 0;
}

在这个测试用例中，ransomNote 为 "aabb"，magazine 为 "abbbcca"。通过运行上述程序，我们会发现输出为 "可以构成"，说明 magazine 中的字符可以成功构建 ransomNote。