华为OD机试真题 - 数字排列 (D卷,200分)
题目描述
小明负责公司年会,想出一个趣味游戏:
屏幕给出 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
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试题库D卷 文章被收录于专栏
2024年5-11月份考的D卷,不用再看AB卷,CD卷题目一样。多种语言解法,欢迎提供更好的解法。