下载模板优化网址
今天，带来哈希表相关算法的讲解。文中不足错漏之处望请斧正！
理论基础点这里
1. 快乐数
分析题意
出题者已经把题意明确告诉我们了:
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
题意转化
怎么理解?
如果我们替换平方和的过程中, 发现当前的数字之前已经出现过, 那我们就陷入了无限循环.
如果没有把题意转化过来, 就会手足无措了.
解决思路
那我们只需要不断重复替换平方和的过程, 再同时判断平方和之前是否出现过:
- 没出现过: 继续重复替换
- 出现过: 陷入无限循环, 结束
编程实现
取每位上的数
关于取十进制数上的每位, 可以再谈谈.
如, 要取1234中的每位数.
1234 % 10 = 4 //取到最后一位
1234 /= 10; //去掉最后一位
123 % 10 = 3 //取到倒数第二位
123 /= 10; //去掉最后一位
12 % 10 = 4 //取到倒数第三位
12 /= 10; //去掉最后一位
1 % 10 = 4 //取到倒数第四位
1 /= 10; //去掉最后一位
//最终1234变为0，结束
如果是二进制, 八进制, 只需要mod8即可.
class Solution {
public:// 可能替换的过程可能一直循环:// 如果当前得到的数之前已经得到过, 则会无限循环; 反之不会bool isHappy(int n) {unordered_set<int> appearedNum;while (n != 1) {int sum = getSqureSum(n);// 只要当前的数之前没出现过, 就代表可能这个数能变到1if (appearedNum.find(sum) == appearedNum.end()) {appearedNum.insert(sum);} else { // 反之不可能变到1return false;}n = sum;}return true;}
private:int getSqureSum(int n) {int sum = 0;while (n) {sum += pow(n % 10, 2);n /= 10;}return sum;}
};
2. 两数之和
分析题意
*很好理解, 无需分析.
题意转化
找到 x 和 y, 满足 x + y = target.
解决思路
一层遍历获取 x, 查找nums内是否有这样的 y 满足 y = target - x.
关于查找:
- for暴力查找 – O(n)
- 哈希快速查找 – O(1)
查找某个元素在某个集合中是否用过, 这是哈希的绝活; 而且题目要求返回下标. 综合这两点, 我们用 unordered_map, 存储键值对的哈希表.
编程实现
class Solution {
public:// 找到 x 和 y, 满足 x + y = targetvector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numsMap; // <value, index>// 一层遍历获取 x, 查找nums内是否有这样的 y 满足 y = target - xfor (int i = 0; i < nums.size(); ++i) {int x = nums[i];int y = target - x;auto iter = numsMap.find(y);if (iter != numsMap.end()) {int i1 = i;int i2 = iter->first;return {i, iter->second};} else {numsMap.insert(pair<int, int>(nums[i], i));}}return {};}
};
今天的分享就到这里了，感谢您能看到这里。
这里是培根的blog，期待与你共同进步！