ch3-of-programmercarl

哈希 C++ C 代码随想录双指针 map set

刷题

发布日期: 2022-04-18

242. 有效的字母异位词
- 思路
- 代码
349. 两个数组的交集
- 思路
- 代码
202. 快乐数
- 思路
- 代码
1. 两数之和
- 思路
- 代码
454. 四数相加 II
- 思路
- 代码
383. 赎金信
- 思路
- 代码
15. 三数之和
- 思路
- 代码
18. 四数之和
- 思路
- 代码
总结

1 有效的字母异位词

题目链接：242. 有效的字母异位词

1.1 题目描述

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

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

示例1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例2:

输入: s = “rat”, t = “car”
输出: false

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

1.2 思路

两种做法：

一种是哈希表，将 s 的每个字符映射到哈希表中，然后遍历 t ,如果当前字符在哈希表中不存在，则说明 s 和 t 不是字母异位词；若存在，则将哈希表中该字符的数量减去 1 ，当该字符数量为零则将该关键字删去。遍历 t 后判断哈希表中元素个数，当为零说明二者为字母异位词，否则则返回false.
另一种是排序，直接对 s 和 t 按字符进行排序，然后对两个字符串进行比较，相等则是字母异位词，返回true，否则返回 false 。

完整代码如下：

Cpp 实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        map<char, int> m;
        for(char ch: s){
            if(m.count(ch)){
                m[ch]++;
            }else{
                m[ch] = 1;
            }
        }
        for(char ch: t){
            if(!m.count(ch)){
                return false;
            }else{
                m[ch]--;
                if(m[ch] == 0) m.erase(ch);
            }
        }
        return m.size() == 0;
    }
};

C 实现

int cmp(const void *a, const void *b){
    return(*(char*)a-*(char*)b);   //从小到大
}
bool isAnagram(char * s, char * t){
    if(strlen(s)!=strlen(t)) return false;
    qsort(s,strlen(s),sizeof(char),cmp);
    qsort(t,strlen(t),sizeof(char),cmp);
    for(int i=0;i<strlen(s);i++){
        if(s[i]!=t[i]) return false;
    }
    return true;
}

2 两个数组的交集

题目链接：349. 两个数组的交集

2.1 题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

2.2 思路

创建哈希表，遍历 nums1 并将每一个数插入 map 中，然后遍历nums2, 对当前遍历的数字在哈希表中查找，若哈希表中存在该数字则将该数字插入res中，并将该数字从哈希表中删去（题目中要求输出结果中每个元素一定是唯一的）。

完整代码如下：

Cpp 实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        map<int, int> m;
        for(int n: nums1){
            m[n]++;
        }
        for(int n: nums2){
            if(!m.count(n)){
                continue;
            }
            res.emplace_back(n);
            m.erase(n);
        }
        return res;
    }
};

C 实现

struct hashTable{
    int key;
    UT_hash_handle hh;
};

void createHashTable(struct hashTable **users,int user_id){
    struct hashTable *tmp;
    HASH_FIND_INT(*users,&user_id,tmp);
    if(tmp==NULL){
        tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
        tmp->key = user_id;
        HASH_ADD_INT(*users,key,tmp);
    }else{
        return;
    }
}

int* getIntersection(struct hashTable** users1, struct hashTable** users2, int* returnSize) {
    if (HASH_COUNT(*users1) > HASH_COUNT(*users2)) {
        return getIntersection(users2, users1, returnSize);
    }
    int* intersection = malloc(sizeof(int) * (HASH_COUNT(*users1) + HASH_COUNT(*users2)));
    struct hashTable *s, *tmp;
    HASH_ITER(hh, *users1, s, tmp) {
        struct hashTable *tmp2;
        HASH_FIND_INT(*users2,&s->key,tmp2);
        if(tmp2!=NULL){
            intersection[(*returnSize)++] = s->key;
        }
    }
    return intersection;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    *returnSize = 0;
    struct hashTable *set1 = NULL,*set2 = NULL;
    for(int i=0;i<nums1Size;i++){
        createHashTable(&set1,nums1[i]);
    }
    for(int i=0;i<nums2Size;i++){
        createHashTable(&set2,nums2[i]);
    }
    return getIntersection(&set1,&set2,returnSize);
    /*return findIntersection(fmin(nums1Size,nums2Size),&set1,&set2,returnSize);*/
    //*returnSize = n;
}

注： C 实现的代码中可以用数组来作为哈希表。

3 快乐数

题目链接：202. 快乐数

3.1 题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例1:

