题目描述

小明负责公司年会，想出一个趣味游戏：

屏幕给出 1 ~ 9 中任意 4 个不重复的数字，大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 N 位置的数字，其中 N 为给出数字中最大的（如果不到这么多数字则给出最后一个即可）。

注意：

2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接，且屏幕不能同时给出 2 和 5；
6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接，且屏幕不能同时给出 6 和 9。

如给出：1，4，8，7，则可以拼接的数字为：

1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178 ... (省略后面的数字)

那么第 N （即8）个的数字为 41。

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

输入以逗号分隔的 4 个 int 类型整数的字符串。

输出描述

输出为这几个数字可拼成的数字从小大大排列位于第 N （N为输入数字中最大的数字）位置的数字，

如果输入的数字不在范围内或者有重复，则输出-1。

用例

题目解析

首先，我们需要将输入的字符串转换为整数列表。
然后，我们需要检查输入的数字是否在范围内且没有重复。如果不满足条件，则输出-1。
接下来，我们需要根据题目要求，将数字进行排序和拼接。
最后，我们需要找到第N个数字并输出。

JS算法源码

 const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const nums = (await readline()).split(",").map(Number);
  console.log(solution(nums));
})();

function solution(nums) {
  for (let num of nums) {
      if (num < 1 || num > 9) return -1;
  }

  const set = new Set(nums);

   if (set.size != 4) {
    return -1;
  }

   if (set.has(2) && set.has(5)) {
    return -1;
  }

   if (set.has(6) && set.has(9)) {
    return -1;
  }

  const path = [];
  const vis = new Array(nums.length).fill(false);

  const map = new Map([
    [2, 5],
    [5, 2],
    [6, 9],
    [9, 6],
  ]);

    const res = [];

   dfs(nums, vis, path, map, res);

   res.sort((a, b) => a - b);

   let n = Math.min(Math.max(...nums), res.length);
  return res[n - 1];
}

function dfs(nums, vis, path, map, res) {
  const pathLength = path.length;
  const pathSum = parseInt(path.join(""));

  if (pathLength > 0) {
    res.push(pathSum);
  }

  if (pathLength == nums.length) {
    return;
  }

  for (let i = 0; i < nums.length; i++) {
    if (vis[i]) continue;

    vis[i] = true;
    path.push(nums[i]);
    dfs(nums, vis, path, map, res);
    path.pop();

    if (map.has(nums[i]) && !vis[nums.indexOf(map.get(nums[i]))]) {
      path.push(map.get(nums[i]));
      dfs(nums, vis, path, map, res);
      path.pop();
    }

    vis[i] = false;
  }
}

Java算法源码

import java.util.*;

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

        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();

        System.out.println(solution(nums));
    }

    public static int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int n = Integer.MIN_VALUE;

        for (int num : nums) {
            if (!isValidNumber(num)) {
                return -1;
            } else {
                set.add(num);
                n = Math.max(n, num);
            }
        }

        if (set.size() != 4) return -1;

        if (hasInvalidPair(set)) return -1;

        HashMap<Integer, Integer> map = createMap();

        boolean[] vis = new boolean[nums.length];

        String path = "";

        ArrayList<Integer> res = new ArrayList<>();

        dfs(nums, vis, path, map, res);

        res.sort((a, b) -> a - b);

        n = Math.min(n, res.size());
        return res.get(n - 1);
    }

    private static boolean isValidNumber(int num) {
        return num >= 1 && num <= 9;
    }

    private static boolean hasInvalidPair(HashSet<Integer> set) {
        return (set.contains(2) && set.contains(5)) || (set.contains(6) && set.contains(9));
    }

    private static HashMap<Integer, Integer> createMap() {
        HashMap<Integer, Integer> map = ne

华为OD机试真题 - 数字排列 (D卷,200分)