#P3233. 数字排列(200分)
-
1000ms
Tried: 84
Accepted: 25
Difficulty: 6
所属公司 :
华为od
数字排列(200分)
题目描述
小明负责公司年会,设计了一个趣味游戏:
屏幕给出 1 ~ 9 中任意 4 个不重复的数字,大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 N 位置的数字,其中 N 为给出数字中最大的(如果不到这么多数字则给出最后一个即可)。
注意:
- 2 可以当作 5 来使用,5 也可以当作 2 来使用进行数字拼接,且屏幕不能同时给出 2 和 5;
- 6 可以当作 9 来使用,9 也可以当作 6 来使用进行数字拼接,且屏幕不能同时给出 6 和 9。
如果输入的数字不在范围内或者有重复,则输出 −1。
思路
-
输入验证:首先读取输入,并进行基本验证:
- 检查数字是否在 1 到 9 之间。
- 检查是否有重复数字。
- 检查是否同时包含 2 和 5,或同时包含 6 和 9。
-
生成可能的数字列表:
- 对于每个输入的数字,根据规则生成它可能表示的数字。例如,2 可以表示为 2 和 5。
- 将所有可能的数字加入到一个集合中,以避免重复。
-
生成所有排列组合:
- 使用回溯算法生成所有长度为 1 到 n 的可能数字排列,注意在每个数字中不重复使用相同的数字。
- 将生成的数字转换为整数,并加入到结果集合中。
-
排序并输出结果:
- 将结果集合转换为有序列表。
- 根据输入数字中的最大值 N,输出第 N 个数字,如果总数少于 N,则输出最后一个数字。
cpp
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
using namespace std;
// 递归函数,生成所有可能的数字组合
void backtrack(int index, vector<vector<char>>& representations, vector<char>& current, set<int>& results) {
// 生成当前组合的所有排列
if (!current.empty()) {
// 生成所有排列
// 使用 next_permutation 需要先对当前组合进行排序
vector<char> sorted_current = current;
sort(sorted_current.begin(), sorted_current.end());
do {
string num_str(sorted_current.begin(), sorted_current.end());
results.insert(stoi(num_str));
} while (next_permutation(sorted_current.begin(), sorted_current.end()));
}
for (int i = index; i < representations.size(); ++i) {
for (char digit : representations[i]) {
current.push_back(digit);
backtrack(i + 1, representations, current, results);
current.pop_back();
}
}
}
int main() {
string input;
getline(cin, input);
// 分割输入字符串,获取数字
stringstream ss(input);
string token;
vector<int> nums;
set<int> numSet; // 用于检查重复
int maxNum = INT_MIN; // 记录最大数字
while (getline(ss, token, ',')) {
// 去除可能的空格
token.erase(remove_if(token.begin(), token.end(), ::isspace), token.end());
if (token.empty()) {
cout << "-1" << endl;
return 0;
}
int num;
try {
num = stoi(token);
} catch (...) {
cout << "-1" << endl;
return 0;
}
if (num < 1 || num > 9) {
cout << "-1" << endl;
return 0;
}
if (numSet.count(num)) {
cout << "-1" << endl;
return 0;
}
nums.push_back(num);
numSet.insert(num);
maxNum = max(maxNum, num);
}
// 输入必须有4个数字
if (nums.size() != 4) {
cout << "-1" << endl;
return 0;
}
// 检查是否同时包含2和5,6和9
if ((numSet.count(2) && numSet.count(5)) || (numSet.count(6) && numSet.count(9))) {
cout << "-1" << endl;
return 0;
}
// 为每个数字生成可能的表示
vector<vector<char>> representations;
for (int num : nums) {
vector<char> reps;
if (num == 2 || num == 5) {
reps.push_back('2');
reps.push_back('5');
} else if (num == 6 || num == 9) {
reps.push_back('6');
reps.push_back('9');
} else {
reps.push_back('0' + num);
}
representations.push_back(reps);
}
set<int> results;
vector<char> current;
backtrack(0, representations, current, results);
// 将结果转换为有序列表
vector<int> resultList(results.begin(), results.end());
sort(resultList.begin(), resultList.end());
// 输出第N个数字
int N = maxNum;
if (N > resultList.size()) {
N = resultList.size();
}
if (N <= 0) {
cout << "-1" << endl;
} else {
cout << resultList[N - 1] << endl;
}
return 0;
}
python
import sys
import itertools
def main():
# 读取输入并去除首尾空白字符
input_str = sys.stdin.readline().strip()
tokens = input_str.split(',')
nums = []
num_set = set()
max_num = -float('inf')
# 输入验证
for token in tokens:
token = token.strip()
if not token:
print(-1)
return
try:
num = int(token)
except:
print(-1)
return
if num < 1 or num > 9:
print(-1)
return
if num in num_set:
print(-1)
return
nums.append(num)
num_set.add(num)
if num > max_num:
max_num = num
# 输入必须有4个数字
if len(nums) != 4:
print(-1)
return
# 检查是否同时包含2和5,或者6和9
if (2 in num_set and 5 in num_set) or (6 in num_set and 9 in num_set):
print(-1)
return
# 为每个数字生成可能的表示
representations = []
for num in nums:
reps = []
if num == 2 or num == 5:
reps = ['2', '5']
elif num == 6 or num == 9:
reps = ['6', '9']
else:
reps = [str(num)]
representations.append(reps)
results = set()
# 递归生成所有可能的组合
def backtrack(index, current):
# 如果当前组合不为空,则生成所有排列并加入结果集
if current:
# 生成当前组合的所有排列
perms = set(itertools.permutations(current))
for perm in perms:
num = int(''.join(perm))
results.add(num)
# 继续选择下一个数字
for i in range(index, len(representations)):
for rep in representations[i]:
current.append(rep)
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
# 将结果转换为有序列表
result_list = sorted(results)
# 输出第N个数字
N = max_num
if N > len(result_list):
N = len(result_list)
if N <= 0:
print(-1)
else:
print(result_list[N - 1])
if __name__ == "__main__":
main()
java
import java.util.*;
import java.io.*;
public class Main {
// 递归函数,生成所有可能的数字组合
public static void backtrack(int index, List<List<Character>> representations, List<Character> current, Set<Integer> results) {
if (!current.isEmpty()) {
// 生成当前组合的所有排列
List<Character> sortedCurrent = new ArrayList<>(current);
Collections.sort(sortedCurrent);
Set<String> perms = new HashSet<>();
permute(sortedCurrent, 0, perms);
for (String perm : perms) {
results.add(Integer.parseInt(perm));
}
}
for (int i = index; i < representations.size(); i++) {
for (char digit : representations.get(i)) {
current.add(digit);
backtrack(i + 1, representations, current, results);
current.remove(current.size() - 1);
}
}
}
// 生成所有排列并存储为字符串
public static void permute(List<Character> chars, int start, Set<String> perms) {
if (start == chars.size() - 1) {
StringBuilder sb = new StringBuilder();
for (char c : chars) {
sb.append(c);
}
perms.add(sb.toString());
return;
}
for (int i = start; i < chars.size(); i++) {
Collections.swap(chars, start, i);
permute(chars, start + 1, perms);
Collections.swap(chars, start, i);
}
}
public static void main(String[] args) throws IOException {
// 读取输入并验证
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String[] tokens = input.split(",");
Set<Integer> numSet = new HashSet<>();
int maxNum = Integer.MIN_VALUE;
List<Integer> nums = new ArrayList<>();
// 输入验证
for (String token : tokens) {
token = token.trim();
if (token.isEmpty()) {
System.out.println(-1);
return;
}
int num;
try {
num = Integer.parseInt(token);
} catch (NumberFormatException e) {
System.out.println(-1);
return;
}
if (num < 1 || num > 9) {
System.out.println(-1);
return;
}
if (numSet.contains(num)) {
System.out.println(-1);
return;
}
nums.add(num);
numSet.add(num);
if (num > maxNum) {
maxNum = num;
}
}
// 输入必须有4个数字
if (nums.size() != 4) {
System.out.println(-1);
return;
}
// 检查是否同时包含2和5,6和9
if ((numSet.contains(2) && numSet.contains(5)) || (numSet.contains(6) && numSet.contains(9))) {
System.out.println(-1);
return;
}
// 为每个数字生成可能的表示
List<List<Character>> representations = new ArrayList<>();
for (int num : nums) {
List<Character> reps = new ArrayList<>();
if (num == 2 || num == 5) {
reps.add('2');
reps.add('5');
} else if (num == 6 || num == 9) {
reps.add('6');
reps.add('9');
} else {
reps.add((char) ('0' + num));
}
representations.add(reps);
}
Set<Integer> results = new HashSet<>();
List<Character> current = new ArrayList<>();
backtrack(0, representations, current, results);
// 将结果转换为有序列表
List<Integer> resultList = new ArrayList<>(results);
Collections.sort(resultList);
// 输出第N个数字
int N = maxNum;
if (N > resultList.size()) {
N = resultList.size();
}
if (N <= 0) {
System.out.println(-1);
} else {
System.out.println(resultList.get(N - 1));
}
}
}
题目内容
小明负责公司年会,想出一个趣味游戏:
屏幕给出 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 。
输入描述
输入以逗号分隔的 4 个 int 类型整数的字符串。
输出描述
输出为这几个数字可拼成的数字从小大大排列位于第 N ( N 为输入数字中最大的数字)位置的数字,
如果输入的数字不在范围内或者有重复,则输出 −1。
样例1
输入
1,4,8,7
输出
41
说明
可以构成的数字按从小到大排序为:
1,4,7,8,14,17,18,41,47,48,71,74,78,81,84,87,147,148,178 ... (省略后面的数字),
故第8个为41
样例2
输入
2,5,1
输出
-1
说明
2和5不能同时出现
样例3
输入
3,0,9
输出
-1
说明
0不在1到9范围内
样例4
输入
3,9,7,8
输出
39
说明
注意9可以当6使用,所以可以构成的数字按从小到大排序为:3,6,7,8,9,36,37,38,39,63,67,68,73,76,78,79,83 ... (省略后面的数字),
故第9个为39