输入: n = 19
输出: true
解释:
$1^2 + 9^2 = 82$
$8^2 + 2^2 = 68$
$6^2 + 8^2 = 100$
$1^2 + 0^2 + 0^2 = 1$

示例2:

输入: n = 2
输出: false

3.2 思路

模拟。循环对 n 计算每个位置上的数字平方和，并判断当前计算结果在哈希表中是否已经存在，如果已经存在说明出现了循环，不可能计算得到 1 的结果，因而直接返回 false；否则把当前的计算结果插入哈希表中，并将该数值赋给 n.(Cpp 实现)
双指针。类似链表中判断是否成环，设置两个指针，快指针每次计算对当前数字进行每个位置的数字平方和两次，而慢指针每次只计算一次，如果快慢指针相等且快指针不为 1 则说明陷入循环，返回 false, 否则返回 true.(C 实现) 注意 : 快指针应该初始化为下一个计算结果，否则将不会进入循环。

完整代码如下：

Cpp 实现

class Solution {
public:
    int cal(int num){
        int tmp = 0, sum = 0;
        while(num){
            tmp = num%10;
            sum += pow(tmp,2);
            num /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        map<int, int> m;
        while(n != 1){
            int tmp = cal(n);
            if(m.count(tmp)){
                return false;
            }
            m[tmp]++;
            n = tmp;
        }
        return true;
    }
};

C 实现

int cal(int num){
    int tmp = 0, sum = 0;
    while(num){
        tmp = num%10;
        sum += tmp*tmp;
        num /= 10;
    }
    return sum;
}

bool isHappy(int n){
    int fast = cal(n) , slow = n;
    while(fast != 1 && fast != slow){
        fast = cal(cal(fast));
        slow = cal(slow);
    }
    return fast == 1;
}

4 两数之和

题目链接：1. 两数之和

4.1 题目描述

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

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

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

示例1:

输入: nums = [2,7,11,15], target = 9
输出: [0,1]

示例2:

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

示例3:

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

4.2 思路

创建一个哈希表，键为 nums[i] 、值为 i ，然后遍历数组，先在哈希表中查找是否已存在target - nums[i]，如果有则将两个对应的索引插入 res 中并进行返回即可。

完整代码如下：

Cpp 实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        map<int, int> m;
        for(int i = 0; i < nums.size(); ++i){
            if(m.count(target - nums[i])){
                res.emplace_back(i);
                res.emplace_back(m[target-nums[i]]);
                break;
            }else{
                 m[nums[i]] = i;
            }
        }
        if(!res.size()){
            res.emplace_back(-1);
            res.emplace_back(-1);
        }
        return res;
    }
};

C 实现

struct hashTable{
    int key;
    int val;
    UT_hash_handle hh;
};

void insert(struct hashTable **set,int key,int value){
    struct hashTable *tmp;
    HASH_FIND_INT(*set,&key,tmp);
    if(tmp==NULL){
        tmp = malloc(sizeof(struct hashTable));
        tmp->key = key;
        tmp->val = value;
        HASH_ADD_INT(*set,key,tmp);
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ret = malloc(sizeof(int)*2);
    *returnSize = 2;
    struct hashTable *set = NULL;
    for(int i=0;i<numsSize;i++){
        struct hashTable *tmp;
        int num=target - nums[i];
        HASH_FIND_INT(set,&num,tmp);
        if(tmp!=NULL){
            ret[0] = tmp->val;
            ret[1] = i;
            return ret;
        }else{
            insert(&set,nums[i],i);
        }
    }
    memset(ret,-1,sizeof(int)*2);
    return ret;
}

5 四数相加 II

题目链接：454. 四数相加 II

5.1 题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例1:

输入: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出: 2
解释:
两个元组如下：
1.(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2.(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例2:

输入: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出: 1

5.2 思路

将四个数组分为两组，先对nums1和nums2进行遍历，将二者的加和插入到哈希表中，然后再遍历nums3 和 nums4 进行遍历，用target减去二者加和并再哈希表中查找是否存在这个结果值，如果存在则将该结果值对应的哈希表中的值加到结果中。

完整代码如下：

Cpp 实现

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        map<int, int> m;
        for(int num1 : nums1){
            for(int num2 : nums2){
                m[num1+num2]++;
            }
        } 
        int ans = 0;
        for(int num3 : nums3){
            for(int num4 : nums4){
                int target = num3+num4;
                if(m.count(-target)){
                    ans += m[-target];
                }
            }
        }
        return ans;
    }
};

C 实现

typedef struct {
    long key;
    int cnt;
    UT_hash_handle hh;
}HashTable;

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){
    HashTable *users = NULL, *tmp;
    int n = nums1Size;
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            long sum = nums1[i] + nums2[j];
            HASH_FIND_INT(users, &sum, tmp);
            if(tmp){
                tmp->cnt += 1;
            }else{
                tmp = (HashTable *)malloc(sizeof(HashTable));
                tmp->key = sum;
                tmp->cnt = 1;
                HASH_ADD_INT(users, key, tmp);
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            long sum = -(nums3[i] + nums4[j]);
            HASH_FIND_INT(users, &sum, tmp);
            if(tmp){
                ans += tmp->cnt;
            }
        }
    }
    return ans;
}

