华为OD机试 - 数字排列 - 深度优先搜索dfs算法（Python/JS/C/C++ 2024 C卷 200分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
一、题目描述
小明负责公司年会，想出一个趣味游戏：
屏幕给出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,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 i=0;i<set->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 i=0;i<4;i++){if(!used[i]){used[i] = true;int len = strlen(temp);temp[len] = arr[i] + '0';temp[len+1] = '\0';dfs(arr, used, temp, depth+1, set);// 如果当前数字有可替换的数字int replaced = replace_map(arr[i]);if(replaced != -1){temp[len] = replaced + '0';temp[len+1] = '\0';dfs(arr, used, temp, depth+1, 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 i=0;i<4;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) has2=true;if(arr[i]==5) has5=true;if(arr[i]==6) has6=true;if(arr[i]==9) has9=true;}// 不能同时包含2和5if(has2 && has5){printf("-1\n");return 0;}// 不能同时包含6和9if(has6 && has9){printf("-1\n");return 0;}// 排序for(int i=0;i<3;i++){for(int j=i+1;j<4;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);vector<string> parts;string token;// 分割输入stringstream ss(input);while(getline(ss, token, ',')){parts.push_back(token);}// 校验输入if(parts.size() !=4){cout<<-1;return 0;}vector<int> arr;set<int> seen;bool has2=false, has5=false, has6=false, has9=false;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) has2=true;if(num ==5) has5=true;if(num ==6) has6=true;if(num ==9) has9=true;arr.push_back(num);}if((has2 && has5) || (has6 && has9)){cout<<-1;return 0;}sort(arr.begin(), arr.end());int N = arr[3];set<int> numbers;// DFS生成数字function<void(string, vector<bool>&)> dfs = [&](string temp, vector<bool> &used)->void{if(!temp.empty()){numbers.insert(stoi(temp));}for(int i=0;i<4;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;}}};vector<bool> used(4, false);dfs("", used);if(numbers.empty()){cout<<-1;return 0;}// 将set转换为vector并排序vector<int> sorted_numbers(numbers.begin(), numbers.end());sort(sorted_numbers.begin(), sorted_numbers.end());if(N <= sorted_numbers.size()){cout<<sorted_numbers[N-1];}else{cout<<sorted_numbers.back();}return 0;
}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
