(C卷,100分)- 水仙花数（Java & JS & Python & C）

题目描述

所谓水仙花数，是指一个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。

用例

题目解析

这道题实现逻辑并不难，大家可以看下面算法源码。

但是本题的水仙花数最长可以有7位，也就是百万级别的，虽然下面算法差不多是O(n)的，但是估计也Hold不住。

暂时还没想到更好的办法。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    let [n, m] = lines.map(Number);
    console.log(getResult(n, m));
    lines.length = 0;
  }
});

function getResult(n, m) {
  // 若输入不合法，返回-1
  if (n < 3 || n > 7 || m < 0) return -1;

  // 提前计算好0~9的N次方, 避免后续进行重复计算
  const powN = {};
  for (let i = 0; i <= 9; i++) {
  powN[i] = Math.pow(i, n);
  }

  // N位数的最小值
  const minNum = Math.pow(10, n - 1);
  // N位数的最大值 + 1
  const maxNum = Math.pow(10, n);

  // 记录当前水仙花数
  let ans = 0;
  
  // 记录当前水仙花数的索引
  let idx = 0;

  // 遍历所有的N位数
  for (let num = minNum; num < maxNum; num++) {
// 记录num各位数字的N次方之和
let sum = 0;

// 遍历num的每一位数字
for(let c of (num + "")) {
sum += powN[c];
}

    // 判断num是否为水仙花数
    if (num == sum) {
      ans = num;
  // 如果num刚好是N位数的第m个水仙花数，则直接返回，否则继续查找
      if (idx++ == m) return ans;
    }
  }

  // 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积
  return ans * m;
}

Java算法源码

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    System.out.println(getResult(n, m));
  }

  public static long getResult(int n, int m) {
// 若输入不合法，返回-1
    if (n < 3 || n > 7 || m < 0) return -1;

    // 提前计算好0~9的N次方, 避免后续进行重复计算
    HashMap<Character, Integer> powN = new HashMap<>();
    for (int i = 0; i <= 9; i++) {
// 将整型0~9转化字符'0'~'9'，即让i+'0'即可
powN.put((char) (i + '0'), (int) Math.pow(i, n));
}

    // 最小的N位数
    int min = (int) Math.pow(10, n - 1);
// 最大的N位数
    int max = (int) Math.pow(10, n);

    // 记录当前水仙花数
    long ans = 0;

// 记录当前水仙花数是第几个
    int idx = 0;

    for (int num = min; num < max; num++) {
  // 记录num各位数字的N次方之和
  int sum = 0;
  
  // 遍历num的每一位数字
  String str = num + "";
  for(int i=0; i<n; i++) {
  sum += powN.get(str.charAt(i));
  }

      // 判断num是否为水仙花数
      if (sum == num) {
        ans = num;
// 如果num刚好是N位数的第m个水仙花数，则直接返回，否则继续查找
        if (idx++ == m) return ans;
      }
    }

    // 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积
    return ans * m;
  }
}

Python算法源码

import math

# 输入获取
n = int(input())
m = int(input())


# 算法入口
def getResult():
    # 若输入不合法，返回-1
    if n < 3 or n > 7 or m < 0:
        return -1

    # 提前计算好0~9的N次方, 避免后续进行重复计算
    powN = {}
    for i in range(10):
        powN[str(i)] = int(math.pow(i, n))

    # 最小的N位数
    minV = int(math.pow(10, n-1))
    # 最大的N位数
    maxV = int(math.pow(10, n))

    # 记录当前水仙花数
    ans = 0
    
    # 记录当前水仙花数是第几个
    idx = 0

    for num in range(minV, maxV):
        # 记录num各位数字的N次方之和
        sumV = 0
    
        # 遍历num的每一位数字
        for c in str(num):
            sumV += powN[c]

        # 判断num是否为水仙花数
        if sumV == num:
            ans = num
            
            # 如果num刚好是N位数的第m个水仙花数，则直接返回，否则继续查找
            if idx == m:
                return ans
            
            idx += 1

    # 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积
    return ans * m


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <math.h>

long getResult(int n, int m);

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    printf("%ldn", getResult(n, m));

    return 0;
}

long getResult(int n, int m) {
    // 若输入不合法，返回-1
    if(n < 3 || n > 7 || m < 0) return -1;

    // 提前计算好0~9的N次方, 避免后续进行重复计算
    int powN[10];
    for(int i=0; i<10; i++) {
        powN[i] = (int) pow(i, n);
    }

    // 最小的N位数
    int min = (int) pow(10, n - 1);
    // 最大的N位数
    int max = (int) pow(10, n);

    // 记录当前水仙花数
    long ans = 0;

    // 记录当前水仙花数是第几个
    int idx = 0;

    for(int num = min; num < max; num++) {
        // 记录num各位数字的N次方之和
        int sum = 0;

        // 遍历num的每一位数字
        int num_cp = num;
        while(num_cp > 0) {
            sum += powN[num_cp % 10];
            num_cp /= 10;
        }

        // 判断num是否为水仙花数
        if(sum == num) {
            ans = num;
            // 如果num刚好是N位数的第m个水仙花数，则直接返回，否则继续查找
            if(idx++ == m) return ans;
        }
    }

    // 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积
    return ans * m;
}