leecode349.两个数组的交集
这个题目有两种解法，第一种解法是直接用unordered_set来解决，因为他可以自动排序并且去重。而且查找复杂度很低
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> one(nums1.begin(), nums1.end());
unordered_set<int> two(nums2.begin(), nums2.end());
vector<int> result;
for(auto num:one){
if(two.find(num) != two.end()){
result.push_back(num);
}
}
return result;
}
};
但是这种写法有一个问题，就是one，two比较大的时候比较耗空间，我们用时间换了空间。那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。
但是我们可以直观的发现，此题的数据范围是1-1000，所以我们可以制造一个1000size的hash数组
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//一定要记得初始化，不然hash表内的数据不为0
int hashtable[1001]={0};
unordered_set<int> two(nums2.begin(), nums2.end());
vector<int> result;
for(auto num:nums1)
{hashtable[num]++;}
for(auto num2:two){
if(hashtable[num2] > 0){
result.push_back(num2);
}
}
return result;
}
};
leecode202. 快乐数
class Solution {
public:
int getSum(int n){
int sum = 0;
while(n!=0){
//关键就是这步，这步很重要
sum += (n%10) * (n%10);
n/=10;
}
return sum;
}
//判断数字是否重复出现过，如果重复出现过证明进入了死循环
unordered_set<int> cnt;
int result;
int ans = 0;;
bool isHappy(int n) {
while(1){
result = getSum(n);
if(result == 1){
return true;
}
if(cnt.find(result) == cnt.end()){
cnt.insert(result);
}
//说明已经进入无线循环
else if(cnt.find(result) != cnt.end()){
return false;
}
n = result;
}
}
};
leecode1. 两数之和
这道题我在第一次做的时候，用的是暴力解法
直到我在代码随想录上看见了一道不错的解法，是小于O(n2)的
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> cnt;
for(int i = 0; i < nums.size(); i++){
auto iter = cnt.find(target - nums[i]);
if(iter != cnt.end()){
return {i, iter->second};
}
cnt.insert(pair<int,int>(nums[i],i));
}
return {};
}
};
