代码随想录算法训练营第六天 | 242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和
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;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!