6 赎金信

题目链接：383. 赎金信

6.1 题目描述

给你两个字符串：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

6.2 思路

先判断ransomNote 和 magazine 的长度，若前者大于后者，则返回 false; 然后遍历 magazine ,并将当前遍历的字符作为键插入哈希表中，并将对应的值加 1. 最后遍历 ransomNote，判断当前字符在哈希表中是否存在，若不存在则返回 false，否则则将当前字符对应的值减去 1 ，若减 1后为 0 则将该关键字删去。

完整代码如下：

Cpp实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int len1 = ransomNote.length(), len2 = magazine.length();
        if(len1 > len2) return false;
        map<char, int> m;
        for(char ch: magazine){
            m[ch]++;
        }
        for(char ch: ransomNote){
            if(!m.count(ch)){
                return false;
            }
            m[ch]--;
            if(!m[ch]) m.erase(ch);
        }
        return true;
    }
};

C 实现

bool canConstruct(char * ransomNote, char * magazine){
    if(strlen(magazine)<strlen(ransomNote)){
        return false;
    }
    int* tmpRansomNote = malloc(sizeof(int)*26);
    int* tmpMagazine = malloc(sizeof(int)*26);
    memset(tmpRansomNote,0,sizeof(int)*26);
    memset(tmpMagazine,0,sizeof(int)*26);
    for(int i=0;i<strlen(magazine);i++){
        if(i<strlen(ransomNote)) tmpRansomNote[ransomNote[i]-'a']++;
        tmpMagazine[magazine[i]-'a']++;
    }
    for(int j=0;j<26;j++){
        if(tmpMagazine[j]<tmpRansomNote[j]){
            return false;
        }
    }
    return true;
}

7 三数之和

题目链接：15. 三数之和

7.1 题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例1:

输入: nums = [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]

示例2:

输入: nums = []
输出: []

示例3:

输入: [0]
输出: []

7.2 思路

先将数组进行排序，然后分别用first、second和third分别指代第一、第二和第三个选取的数字的索引，用 first 遍历数组，然后 target 设为 -nums[first](题目要三数之和为 0 )，然后second 赋为 first + 1, 而third 赋为 nums.size()-1,进行循环判断nums[second] + nums[third] 是否等于 target，若是则将三个索引插入答案，并将second和third向中间移动(要移动到不等于上一个值的地方，因为题目规定 不能出现重复的三元组); 若nums[second] + nums[third] 小于 target，则应该试图把第二和第三的加和变大，所以将 second 右移一位；若nums[second] + nums[third] 大于 target，则应该试图把第二和第三的加和变小，所以将 third 左移一位。

这题不大适用哈希表，因为题目规定 不能出现重复的三元组，如果用哈希表的话，插入完成后需要对重复的三元组进行删除。

完整代码如下：

Cpp 实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n < 3) return res;
        sort(nums.begin(), nums.end());
        for(int first = 0; first < n -2; ++first){
            if(first && nums[first] == nums[first-1]){
                continue;
            }
            int target = - nums[first];
            int second = first + 1, third = n - 1;
            while(second < third){
                int tmp = nums[second] + nums[third];
                if(tmp == target){
                    res.push_back({nums[first], nums[second], nums[third]});
                    while(second < third && nums[second] == nums[++second]);
                    while(second < third && nums[third] == nums[--third]);
                }else if(tmp < target){
                    ++second;
                }else{
                    --third;
                }
            }
        }
        return res;
    }
};

C 实现

