力扣面试经典题之哈希表

383. 赎金信

简单

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

bool canConstruct(char* ransomNote, char* magazine) {
    int rr=strlen(ransomNote);
    int mm=strlen(magazine);
    int count=0;
    for(int i=0;i<rr;i++){
        for(int j=0;j<mm;j++){
            if(ransomNote[i]==magazine[j]){
               count++;
               magazine[j]=' ';
               break;
            }
        }
    }
    if(count==rr){
        return true;
    }
     return false;
}

205. 同构字符串

简单

给定两个字符串?s?和?t?，判断它们是否是同构的。

如果?s?中的字符可以按某种映射关系替换得到?t?，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s?和?t?由任意有效的 ASCII 字符组成

bool isIsomorphic(char* s, char* t) {
    int a[200],f[200]={0};
    for(int i=0;i<200;i++){
        a[i]=-1;
    }
    int ss=strlen(s);
    int tt=strlen(t);
    if(ss!=tt){
        return false;
    }
    for(int i=0;i<ss;i++){
        int p=s[i]-' ';
        if(a[p]==-1&&f[t[i]-' ']==0){
            a[p]=t[i]-' ';
            f[(t[i]-' ')]=1;
         }else if(a[p]==-1&&f[t[i]-' ']!=0){
                  return false;
         }else{
            if(a[p]!=t[i]-' '){
                   return false;
            }
       }

    }

    return true;
}

290. 单词规律

简单

给定一种规律?pattern?和一个字符串?s?，判断?s?是否遵循相同的规律。

这里的?遵循?指完全匹配，例如，?pattern?里的每个字母和字符串?s?中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

• 1 <= pattern.length <= 300
• pattern?只包含小写英文字母
• 1 <= s.length <= 3000
• s?只包含小写英文字母和?' '
• s?不包含?任何前导或尾随对空格
• s?中每个单词都被?单个空格?分隔

bool wordPattern(char* pattern, char* s) {
    char *hashset[26];
    for(int i=0;i<26;i++){
        hashset[i]=NULL;
    }
    int pp=strlen(pattern);
    const char ff[2]=" ";
    char *token=NULL;
    for(int i=0;i<pp;i++){
      
        if(token == NULL){
            token = strtok(s, ff);
        }
        else{
             token = strtok(NULL, ff);
             if(token == NULL) {
                 return false;
             }
        }
        if(hashset[pattern[i]-'a']==NULL){
            
                 hashset[pattern[i]-'a']=token;
       }else{
           if(strcmp(hashset[pattern[i]-'a'],token)!=0){
                   return false;
            }
        }
    }
    token = strtok(NULL, ff);
    if(token != NULL)
    {
        return false;
    }
    for(int i =0; i < 26; i++)
    {
        if(hashset[i]!= NULL)
        {
            for(int j = i+ 1; j < 26; j++)
            {
                if(hashset[j]!= NULL)
                {
                    if(strcmp(hashset[i], hashset[j]) == 0)
                    {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

242. 有效的字母异位词

简单

给定两个字符串?s?和?t?，编写一个函数来判断?t?是否是?s?的字母异位词。

注意：若?s?和?t?中每个字符出现的次数都相同，则称?s?和?t?互为字母异位词。

示例?1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s?和?t?仅包含小写字母

bool isAnagram(char* s, char* t) {
    int snum[26]={0};
    int tnum[26]={0};
    int ss=strlen(s);
    int tt=strlen(t);
    for(int i=0;i<ss;i++){
        snum[s[i]-'a']++;
    }
    for(int i=0;i<tt;i++){
        tnum[t[i]-'a']++;
    }
    for(int i=0;i<26;i++){
        if(snum[i]!=tnum[i]){
            return false;
        }
    }
    return true;
}

1. 两数之和

简单

给定一个整数数组?nums?和一个整数目标值?target，请你在该数组中找出?和为目标值?target? 的那?两个?整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int *a=(int*)malloc(sizeof(int)*2);
    for(int i=0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
            if(nums[i]+nums[j]==target){
               a[0]=i;
               a[1]=j;
               (*returnSize)=2;
                break;
            }
        }
    }
     return a;
}