判断一个数是否迷人

难度:

标签:

题目描述

You are given an integer n that consists of exactly 3 digits.

We call the number n fascinating if, after the following modification, the resulting number contains all the digits from 1 to 9 exactly once and does not contain any 0's:

Concatenate n with the numbers 2 * n and 3 * n.

Return true if n is fascinating, or false otherwise.

Concatenating two numbers means joining them together. For example, the concatenation of 121 and 371 is 121371.

Example 1:

Input: n = 192
Output: true
Explanation: We concatenate the numbers n = 192 and 2 * n = 384 and 3 * n = 576. The resulting number is 192384576. This number contains all the digits from 1 to 9 exactly once.

Example 2:

Input: n = 100
Output: false
Explanation: We concatenate the numbers n = 100 and 2 * n = 200 and 3 * n = 300. The resulting number is 100200300. This number does not satisfy any of the conditions.

Constraints:

100 <= n <= 999

代码结果

运行时间: 17 ms, 内存: 16.0 MB

/*
 * 思路：
 * 1. 获取 n, 2 * n 和 3 * n 的字符串表示。
 * 2. 将三个字符串连接起来。
 * 3. 使用 Java Stream 检查连接后的字符串是否包含数字 1 到 9 各一次且不包含任何 0。
 * 4. 如果满足条件，返回 true；否则返回 false。
 */
import java.util.stream.IntStream;
import java.util.stream.Collectors;

public class FascinatingNumberStream {
    public static boolean isFascinating(int n) {
        // Step 1: 获取 n, 2 * n 和 3 * n 的字符串表示
        String combined = "" + n + (2 * n) + (3 * n);

        // Step 2: 使用 Java Stream 检查连接后的字符串是否包含数字 1 到 9 各一次且不包含任何 0
        if (combined.length() != 9) {
            return false;
        }
        return IntStream.rangeClosed(1, 9)
                .mapToObj(i -> String.valueOf(i))
                .allMatch(combined::contains);
    }

    public static void main(String[] args) {
        System.out.println(isFascinating(192)); // true
        System.out.println(isFascinating(100)); // false
    }
}

解释

方法:

此题解首先计算输入的三位数n、2n和3n的值，然后将这些数字转换为字符串并连接起来。接着，检查生成的字符串是否恰好包含数字1到9各一次且不包含数字0。具体步骤包括：1) 检查字符串中是否包含'0'；2) 检查字符串长度是否为9；3) 检查字符串中的所有字符是否都是唯一的（通过将字符串转换为集合并比较长度来实现）。如果这三个条件都满足，返回true，否则返回false。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在检查字符串是否包含数字1到9时，不直接使用排序或其他方法而是选择使用集合来判断唯一性？

▷

使用集合来判断字符串中的字符是否唯一是一种简单而高效的方法。使用集合，我们可以直接插入每个字符，并利用集合的属性（不允许重复元素）来确保所有字符都是唯一的。如果使用排序，虽然可以通过比较相邻字符来检查重复，但排序本身通常具有O(n log n)的时间复杂度，比转换为集合并检查长度（大致为O(n)的时间复杂度）更耗时。此外，使用集合的方法代码更简洁，易于理解和维护。

🦆

如果输入的三位数n是以0结尾的，例如230，那么2n和3n的结果是否会影响字符串的总长度，从而影响算法的判断？

▷

如果输入的三位数n是以0结尾的，例如230，其2n为460，3n为690。虽然这些乘积仍然是三位数，但问题的关键在于最终生成的字符串是否正确地包含了1至9的每个数字恰好一次。在这个特定的例子中，即便n、2n和3n都是三位数，生成的字符串仍然可以满足长度为9的要求。然而，如果n、2n或3n中的任何一个乘积结果导致长度不为三位数（如数值较小），则会影响字符串的总长度，从而影响算法的判断。

🦆

题解中提到'将字符串转换为集合并比较长度'，这个方法在什么样的情况下可能会失败？或者说，这种方法是否总是可靠的？

▷

将字符串转换为集合并比较长度的方法通常是可靠的，前提是我们已经确保了字符串不包含不应存在的字符（例如数字0或超过9的数字）。这种方法的关键在于它假定输入字符串只包含目标字符集（1至9）。如果字符串包含任何非目标字符或目标字符重复，长度检查将会失败。因此，只要前置条件满足（不包含数字0，且字符串长度为9），这种方法就是可靠的。

🦆

算法中有一个明确的假设是n为三位数，那么如果n不是三位数，比如是一位或两位数，这个算法是否还能正确运行？如果不能，应该如何修改算法以适应任意位数的整数？

▷

如果n不是三位数，比如一位或两位数，这个算法可能无法正确运行，因为n、2n和3n生成的字符串可能不会达到9个字符的长度，从而无法包含所有从1到9的数字。为了修改算法适应任意位数的整数，我们可以引入一个循环或递归机制，不断增加乘数直到生成的字符串长度至少为9，并在此过程中检查生成的字符串是否满足包含1到9的数字恰好一次的条件。这样可以确保算法能适用于不同长度的整数输入。

判断一个数是否迷人

题目描述

代码结果

解释

代码细节讲解

相关问题