哈希表
题意:给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。注意:若s和t中每个字符出现的次数都相同,则称s和t互为字母异位词。
示例:
思路:我们可以先创建一个unordered_map用于记录s中元素出现的次数,然后再遍历t,让t出现元素次数减去s出现次数。最后在对map进行遍历,若map中存储的元素次数全为0,则说明两字符串互为字母异位词,输出true;否则输出false
bool isAnagram(string s, string t) {
unordered_map<char,int> map;
for(auto e:s)
{
map[e]++;
}
for(auto e:t)
{
map[e]--;
}
for(auto e:map)
{
if(e.second!=0)
{
return false;
}
}
return true;
}
题意:给定两个数组nums1和nums2,返回它们的交集唯一的。我们可以不考虑输出结果的顺序 。
示例:
思路:大体思路都是一样的,都是先去除数组中重复的元素,然后通过find找出另一个数组中的重复元素,再插入到输出数组中。有两种去重方法:1.vector去重,vector中有一个函数unique,可以将数组中重复的元素移动到数组末尾,返回的迭代器就是重复元素的首元素位置,然后将数组重复元素去除即可;2.利用unordered_set的特性去重:unordered_set的特性有:无序性,唯一性,快速查找和插入删除的特点,唯一性就是存储的元素是唯一的
vector去重代码:
void DelRepeat(vector<int>& num)//去重
{
sort(num.begin(), num.end());
auto it = unique(num.begin(), num.end());//该函数可以将数组中重复元素放在末尾,并返回重复元素的起始位置
num.erase(it, num.end());//删除重复元素
}
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
DelRepeat(nums1);
DelRepeat(nums2);
vector<int> arr;
for(auto e:nums1)
{
if(find(nums2.begin(),nums2.end(),e)!=nums2.end())
{
arr.push_back(e);
}
}
return arr;
}
利用unordered_set特性去重代码:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());//使用unordered_set的特性:值唯一去重
unordered_set<int> set2(nums2.begin(), nums2.end());
vector<int> arr;
for (auto e : set1)//遍历set1,找出set1和set2中重复的元素
{
if (set2.find(e) != set2.end())
arr.push_back(e);
}
return arr;
}
题意:编写一个算法来判断一个数n是不是快乐数。
「快乐数」定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为1,也可能是 无限循环 但始终变不1。
- 如果这个过程 结果为1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回false。
示例:
思路:判断快乐数非常简单,根据定义进行无限循环,如果循环结果有1,就表示该数为快乐数;但是如果不为快乐数,那就真的无限循环了,因此我们需要有一个判断条件,证明该数就不是快乐数。我们可以使用任意数组存储每次数位平方和的结果,当某次的数位平方和在数组中存在,就说明进入了循环的入口,该数字也就一定不是快乐数
long long HappyNum(int n)//可以计算出该元素每个位置数字的平方和
{
long long sum = 0;
while (n)
{
sum += ((n % 10)*(n % 10));
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while (n)
{
long long sum = HappyNum(n);//预防越界,定义long long接收函数返回值
if (sum == 1)//等于1,说明是快乐数
{
break;
}
if (set.find(sum) != set.end())//由于不是快乐数会导致无限循环,因此肯定在循环期间有一个数会是循环的起始
{
return false;
}
set.insert(sum);
n = sum;
}
return true;
}
题意:给定一个整数数组nums和一个整数目标值target,请你在该数组中找出 和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例:
思路:本题有两种思路,1.暴力求解:两层for循环,找出两数组合的所有可能,若有等于target的情况,写入arr中,时间复杂程度为O(n^2);2.使用unordered_map特性求解:由于unordered_map查找元素的时间复杂程度为O(1),因此我们可以将元素一一放入其中进行匹配,若有两个元素等于target,则输出arr,即节省时间,又节约空间
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> arr;
for (int i = 0; i < nums.size(); i++)//两层for循环遍历,时间复杂程度为O(n^2)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target)
{
arr.push_back(i);
arr.push_back(j);
break;
}
}
}
return arr;
}
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map;
vector<int> arr;
for(int i=0;i<nums.size();i++)
{
auto e=map.find(target-nums[i]);//将find找到的与之匹配的元素迭代器,之后需要保存
if(e!=map.end())//找到该元素
{
arr.push_back(i);
arr.push_back(e->second);
break;//跳出循环,减少时间和空间的消耗
}
map[nums[i]]=i;//若没有与之匹配的元素,则引入下一个元素继续判断,节省空间
}
return arr;
}
标签:map,arr,练习,set,day5,算法,vector,元素,unordered
From: https://blog.51cto.com/u_15209404/6461965