1.有效异位词
242. 有效的字母异位词
直接使用库函数的multiset来判断
其实没什么好说的，因为字符串有重复的可以出现所以用的multiset
缺点：确实浪费空间，红黑树的插入删除，浪费时间
class Solution {
public:
bool isAnagram(string s, string t) {
multiset<char> ms;
multiset<char> mt;
for (auto e : s)
ms.insert(e);
for (auto e : t)
mt.insert(e);
if (ms.size() != mt.size())
return false;
auto begin1 = ms.begin();
auto begin2 = mt.begin();
while (begin1 != ms.end())
{
if (*begin1 != *begin2)
return false;
begin1++;
begin2++;
}
return true;
}
};2.数组实现
26个小写字母，而且是连续的，那么我们直接用数组来存储也可以的
1.那么映射的方式也很简单了，a就对应下标0，z对应下标25
2.第一个string里的字符对应下标元素有则加一；第二个是减一
3.到这里说明两个string都应该映射过了，那么我们检查hash是不是已经全为空，如果不是失败；反之成功
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26]={0};
for(auto e:s)
hash[e-'a']++;
for(auto e:t)
hash[e-'a']--;
for(int i=0;i<26;i++)
{
if(hash[i]!=0)
return false;
}
return true;
}
};2.数组交集
349. 两个数组的交集
用unordered_set去重，用unordered_map计数
1.unordered_set插入所有元素，不重复出现
2.unordered_map把两个unordered_set中的东西判断一下，遍历如果是1的就是交集
缺点：简单问题复杂化了
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ret;
unordered_set<int> s1;
unordered_set<int> s2;
unordered_map<int,int> m;
for(auto& e:nums1)
s1.insert(e);
for(auto& e:nums2)
s2.insert(e);
for(auto& e:s1)
m[e]++;
for(auto& e:s2)
m[e]++;
for(auto& e:m)
{
if(e.second==2)
ret.push_back(e.first);
}
return ret;
}
};优化过的
1.ret_set用来存储两个的交集
2.num_set存储nums1的所有元素
3.遍历一遍nums2，在num_set中能找到的说明是交集要插入ret_set，ret_set能去重
4.返回ret_set里的元素就行了
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> ret_set;
unordered_set<int> num_set(nums1.begin(),nums1.end());
for(auto e:nums2)
{
if(num_set.find(e)!=num_set.end())
ret_set.insert(e);
}
vector<int> ret(ret_set.begin(),ret_set.end());
return ret;
}
};数组实现
由于其数据个数范围在1~1000，因此我们通过数组实现也可以
unordered_set的缺点是哈希冲突会调用内部函数调整，这也减少了效率
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> ret_set;
int hash[1001]={0};
for(auto e:nums1)
hash[e]=1;
for(auto e:nums2)
{
if(hash[e]==1)
ret_set.insert(e);
}
vector<int> ret(ret_set.begin(),ret_set.end());
return ret;
}
};3.快乐数
202. 快乐数
一个数拆开平方相加其实很好写，重要的是怎么判断重复了。因此哈希表是一个很好的查重
1.先定义一个unordered_set，并且插入n
2.n没到1或者没有重复都要不停循环，那么我们结束循环条件就是n为1
3.定义一个临时遍历sum，它用来算n拆开后的平方的总和，再把n变成sum
4.这下就要看n有没有重复，重复则返回false；没有则依然循环
5.结束循环说明n为1，那么就返回true
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> us;
us.insert(n);
while(n!=1)
{
int sum = 0;
while(n)
{
sum+=(n%10)*(n%10);
n/=10;
}
n=sum;
if(us.find(n)==us.end())
us.insert(n);
else
return false;
}
return true;
}
};4.两数之和
1. 两数之和
暴力求法
两层循环就行了
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size();i++)
{
for(int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
return {i,j};
}
}
return {};
}
};洋洋洒洒写完后，看就这么几个字
"你可以想出一个时间复杂度小于
O(n^2)的算法吗？" -- 要求反而是一种提示。哈希表
1.回顾一下我们要干什么，我们要上两个数加起来等于目标的
2.那么我们如果已经知道一堆数加起来一定不能等于目标，下一个加进来的，能不能利用已知前面的特性去专门找有没有符合的呢？两层暴力循环意味着我们没有利用起来已经遍历过的数，所以哥们觉得这也可以优化文章来源：https://www.toymoban.com/news/detail-431138.html
3.遍历一个数，我们先将target减去这个数，看看表里有没有，没有就插入这个表；有的话就结束了。优化到时间复杂度为O(N)啊！文章来源地址https://www.toymoban.com/news/detail-431138.html
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> um;
int num = 0;
for(auto e:nums)
{
if(um.find(target-e)==um.end())
um.insert(make_pair(e,num++));
else
return {um.find(target-e)->second,num++};
}
return {};
}
};到了这里，关于【代码随想录】刷题Day6的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
