散列表(哈希表)
1.实现一个基于链表法解决冲突问题的散列表
2.实现一个 LRU 缓存淘汰算法
对应练习题
哈希思想实现:
1.两数之和(1)
https://leetcode-cn.com/problems/two-sum/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//构造一个哈希数组m,一个指针数值
unordered_map<int, int> m;
vector<int> res;
//遍历nums,建立索引
for (int i = 0; i < nums.size(); ++i) {
m[nums[i]] = i;
}
//查找和值为target的整数所在下标
for (int i = 0; i < nums.size(); ++i) {
int t = target - nums[i];
//判断查找到的数字是不是第一个出现的数字,不是就OK(比如4=2+2,需要t是第二个2) 压栈存下标
if (m.count(t) && m[t] != i) {
res.push_back(i);
res.push_back(m[t]);
break;
}
}
return res;
}
};
2.Happy Number(202)
https://leetcode-cn.com/problems/happy-number/
如果出现了4,则这个数就不可能是快乐数了。
class Solution {
public:
bool isHappy(int n) {
//hash无序 值即键 表
unordered_set<int> st;
while (n != 1) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;
if (st.count(n)) break;
st.insert(n);
}
return n == 1;
}
};
网友评论