思路分析

前言

题解区好似没有用哈希的啊。

发现大家都在用 map 来存是否出现过数字，但是需要注意的是，map 的单次查询时间复杂度是 \(\mathcal O(\log n)\) 的，对于大规模的数据就很可能会 TLE。所以，我们可以使用哈希的方法来判断数字是否出现过。

浅谈哈希

哈希，是通过哈希函数将数据映射到数组的某个位置上的技术。如果哈希函数实现的好，那么不同的数据几乎不会映射到同一个上。如果发现了相同，那么就需要采取一些方法来规避了。

这里介绍一下拉链法，思路很简单，就是对于不同的数据映射到了一个相同位置的情况下，那么就开一个 vector 来存储所有映射到了这里的值。查找时遍历整个 vector 就可以进行查值了。

做法分析

首先，我们可以无限枚举 \(x+1\) 并且去除末尾的 \(0\) 后会出现的数字。但是这样我们是一定会陷入无限循环的。为什么呢？不仅仅是因为我们没有强制退出循环，更深层的原因是因为我们形成了一个环。容易证明，我们这样枚举是一定可以回到之前访问过的一个数字的。

如何处理这个情况呢？

• 数组？但是 \(x\) 的上界达到了 \(10^9\)，如果开一个元素数量为 \(10^9\) 的数组来存储，那么我们需要大约 \(7\text{ GiB}\) 的空间，铁定 MLE。

• 我们可以定义一个 unordered_set<int> 来存储之前到达过的值。unordered_set<int> 是 STL 中的一个容器。它的底层是使用哈希实现的，理论时间复杂度是 \(\mathcal O(1)\) 的，但是常数比较大，对于时间限制比较紧张的题目建议手写哈希（当然数组开的下尽量用数组来存储），也不难写。当我们发现这次的数字已经出现过时，那么就可以断定接下来不会找到新的数值了，直接输出 unordered_set<int> 的大小即可。

代码实现

#include <iostream>
#include <unordered_set>
// 如果要使用 unordered_set，那么就必须调用这个库。
int main() {
		int x;
		std::unordered_set<int> h; 
		std::cin >> x;
		h.insert(x); // 开始需要插入开始值
		while (true) {
			++x;
			while (!(x % 10)) x /= 10;
			if (h.find(x) != h.end()) { // 判断数字是否已经出现过了
				std::cout << h.size(); // 输出 h 的大小
				return 0;
			}
			h.insert(x);
		}
		return 0;
}