JLUVicent

242有效的字母异位词&349两个数组的交集&202快乐数&1两数之和

 
  • 2023年 02月20日
  • 0 阅读

day6

242.有效的字母异位词

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

解题思路：利用哈希表的方法，本题将数组作为哈希表，里面有几个细节注意：首先就是数组的赋值，初始要将值赋为0，然后分别遍历两个字符串，将其在数组中的位置对应值进行相应的加或者减操作，最终判断数组中的元素是否都为0，如果为0返回true,否则返回false。

image-20230220203556443

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash1[26] = {0};
        // for( int i = 0; i < 26; i++){
        //     cout<<hash1[i]<<endl;
        // }
        for( int i = 0;i < s.size();i++){
            // 并不用记住字符a的值，有相对数值即可
            hash1[ s[i]-'a' ]++;
        }
        for ( int i = 0;i < t.size();i++){
            hash1[ t[i]-'a']--;
        }
        // cout<<*hash<<endl;
        for ( int i = 0; i < 26; i++){
            // cout<<i<<endl;
            // cout<<hash1[i]<<endl;
            if ( hash1[i] != 0 ){
                return false;
            }
        }
        return true;

    }
};

349.两个数组的交集

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

题目思路：

1.利用数组作为哈希表，由于力扣上限制了数值的范围，因此利用数组作为哈希表，先遍历第一个数组将其对应位置的值进行更新，然后遍历第二个数组看是否在哈希表中出现过。注意对于集合的定义

unordered_set<int> result;
result.insert(nums2[i]);
// 最后将集合转换为数组
vector<int>(result.begin(),result.end());

2.利用set作为哈希表，先将第一个nums存入set哈希表中，注意存入方式。

unordered_set<int> nums_set(nums1.begin(),nums1.end());
// 判断是否出现过条件
nums_set.find(num) != nums_set.end()

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // //1. 数组哈希表写法
        // int hash_map[1001]={0};
        // unordered_set<int> result;
        // for ( int i = 0;i < nums1.size();i++){
        //     hash_map[ nums1[i] ]++;
        // }
        // for ( int i = 0;i < nums2.size();i++){
        //     if( hash_map[ nums2[i] ] != 0 ){
        //         result.insert(nums2[i]);
        //     }
        // }
        // return vector<int>(result.begin(),result.end());

        // 2.set哈希表的解法
        unordered_set<int> result_set;  //存放结果，用set来去重
        unordered_set<int> nums_set(nums1.begin(),nums1.end());
        for(int num:nums2){
            //查看nums2的元素是否在nums_set里面出现过
            if( nums_set.find(num) != nums_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(),result_set.end());
    }
};

202.快乐数

题目链接：202.快乐数

题目思路：本质是一个哈希表的题目，首先应该知道如何计算n的各个位上的平方和，其次判断sum是否为1，如果为1，返回true，如果有重复元素，则返回false。

class Solution {
public:
    // 取各个位上的单数的平方和
    int getSum( int n){
        int sum = 0;
        while (n) {
            sum +=(n % 10) * ( n % 10);//先取个位，再取十位依次进行
            n /=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum = getSum(n);
            if (sum == 1){
                return true;
            }
            // 如果重复出现过，直接return false 说明陷入了循环
            if(set.find(sum)!=set.end()){ //注意判断条件
                return false;
            }
            else{
                set.insert(sum);
            }
            n=sum;
        }

    }
};

1.两数之和

题目链接：1.两数之和

题目思路：通过哈希表将列表中的数值存进去，每遍历一个数，判断target-该数是否在之前的哈希表中出现过，如果出现过，则直接返回位置，没有出现过就将该数插入哈希表中，如果都不满足返回空

// 注意哈希表中的map在C++的写法
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int> map;
        for(int i = 0;i < nums.size();i++){
            //判断目标值-nums[i]是否在map中
            int t = target - nums[i];
            auto iter = map.find(t);
            if( map.find(t) != map.end()){
                return { iter->second,i};
            }
            //如果没有匹配到，将元素加入到map中
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};  
    }
};
搜索