Java 中的自描述数

10 Sept 2024 | 5 分钟阅读

给定一个数字 n。我们的任务是找出 1 到 n 之间的自描述数字。

自描述数字

自描述数字 m 是一个在 b 进制下有 b 个数字的数字，其中最高有效数字位于 0 位，最低有效数字位于 b - 1 位（从左到右，零索引，类似于数组）。此外，位于 n 处的每个数字 d，都计数数字 n 在 m 中出现的次数。观察以下示例。

示例 1

m = 2020

输出: 2020 是一个自描述数字。

解释: 由于数字 2020 只有 4 位，因此考虑使用 4 进制。数字 2 位于 0 位，表示 0 出现了两次。数字 0 位于 1 位，表示 1 出现了零次。再次，数字 2 位于 2 位，表示 2 出现了两次。之后，数字 0 放在 3 位，表示 3 出现了零次。如果我们查看数字，会发现

0 出现了两次。2 出现了两次。此外，1 和 3 出现了零次。因此，上面段落中写的所有陈述都是正确的。因此，2020 是一个自描述数字。

示例 2

m = 6210001000

输出: 6210001000 是一个自描述数字。

解释: 由于数字 2020 只有 10 位，因此考虑使用 10 进制。数字 6 位于 0 位，表示 0 出现了六次。数字 2 位于 1 位，表示 1 出现了两次。再次，数字 1 位于 2 位，表示 2 出现了一次。之后，数字 0 放在 3 位、4 位、5 位、7 位、8 位和 9 位，表示数字 3、4、5、7、8 和 9 出现了零次。在 6 位，我们看到数字 1，表示 6 出现了一次。如果我们查看数字，会发现

6 出现了一次。2 出现了一次。1 出现了两次。2 出现了一次，0 出现了六次。此外，3、4、5、7、8 和 9 出现了零次。因此，上面段落中写的所有陈述都是正确的。因此，6210001000 是一个自描述数字。

实现: 使用嵌套循环

观察以下查找自描述数字的程序。

文件名: SelfDescriptive.java

// Printing self-descriptive number
// lying between 1 to 100000
public class SelfDescriptive 
{

public boolean isSelfDescNum(int n)
{
// changing the integer n to the string str
String str = Integer.toString(n);
for (int k = 0; k < str.length(); k++) 
{

// From the string, one by one, extract each digit
String tempChar = str.charAt(k) + "";

// changing the string (temChar) into an integer
// the variable v keeps the digit located at the index 'k'
int v = Integer.parseInt(tempChar);

// computing the number of times a specific-digit
// is occurring in the number n
int cnt = 0;
for (int p = 0; p < str.length(); p++) 
{
// converting string char to integer
int tmp = Integer.parseInt(str.charAt(p) + "");

// check whether it is the same as the index 'k' or not
// if yes, then increase the count cnt.
if (tmp == k) 
{
cnt = cnt + 1;
}
}

// If it is not the same
// then returning a false value.
if (cnt != v)
{
return false;
}
}
return true;
}
// main method
public static void main(String argvs[])
{
int n = 100000;

// creating an object of the class SelfDescriptive
SelfDescriptive obj = new SelfDescriptive();

System.out.println("In the range 1 to " + n + ", we have the following self-descriptive numbers.");

for (int j = 1; j < n; j++)
{
if (obj.isSelfDescNum(j))
{
System.out.println(j);
}
}
}
}

输出

In the range 1 to 100000, we have the following self-descriptive numbers.
1210
2020
21200

解释: 在外层循环中，每次迭代都会提取所有数字并将其保存在变量 v 中。然后，在内层循环中，有一个变量 cnt 用于计算数字 j（此 j 是外层循环的 j^th 索引）在字符串中出现的次数。最终，将变量 cnt 与变量 v 进行比较。如果比较不匹配，则返回 false 值。

复杂度分析: 程序的 time complexity 为 O(n * len(n) * len(n))。 space complexity 为 O(1)。

如果我们进行一些预处理，将数字的频率存储在一个数组中，那么我们可以降低程序的复杂度。下面程序中给出了该方法的说明。

文件名: SelfDescriptive1.java

// Printing self-descriptive number
// lying between 1 to 100000
public class SelfDescriptive1 
{
public boolean isSelfDescNum(int n)
{
String st = String.valueOf(n);
    int j;
    // auxiliary array for storing the 
    // frequency count
    int freqCount[] = new int[10];
    for (j = 0; j < 10; j++)
    {
      freqCount[j] = 0;
    }
    while (n > 0) 
    {
      freqCount[n % 10] = freqCount[n % 10] + 1;
      n = n / 10;
    }
    for (j = 0; j < st.length(); j++)
    {
        // if the frequency count at the index j
        // does not match with the value at the 
        // index j present in the string st, then
        // the given number n is not the self-descriptive 
        // number.
      if (freqCount[j] != (st.charAt(j) - '0'))
      {
        return false;
      }
    }
    return true;
}
// main method
public static void main(String argvs[])
{
int n = 100000;
// creating an object of the class SelfDescriptive1
SelfDescriptive1 obj = new SelfDescriptive1();
System.out.println("In the range 1 to " + n + ", we have the following self-descriptive numbers.");
for (int j = 1; j < n; j++)
{
if (obj.isSelfDescNum(j))
{
System.out.println(j);
}
}
}
}

输出

In the range 1 to 100000, we have the following self-descriptive numbers.
1210
2020
21200

复杂度分析: 程序的 time complexity 为 O(n * len(n))。 space complexity 为 O(1)。有人可能会争辩说我们使用了辅助数组。然而，辅助数组的大小为 10，并且在任何情况下都不会改变。因此，我们可以说辅助数组的大小是固定的，使得 space complexity 为 O(1)。

下一个主题Java 中的混合继承

Java 中的自描述数

自描述数字

实现: 使用嵌套循环

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的自描述数

自描述数字

实现: 使用嵌套循环

相关帖子

ClassNotFoundException Java

How to Achieve Multiple Inheritance in Java

Lexicographical Order Java

Java ClassLoader

Java CORS Error

Java 中的有效 final 变量及示例

Java 中 HashSet 的各种操作

Java 中从数组中删除重复项

Java 中的两位小数

Java 中带跳过的锯齿形网格遍历

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器