返回目录

题目描述

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

屏幕给出 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,4,8,7
输出	4
说明	可以构成的数字按从小到大排序为： 1，4，7，8，14，17，18，41，47，48，71，74， 78，81，84，87，147，148，178 ... （省略后面的数 字） 故第八个为41

题目解析

首先本题需要我们做一些输入校验：

• 输入同时给出 2 和 5
• 输入同时给出 6 和 9
• 输入的数字不在范围内或者有重复

以上情况的输入返回-1，表示输入校验失败。

本题需要我们求解某个序列的所有排列情况，比如无重复元素序列：[a, b, c]，则所有排列为：

• a
• b
• c
• ab
• ba
• ac
• ca
• bc
• cb
• abc
• acb
• bac
• bca
• cab
• cba

Python算法源码

def solution(nums):
    # 定义深度优先搜索函数
    def dfs(path, vis):
        nonlocal res
        # 如果路径不为空，则将路径转换为整数并添加到结果列表中
        if path:
            res.append(int(path))

        # 如果路径长度等于输入数字列表长度，则结束递归
        if len(path) == len(nums):
            return

        # 遍历输入数字列表
        for i in range(len(nums)):
            # 如果当前数字已经被访问过，则跳过
            if vis[i]:
                continue

            # 标记当前数字为已访问
            vis[i] = True

            # 继续深度优先搜索
            dfs(path + str(nums[i]), vis)

            # 如果当前数字可以替换为另一个数字，则继续搜索
            if nums[i] in map:
                dfs(path + str(map[nums[i]]), vis)

            # 恢复当前数字的未访问状态，以便下一次搜索
            vis[i] = False

    # 将输入的数字列表转换为集合，方便检查数字是否重复
    set_nums = set(nums)
    # 获取输入数字中的最大值
    n = max(set_nums)

    # 如果输入的数字个数不为4，则返回-1
    if len(set_nums) != 4:
        return -1

    # 如果同时存在数字2和5，或者同时存在数字6和9，则返回-1
    if (2 in set_nums and 5 in set_nums) or (6 in set_nums and 9 in set_nums):
        return -1

    # 定义数字替换规则的字典
    map = {2: 5, 5: 2, 6: 9, 9: 6}
    # 初始化访问数组，记录数字是否被访问过
    vis = [False] * len(nums)
    # 初始化结果列表
    res = []

    # 调用深度优先搜索函数
    dfs("", vis)

    # 对结果列表进行排序
    res.sort()
    # 获取结果中第n个数字，n为输入数字中的最大值，但不超过结果列表长度
    n = min(n, len(res))

    # 返回结果列表中第n个数字
    return res[n - 1]


if __name__ == "__main__":
    # 读取输入的数字列表
    nums = list(map(int, input().split(",")))
    # 调用solution函数并输出结果
    print(solution(nums))

C算法源码

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>

#define MAX_ELEMENTS 1000

// 记录输入的数字
int x_values[MAX_ELEMENTS];
int num_elements = 0;

// 记录转换关系
int conversion_dict[10] = {0};

// 记录所有排列结果
int permutations[MAX_ELEMENTS] = {0};
int permutations_count = 0;

char temp_path[5] = {'\0'};
int temp_path_size = 0;

int visited[4] = {0};

// 递归求解所有排列
void depth_first_search() {
    if (temp_path_size > 0) {
        permutations[permutations_count++] = atoi(temp_path);
    }

    if (temp_path_size == 4) {
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (visited[i]) continue;

        visited[i] = 1;

        temp_path[temp_path_size++] = (char) (x_values[i] + '0');
        depth_first_search();
        temp_path[--temp_path_size] = '\0';

        // 处理数字转换关系
        int num = conversion_dict[x_values[i]];
        if (num != 0) {
            temp_path[temp_path_size++] = (char) (num + '0');
            depth_first_search();
            temp_path[--temp_path_size] = '\0';
        }

        visited[i] = 0;
    }
}

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    return *((int *) a) - *((int *) b);
}