int cmp(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if(numsSize < 3) return NULL;
    int n = numsSize;
    int** ret = (int **)malloc(sizeof(int *)*n*n);
    *returnColumnSizes = (int *)malloc(sizeof(int)*n*n);
    qsort(nums, n, sizeof(int), cmp);
    for(int i = 0; i < n-2; i++){
        if(nums[i] > 0) return ret;
        if(i>0 && nums[i]==nums[i-1]){
            continue;
        }
        int left= i + 1, right = n-1;
        while(left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == 0){
                ret[*returnSize] = (int *)malloc(sizeof(int)*3);
                (*returnColumnSizes)[*returnSize] = 3; 
                ret[*returnSize][0] = nums[i];
                ret[*returnSize][1] = nums[left];
                ret[*returnSize][2] = nums[right];
                (*returnSize)++;
                while(left < right && nums[left ] == nums[++left]); //这两行划重点！！！！！！！
                while(left < right && nums[right] == nums[--right]);
            }else if(sum > 0){
                right--;
            }else{
                left++;
            }
        }
    }
    return ret;
}

8 四数之和

题目链接：18. 四数之和

8.1 题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

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

示例1:

输入: nums = [1,0,-1,0,-2,2], target = 0
输出: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例2:

输入: nums = [2,2,2,2,2], target = 8
输出: [[2,2,2,2]]

8.2 思路

思路和”三数之和”思路一致，只是多加了一层 for 循环即可，时间复杂度为 $O(n^3logn)$

完整代码如下：

Cpp 实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int first = 0; first < n - 3; ++first){
            if(first && nums[first] == nums[first-1]){
                continue;
            }
            for(int second = first+1; second < n-2; ++second){
                if(second > first+1 && nums[second] == nums[second-1]){
                    continue;
                }
                int rest = target - nums[first] - nums[second];
                int third = second + 1, fourth = n - 1;
                while(third < fourth){
                    int tmp = nums[third] + nums[fourth];
                    if(tmp == rest){
                        res.push_back({nums[first],nums[second],nums[third],nums[fourth]});
                        while(third < fourth && nums[third] == nums[++third]);
                        while(third < fourth && nums[fourth] == nums[--fourth]);
                    }else if(tmp < rest){
                        ++third;
                    }else{
                        --fourth;
                    }
                }
            }
        }
        return res;
    }
};

C 实现

int cmp(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}



int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    int n = numsSize;  
    *returnSize = 0;
    if(n < 4) return NULL;

    qsort(nums, n, sizeof(int), cmp);
    int** ret = (int **)malloc(sizeof(int *) * n* n* n);
    *returnColumnSizes = (int *)malloc(sizeof(int) *n *n *n);
    for(int first = 0; first < n-3; first++){
        if(first > 0 && nums[first] == nums[first-1]){
            continue;
        }
        for(int second = first + 1; second < n-2; second++){
            if(second > first + 1 && nums[second] == nums[second-1]){
                continue;
            }
            int sum = target - nums[first] - nums[second];
            int third = second + 1, fourth = n-1;
            while(third < fourth){
                if(nums[third] + nums[fourth] == sum){
                    ret[*returnSize] = (int *)malloc(sizeof(int)*4);
                    (*returnColumnSizes)[*returnSize] = 4;
                    ret[*returnSize][0] = nums[first];
                    ret[*returnSize][1] = nums[second];
                    ret[*returnSize][2] = nums[third];
                    ret[*returnSize][3] = nums[fourth];
                    (*returnSize)++;
                    while(fourth > third && nums[fourth] == nums[--fourth]);
                    while(fourth > third && nums[third] == nums[++third]);
                }else if(nums[third] + nums[fourth] < sum){
                    third++;
                }else{
                    fourth--;
                }
            }
        }
     }
    return ret;
}

总结

本章主要考察哈希表和双指针法。

C++ 中的 set 仅有键无值，可以实现O(1)的关键字查找与插入，且插入时如果关键字已存在则不再插入。set 是一种关联性容器，其内部的数据都是有序的。
multiset: 整体的接口和 set 都相同，但是 multiset 可以插入 key 相同的值. 如果用 find 查找 key 值时，找到的是中序遍历第一个(中序遍历其实就是遍历数组的最左端那个)，因此不断遍历下去可以找到这个 multiset 里所有的 key 值。 multiset 和 set 一样不能够对数据进行修改。
map: 有别于 set 的是，map是一种key(键),value(值)的形式，用来保存键和值组成的集合，键必须是唯一的，但值可以不唯一。里面的元素可以根据键进行自动排序，由于map是key_value的形式，所以map里的所有元素都是pair类型。pair里面的first被称为key(键），second被称为value(值）。map可以通过关键字查找映射关联信息value，同时根据key值进行排序。
multimap: multimap允许key值的冗余，因此key值相同也可以进行插入。

set和map的底层都是通过红黑树来实现的，二者都不允许对键进行修改，但后者可以对值进行修改。
unordered_set: 与set类似，但底层是通过哈希实现的，且内部元素为无序状态， unordered_map 也类似，不再赘述。