劳动服务公司网站源码,花都网站 建设信科网络,wordpress分享到微信朋友圈,电商网店代运营华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试真题Python/JS/C/C》。
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。
一、题目描述
小明负责公司年会想出一个趣味游戏
屏幕给出1~9任意4个不重复的数字大家以最快的时间给出这几个数字可拼成的数字从小到大排列位于第N位置的数字其中N为给出数字中最大的数如果不到这么多数字则给出最后一个即可。
注意
2可以当做5来使用5也可以当做2来使用进行数字拼接且屏幕不能同时给出2和56可以当做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,187…
那么第N个数字即第8个数字为41输出41。
二、输入描述
输入以逗号分隔的4个1~9的数字组成的字符串。
三、输出描述
输出这几个数字可拼成的数字从小到大排列位于第N位置的数字其中N为给出数字中最大的数。
如果输入的数字不在规定的范围内或有重复则输出-1
1、输入
1,4,8,7
2、输出
41
3、说明
可以拼接的数字为
1,4,7,8,14,17,18,41,47,48,71,74,78,81,84,87,147,148,178,187…
那么第N个数字即第8个数字为41输出41。
四、测试用例
1、输入
1,4,8,7
2、输出
41
3、说明
获取组成的数字从小到大排序后第8个数字
1,4,7,8,14,17,18,41,47,48,71,74,78,81,84,87,147,148,174,178,184,187…
即为41。
五、解题思路
输入4个1~9的数字升序排序校验输入合法性 如果不足4个数字则输出-1输入必须是1~9的数字不能同时包含2和5不能同时包含6和9 取最大的数N通过深度优先搜索dfs算法拼接所有数字参数依次为输入的4位数数组、数字是否使用过、拼接的数字获取组成的数字从小到大排序后第N个数字。
六、Python算法源码
import sys# 定义数字互换关系
replace_map {2: 5, 5: 2, 6: 9, 9: 6}def check_input(parts):if len(parts) ! 4:return Falseseen set()has2 has5 has6 has9 Falsefor part in parts:try:num int(part)except ValueError:return Falseif num 1 or num 9:return Falseif num in seen:return Falseseen.add(num)if num 2:has2 Trueif num 5:has5 Trueif num 6:has6 Trueif num 9:has9 True# 不能同时包含2和5if has2 and has5:return False# 不能同时包含6和9if has6 and has9:return Falsereturn Truedef generate_numbers(arr):numbers set()def dfs(temp, used):if temp:numbers.add(int(temp))for i in range(len(arr)):if not used[i]:used[i] True# 使用当前数字dfs(temp str(arr[i]), used)# 如果当前数字有可替换的数字if arr[i] in replace_map:dfs(temp str(replace_map[arr[i]]), used)used[i] Falsedfs(, [False]*4)return sorted(numbers)def main():input_line sys.stdin.readline().strip()parts input_line.split(,)if not check_input(parts):print(-1)returnarr sorted(map(int, parts))N arr[3]sorted_numbers generate_numbers(arr)if not sorted_numbers:print(-1)returnif N len(sorted_numbers):print(sorted_numbers[N-1])else:print(sorted_numbers[-1])if __name__ __main__:main()
七、JavaScript算法源码
const readline require(readline);// 定义数字互换关系
const replaceMap {2: 5,5: 2,6: 9,9: 6
};function checkInput(parts) {if (parts.length ! 4) return false;const seen new Set();let has2 false, has5 false, has6 false, has9 false;for (let part of parts) {let num parseInt(part);if (isNaN(num) || num 1 || num 9) return false;if (seen.has(num)) return false;seen.add(num);if (num 2) has2 true;if (num 5) has5 true;if (num 6) has6 true;if (num 9) has9 true;}// 不能同时包含2和5if (has2 has5) return false;// 不能同时包含6和9if (has6 has9) return false;return true;
}function generateNumbers(arr) {const numbers new Set();function dfs(temp, used) {if (temp ! ) {numbers.add(parseInt(temp));}for (let i 0; i arr.length; i) {if (!used[i]) {used[i] true;// 使用当前数字dfs(temp arr[i], used);// 如果当前数字有可替换的数字if (replaceMap[arr[i]] ! undefined) {dfs(temp replaceMap[arr[i]], used);}used[i] false;}}}dfs(, [false, false, false, false]);return Array.from(numbers).sort((a, b) a - b);
}const rl readline.createInterface({input: process.stdin,output: process.stdout
});rl.on(line, function(line){const parts line.trim().split(,);if (!checkInput(parts)) {console.log(-1);rl.close();return;}let arr parts.map(Number).sort((a, b) a - b);let N arr[3];let sortedNumbers generateNumbers(arr);if (sortedNumbers.length 0) {console.log(-1);rl.close();return;}if (N sortedNumbers.length) {console.log(sortedNumbers[N-1]);} else {console.log(sortedNumbers[sortedNumbers.length -1]);}rl.close();
});
八、C算法源码
#include stdio.h
#include stdlib.h
#include string.h
#include stdbool.h// 定义数字互换关系
int replace_map(int num) {if (num 2) return 5;if (num 5) return 2;if (num 6) return 9;if (num 9) return 6;return -1;
}typedef struct {int *data;int size;int capacity;
} IntSet;// 初始化集合
void initSet(IntSet *set) {set-capacity 1000;set-size 0;set-data (int*)malloc(sizeof(int)*set-capacity);
}// 添加元素到集合如果存在则不添加
void addSet(IntSet *set, int num) {for(int i0;iset-size;i) {if(set-data[i] num) return;}if(set-size set-capacity){set-capacity *2;set-data (int*)realloc(set-data, sizeof(int)*set-capacity);}set-data[set-size] num;
}// 生成所有可能的数字
void dfs(int arr[], bool used[], char temp[], int depth, IntSet *set) {if(depth 0){int num atoi(temp);addSet(set, num);}for(int i0;i4;i){if(!used[i]){used[i] true;int len strlen(temp);temp[len] arr[i] 0;temp[len1] \0;dfs(arr, used, temp, depth1, set);// 如果当前数字有可替换的数字int replaced replace_map(arr[i]);if(replaced ! -1){temp[len] replaced 0;temp[len1] \0;dfs(arr, used, temp, depth1, set);}temp[len] \0;used[i] false;}}
}// 比较函数用于qsort
int cmp(const void *a, const void *b){return (*(int*)a - *(int*)b);
}int main(){char input[100];if(!fgets(input, sizeof(input), stdin)){printf(-1\n);return 0;}// 去除换行符input[strcspn(input, \n)] 0;char *parts[4];int count 0;char *token strtok(input, ,);while(token ! NULL count 4){parts[count] token;token strtok(NULL, ,);}if(count !4){printf(-1\n);return 0;}int arr[4];bool has2 false, has5 false, has6 false, has9 false;bool seen[10] {false};for(int i0;i4;i){arr[i] atoi(parts[i]);if(arr[i]1 || arr[i]9){printf(-1\n);return 0;}if(seen[arr[i]]){printf(-1\n);return 0;}seen[arr[i]] true;if(arr[i]2) has2true;if(arr[i]5) has5true;if(arr[i]6) has6true;if(arr[i]9) has9true;}// 不能同时包含2和5if(has2 has5){printf(-1\n);return 0;}// 不能同时包含6和9if(has6 has9){printf(-1\n);return 0;}// 排序for(int i0;i3;i){for(int ji1;j4;j){if(arr[i]arr[j]){int temp arr[i];arr[i] arr[j];arr[j] temp;}}}int N arr[3];IntSet set;initSet(set);char tempStr[10] ;bool used[4] {false};dfs(arr, used, tempStr, 0, set);if(set.size 0){printf(-1\n);free(set.data);return 0;}// 排序qsort(set.data, set.size, sizeof(int), cmp);if(N set.size){printf(%d\n, set.data[N-1]);}else{printf(%d\n, set.data[set.size-1]);}free(set.data);return 0;
}
九、C算法源码
#include bits/stdc.h
using namespace std;// 定义数字互换关系
int replace_map(int num){if(num 2) return 5;if(num 5) return 2;if(num 6) return 9;if(num 9) return 6;return -1;
}int main(){string input;getline(cin, input);vectorstring parts;string token;// 分割输入stringstream ss(input);while(getline(ss, token, ,)){parts.push_back(token);}// 校验输入if(parts.size() !4){cout-1;return 0;}vectorint arr;setint seen;bool has2false, has5false, has6false, has9false;for(auto s: parts){int num stoi(s);if(num 1 || num 9) {cout-1; return 0;}if(seen.count(num)) {cout-1; return 0;}seen.insert(num);if(num 2) has2true;if(num 5) has5true;if(num 6) has6true;if(num 9) has9true;arr.push_back(num);}if((has2 has5) || (has6 has9)){cout-1;return 0;}sort(arr.begin(), arr.end());int N arr[3];setint numbers;// DFS生成数字functionvoid(string, vectorbool) dfs [](string temp, vectorbool used)-void{if(!temp.empty()){numbers.insert(stoi(temp));}for(int i0;i4;i){if(!used[i]){used[i] true;// 使用当前数字dfs(temp to_string(arr[i]), used);// 如果有可替换的数字int replaced replace_map(arr[i]);if(replaced ! -1){dfs(temp to_string(replaced), used);}used[i] false;}}};vectorbool used(4, false);dfs(, used);if(numbers.empty()){cout-1;return 0;}// 将set转换为vector并排序vectorint sorted_numbers(numbers.begin(), numbers.end());sort(sorted_numbers.begin(), sorted_numbers.end());if(N sorted_numbers.size()){coutsorted_numbers[N-1];}else{coutsorted_numbers.back();}return 0;
} 下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 2024 E卷 200分
本文收录于华为OD机试真题Python/JS/C/C
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。
