最新华为OD机试考点合集：华为OD机试2024年真题题库（E卷+D卷+C卷）_华为od机试题库-CSDN博客
题目描述
所谓 水仙花数，是指一个n位的正整数，其各位数字的n次方和等于该数本身。
例如153是水仙花数，153是一个3位数，并且153=1^3+5^3+3^3。
输入描述
第一行输入一个整数n，表示一个n位的正整数。n在3到7之间，包含3和7。
第二行输入一个整数m，表示需要返回第m个水仙花数。
输出描述
返回长度是n的第m个水仙花数。个数从0开始编号。
若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积。
若输入不合法，返回-1。
示例1
输入
3
0
输出
153
说明
153是第一个水仙花数.
示例2
输入
9
1
输出
-1
说明
9超出范围
解题思路
打表法是一种通过预先计算并存储结果，以加快后续查询的解题方法。这个策略特别适用于具有固定解集的问题，通过提前计算所有可能的结果，避免每次查询都重新计算，大大提高效率。以下是打表法解题思路的通用过程，以及针对水仙花数问题的具体应用。
1. 预处理阶段：
- 根据问题的定义，计算并存储所有 3 到 7 位的水仙花数。这些数是固定的，因此可以提前计算出来并存储在某种数据结构中。
2. 查询阶段：
- 当接收到查询时（即输入 n 和 m），我们只需直接从预处理好的结果中进行查找，避免实时计算。
3. 解题步骤：
步骤 1：预先计算水仙花数表
- 对于每个位数 n（从 3 到 7），遍历范围内的所有数，检查其是否为水仙花数。如果某个数的各位数字的 n 次幂之和等于该数本身，那么它就是一个水仙花数。
- 将所有找到的水仙花数按位数存储在一个表格中，例如：
水仙花数表：
3 位：153, 370, 371, 407
4 位：1634, 8208, 9474
5 位：54748, 92727, 93084
6 位：548834
7 位：1741725, 4210818, 9800817, 9926315
生成水仙花数表的思路：
1. 遍历范围：
- 对于每个位数 n，生成从 10^(n-1) 到 10^n - 1 范围内的所有数字，并判断它们是否是水仙花数。
2. 判断条件：
- 对于每一个数，提取它的每一位数字，计算这些数字的 n 次幂之和。
- 如果该和等于原数，则该数是水仙花数。
3. 存储结果：
- 将找到的水仙花数按照位数存储在一个表中，以便后续查表。
c++解法：
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
// 预先存储的水仙花数表
map<int, vector<int>> table = {
{3, {153, 370, 371, 407}},
{4, {1634, 8208, 9474}},
{5, {54748, 92727, 93084}},
{6, {548834}},
{7, {1741725, 4210818, 9800817, 9926315}}
};
// 输入 n 和 m
int n, m;
cin >> n >> m;
// 检查 n 是否在 3 到 7 之间，或者 m 是否为负数
if (n < 3 || n > 7 || m < 0) {
cout << -1 << endl; // 非法输入
} else if (m >= table[n].size()) {
// 如果 m 超出该位数水仙花数的数量，输出最后一个水仙花数乘以 m
cout << (long long)table[n].back() * m << endl;
} else {
// 否则，输出第 m 个水仙花数
cout << table[n][m] << endl;
}
return 0;
}Java解法：
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 预先存储的水仙花数表
Map<Integer, int[]> table = new HashMap<>();
table.put(3, new int[]{153, 370, 371, 407});
table.put(4, new int[]{1634, 8208, 9474});
table.put(5, new int[]{54748, 92727, 93084});
table.put(6, new int[]{548834});
table.put(7, new int[]{1741725, 4210818, 9800817, 9926315});
// 创建扫描器获取用户输入
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
// 检查 n 是否在 3 到 7 之间，或者 m 是否为负数
if (n < 3 || n > 7 || m < 0) {
System.out.println(-1); // 非法输入
} else if (m >= table.get(n).length) {
// 如果 m 超出该位数水仙花数的数量，输出最后一个水仙花数乘以 m
System.out.println((long)table.get(n)[table.get(n).length - 1] * m);
} else {
// 否则，输出第 m 个水仙花数
System.out.println(table.get(n)[m]);
}
// 关闭扫描器
scanner.close();
}
}python解法：
# 预先存储的水仙花数表
table = {
3: [153, 370, 371, 407],
4: [1634, 8208, 9474],
5: [54748, 92727, 93084],
6: [548834],
7: [1741725, 4210818, 9800817, 9926315],
}
def main():
# 输入 n 和 m
n = int(input())
m = int(input())
# 检查 n 是否在 3 到 7 之间
if n < 3 or n > 7 or m < 0:
print(-1) # 非法输入
elif m + 1 > len(table[n]):
# 如果 m 超出该位数水仙花数的数量，输出最后一个水仙花数乘以 m
print(table[n][-1] * m)
else:
# 否则，输出第 m 个水仙花数
print(table[n][m])
if __name__ == "__main__":
main()