代码随想录算法训练营第六天 | 242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

2023-12-18 11:30:58

242. 有效的字母异位词

题目链接:242. 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

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

文章讲解/视频讲解:https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

思路

用哈希表来解决,因为题目中已经提到s和t仅包含小写字母,所以哈希表可以用一个长为26的数组代替。

首先预判断,如果s和t长度不一,返回false。

设置两个哈希表,分别记录s和t中每个字母的出现次数,如果出现次数完全相同,则说明是字母异位词。

C++实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()) return false;
        vector<int> hashSet1(26, 0), hashSet2(26, 0);
        
        for(int i = 0;i<s.size();i++){
            hashSet1[s[i] - 'a'] += 1;
            hashSet2[t[i] - 'a'] += 1;
        }

        for(int i = 0;i<26;i++){
            if(hashSet1[i] != hashSet2[i]) return false;
        }
        return true;
    }
};

349. 两个数组的交集

题目链接:19.删除链表的倒数第N个节点

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

文章讲解/视频讲解:https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

思路

用哈希表来解决,首先定义一个哈希表hashSet1,用来统计nums1中的所有元素,然后遍历nums2,如果nums2中的元素已经存在于hashSet1,则说明这个元素是两个数组的交集。这时将这个元素存入另一个哈希表hashSet2,用以去重,最后把hashSet2中的元素全都送入一个vector数组中,作为结果。

C++实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hashSet1;
        for(int i = 0;i<nums1.size();i++){
            hashSet1.insert(nums1[i]);
        }

        unordered_set<int> hashSet2;
        
        for(int i = 0;i<nums2.size();i++){
            if(hashSet1.find(nums2[i]) != hashSet1.end()){
                hashSet2.insert(nums2[i]);
            }
        }
        vector<int> results;

        for(auto x : hashSet2){
            results.push_back(x);
        }
        return results;
    }
};

202. 快乐数

题目链接:202. 快乐数

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

「快乐数」 定义为:

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

文章讲解/视频讲解:https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

思路

同样采用哈希表的思路,定义一个函数func来计算每一个正整数所有位置的平方和。每一次循环,将当前数字curr_num送入func,计算得出一个新的值来代替curr_num,同时,将该结果存储进哈希表中,然后循环这一过程。如果当前计算得出的值为1或者已经在哈希表中,则终止。如果最终curr_num等于1,则说明是快乐数,否则不是。

C++实现

class Solution {
public:

    int calculate_square(int n){
        int result = 0;
        while(n != 0){
            int curr = n % 10;
            result += curr * curr;
            n /= 10;
        }
        return result;
    }

    bool isHappy(int n) {
        unordered_set<int> hashSet;
        int curr_num = n;
        hashSet.insert(curr_num);
        while(curr_num != 1){
            curr_num = calculate_square(curr_num);
            if(hashSet.find(curr_num) != hashSet.end()) break;
            hashSet.insert(curr_num);
        }

        return curr_num == 1;
    }
};

1. 两数之和

题目链接:1. 两数之和

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

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

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

文章讲解/视频讲解:https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

这道题是leetcode的第一道题,有很多种实现方式。我能想到的有三种,第一种方法是暴力搜索,两层循环进行遍历,这种方法的时间复杂度为o(n^2);第二种方法是采用哈希表,首先将当前数组全部存入哈希表中,然后再对该数组进行遍历,对于数组中的每一个元素num,判断哈希表中是否有target-num这个元素,如果有,则说明我们找到了这一对元素;第三种方法是采用双指针,首先对数组进行排序,然后定义两个指针left和right,分别指向数组的头和尾,如果nums[left] + nums[right] < target,就令left++,如果nums[left] + nums[right] > target,就令right–,直到找到这一对值,不过需要注意的是,题目要求返回原数组的下标,这一点在排序时需要记录。

C++实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashMap;

        for(int i = 0;i<nums.size();i++){
            hashMap[nums[i]] = i;
        }

        vector<int> result;
        for(int i = 0;i<nums.size();i++){
            if(hashMap.find(target - nums[i]) != hashMap.end() && hashMap[target - nums[i]] != i){
                result.push_back(i);
                result.push_back(hashMap[target - nums[i]]);
                break;
            }
        }

        return result;
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135057922
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。