【算法-哈希表2】快乐数 和 两数之和

今天，带来哈希表相关算法的讲解。文中不足错漏之处望请斧正！

理论基础点这里

---

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，期待与你共同进步！