反转之后不同整数的数目 图解题解

这道题到底在问什么

输入

nums = [1,13,10,12,31]

输出

6

输入

nums = [2,2,2]

输出

1

先想最直接的笨办法

把数组 1、13、10、12、31 摆好,下标 0 到 4。右边这块是我们的集合,现在是空的。第一阶段的任务很简单:从左到右把这五个原数一个一个放进集合。（动画第 4 步）

最优解：一步一步想明白

1. 3记牢这一句:原数入集合,反转值入集合,集合大小就是答案。集合帮我们自动去重,重复的数插进去它不涨。下面先把五个原数放进集合,再逐个反转。
2. 4把数组 1、13、10、12、31 摆好,下标 0 到 4。右边这块是我们的集合,现在是空的。第一阶段的任务很简单:从左到右把这五个原数一个一个放进集合。
3. 5指针走到下标 0,取出原数 1。前面标蓝的都是已经收进集合的原数。现在把 1 也送进去。
4. 6原数 1 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 1 个数。假如原数里有重复的,集合会自动合并、不会重复计。
5. 7指针走到下标 1,取出原数 13。前面标蓝的都是已经收进集合的原数。现在把 13 也送进去。
6. 8原数 13 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 2 个数。假如原数里有重复的,集合会自动合并、不会重复计。
7. 9指针走到下标 2,取出原数 10。前面标蓝的都是已经收进集合的原数。现在把 10 也送进去。
8. 10原数 10 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 3 个数。假如原数里有重复的,集合会自动合并、不会重复计。
9. 11指针走到下标 3,取出原数 12。前面标蓝的都是已经收进集合的原数。现在把 12 也送进去。
10. 12原数 12 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 4 个数。假如原数里有重复的,集合会自动合并、不会重复计。
11. 13指针走到下标 4,取出原数 31。前面标蓝的都是已经收进集合的原数。现在把 31 也送进去。
12. 14原数 31 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 5 个数。假如原数里有重复的,集合会自动合并、不会重复计。
13. 15第二阶段,逐个反转。轮到下标 0 的 1。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。1 走下来得到 1。
14. 16把反转值 1 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
15. 17第二阶段,逐个反转。轮到下标 1 的 13。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。13 走下来得到 31。
16. 18把反转值 31 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
17. 19第二阶段,逐个反转。轮到下标 2 的 10。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。10 走下来得到 1。注意 10 的末位是 0,反转过程里 0 在最前面,累到新数上等于没加,前导零就这样丢掉了,反转结果是 1。
18. 20把反转值 1 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
19. 21第二阶段,逐个反转。轮到下标 3 的 12。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。12 走下来得到 21。
20. 22把反转值 21 丢进集合,面板里之前没有它,这是一个新值,集合多出一行,涨到 6 个。它就是这道题里唯一一个反转后带来的新数字。
21. 23第二阶段,逐个反转。轮到下标 4 的 31。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。31 走下来得到 13。
22. 24把反转值 13 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 6 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
23. 25全部处理完。原数 1、13、10、12、31 进了集合,反转值里只有 21 是新的,其它 1、31、1、13 早就在集合里。数一数面板,一共 6 个不同的整数,这就是答案。整道题的核心只有一句:原数和反转值都塞进一个集合,看它最后有多大。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        s = set(nums)
        for x in nums:
            y = int(str(x)[::-1])
            s.add(y)
        return len(s)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countDistinctIntegers(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        for (int x : nums) {
            int y = 0;
            while (x) {
                y = y * 10 + x % 10;
                x /= 10;
            }
            s.insert(y);
        }
        return s.size();
    }
};

import java.util.*;
class Solution {
    public int countDistinctIntegers(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            s.add(x);
        }
        for (int x : nums) {
            int y = 0;
            while (x > 0) {
                y = y * 10 + x % 10;
                x /= 10;
            }
            s.add(y);
        }
        return s.size();
    }
}

复杂度

面试官可能追问