// 主解决方案函数
int solve_problem() {
    if (num_elements != 4) {
        return -1;
    }

    int max_num = INT_MIN;

    // 记录出现过的数字
    int seen[10] = {0};

    for (int i = 0; i < 4; i++) {
        int num = x_values[i];

        // 数字超出范围
        if (num < 1 || num > 9) return -1;

        if (seen[num]) {
            // 数字重复
            return -1;
        } else {
            seen[num] = 1;
        }

        // 找出最大数字
        max_num = (int) fmax(max_num, num);
    }

    // 2 和 5 不能同时出现
    if (seen[2] && seen[5]) return -1;

    // 6 和 9 不能同时出现
    if (seen[6] && seen[9]) return -1;

    // 设定数字转换关系
    conversion_dict[2] = 5;
    conversion_dict[5] = 2;
    conversion_dict[6] = 9;
    conversion_dict[9] = 6;

    // 求解所有排列
    depth_first_search();

    // 对排列结果进行排序
    qsort(permutations, permutations_count, sizeof(permutations[0]), compare);

    // 如果排列结果足够多，则返回第N个，否则返回最后一个
    if (max_num <= permutations_count) {
        return permutations[max_num - 1];
    } else {
        return permutations[permutations_count - 1];
    }
}

int main() {
    while (scanf("%d", &x_values[num_elements++])) {
        if (getchar() != ',') break;
    }

    printf("%d\n", solve_problem());

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    public static ArrayList<Integer> splitCin(char separator) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        String[] tokens = s.split(Character.toString(separator));
        ArrayList<Integer> res = new ArrayList<>();
        for (String token : tokens) {
            res.add(Integer.parseInt(token));
        }

        return res;
    }

    // 排列求解
    public static void dfs(ArrayList<Integer> nums, boolean[] vis, StringBuilder path, Map<Integer, Integer> dic, ArrayList<Integer> res) {
        if (path.length() > 0) {
            res.add(Integer.parseInt(path.toString()));
        }

        if (path.length() == nums.size()) {
            return;
        }

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

            vis[i] = true;

            path.append(nums.get(i));
            dfs(nums, vis, path, dic, res);
            path.deleteCharAt(path.length() - 1);

            // 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接
            // 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接
            if (dic.containsKey(nums.get(i))) {
                path.append(dic.get(nums.get(i)));
                dfs(nums, vis, path, dic, res);
                path.deleteCharAt(path.length() - 1);
            }

            vis[i] = false;
        }
    }

    public static int solution(ArrayList<Integer> nums) {
        if (nums.size() != 4) {
            return -1;
        }

        int n = Integer.MIN_VALUE;

        // 记录出现过的数字
        boolean[] set = new boolean[10];

        for (int num : nums) {
            if (num < 1 || num > 9) {
                // 输入的数字不在范围内
                return -1;
            }

            if (set[num]) {
                // 输入的数字有重复
                return -1;
            } else {
                set[num] = true;
            }

            // N为给出数字中最大的
            n = Math.max(n, num);
        }

        // 屏幕不能同时给出 2 和 5
        if (set[2] && set[5]) return -1;

        // 屏幕不能同时给出 6 和 9
        if (set[6] && set[9]) return -1;

        StringBuilder path = new StringBuilder();
        boolean[] vis = new boolean[nums.size()];

        // 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接
        // 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接
        Map<Integer, Integer> dic = new HashMap<>();
        dic.put(2, 5);
        dic.put(5, 2);
        dic.put(6, 9);
        dic.put(9, 6);

        // 记录排列
        ArrayList<Integer> res = new ArrayList<>();

        // 排列求解
        dfs(nums, vis, path, dic, res);

        // 给出这几个数字可拼成的数字从小到大排列位于第N位置的数字
        Collections.sort(res);

        // N为给出数字中最大的，如果不到这么多数字则给出最后一个即可
        if (n <= res.size()) {
            return res.get(n - 1);
        } else {
            return res.get(res.size() - 1);
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> nums = splitCin(',');
        System.out.println(solution(nums));
    }
}