【算法-哈希表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，结束
1
2
3
4
5
6
7
8
9

如果是二进制, 八进制, 只需要mod8即可.

class Solution {
public:
    // 可能替换的过程可能一直循环:
    // 如果当前得到的数之前已经得到过, 则会无限循环; 反之不会
    bool isHappy(int n) {
        unordered_set<int> appearedNum;

        while (n != 1) {
            int sum = getSqureSum(n);
            // 只要当前的数之前没出现过, 就代表可能这个数能变到1
            if (appearedNum.find(sum) == appearedNum.end()) {
                appearedNum.insert(sum);
            } else { // 反之不可能变到1
                return false;
            }
            n = sum;
        }

        return true;
    }
private:
    int getSqureSum(int n) {
        int sum = 0;
        while (n) {
            sum += pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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 = target
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numsMap; // 

        // 一层遍历获取 x, 查找nums内是否有这样的 y 满足 y = target - x
        for (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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！