(C卷,200分)- 猜密码（Java & JS & Python）

题目描述

小杨申请了一个保密柜，但是他忘记了密码。只记得密码都是数字，而且所有数字都是不重复的。

请你根据他记住的数字范围和密码的最小数字数量，帮他算下有哪些可能的组合，规则如下：

1. 输出的组合都是从可选的数字范围中选取的，且不能重复；
2. 输出的密码数字要按照从小到大的顺序排列，密码组合需要按照字母顺序，从小到大的顺序排序。
3. 输出的每一个组合的数字的数量要大于等于密码最小数字数量；
4. 如果可能的组合为空，则返回“None”

输入描述

输入的第一行是可能的密码数字列表，数字间以半角逗号分隔
输入的第二行是密码最小数字数量

输出描述

可能的密码组合，每种组合显示成一行，每个组合内部的数字以半角逗号分隔，从小到大的顺序排列。

输出的组合间需要按照字典序排序。
比如：2,3,4放到2,4的前面

备注

字典序是指按照单词出现在字典的顺序进行排序的方法，比如：

• a排在b前
• a排在ab前
• ab排在ac前
• ac排在aca前

用例

题目解析

本题是一道求组合问题。可以利用回溯算法求解。

本题求组合时有如下要求：

• 组合元素个数 ≥ 密码最小数字数量（第二个输入）
• 组合内元素需要按照数值大小升序
• 组合不重复（树层去重）

输出时：

• 如果有多个组合，则多个组合需要按照字典序升序
• 如果没有组合，输出"None"

另外本题没有说明输入的数字是否为单位数，因此需要考虑多位数情况。

本题中树层去重的逻辑可以参考：

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static int[] nums;
  static int level;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    level = Integer.parseInt(sc.nextLine());

    System.out.println(getResult());
  }

  public static String getResult() {
    // 按照数值大小升序，这样后续形成的组合的内部就是按照数值大小升序的
    Arrays.sort(nums);

    // 求不重复组合
    ArrayList<String> res = new ArrayList<>();
    dfs(0, new LinkedList<>(), res);

    if (res.size() > 0) {
      // 组合间按照字典序排序
      res.sort(String::compareTo);
      return String.join("n", res);
    } else {
      return "None";
    }
  }

  public static void dfs(int index, LinkedList<String> path, ArrayList<String> res) {
    if (path.size() >= level) {
      // 如果path层数到达level层，则记录该组合
      res.add(String.join(",", path));
    }

    for (int i = index; i < nums.length; i++) {
      // 树层去重
      if (i > 0 && nums[i] == nums[i - 1]) continue;

      path.add(nums[i] + "");
      dfs(i + 1, path, res);
      path.removeLast();
    }
  }
}

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);
  const level = parseInt(await readline());
  console.log(getResult(nums, level));
})();

function getResult(nums, level) {
  // 按照数值大小升序，这样后续形成的组合的内部就是按照数值大小升序的
  nums.sort((a, b) => a - b);

  // 求不重复组合
  const res = [];
  dfs(nums, 0, level, [], res);

  if (res.length > 0) {
    // 组合间按照字典序排序
    return res.sort().join("n");
  } else {
    return "None";
  }
}

function dfs(nums, index, level, path, res) {
  if (path.length >= level) {
    // 如果path层数到达level层，则记录该组合
    res.push(path.join(","));
  }

  for (let i = index; i < nums.length; i++) {
    // 树层去重
    if (i > 0 && nums[i] == nums[i - 1]) continue;

    path.push(nums[i]);
    dfs(nums, i + 1, level, path, res);
    path.pop();
  }
}

Python算法源码

# 输入获取
nums = list(map(int, input().split(",")))
level = int(input())


def dfs(index, path, res):
    if len(path) >= level:
        # 如果path层数到达level层，则记录该组合
        res.append(",".join(map(str, path)))

    for i in range(index, len(nums)):
        # 树层去重
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        path.append(nums[i])
        dfs(i + 1, path, res)
        path.pop()


# 算法入口
def getResult():
    # 按照数值大小升序，这样后续形成的组合的内部就是按照数值大小升序的
    nums.sort()

    # 求不重复组合
    res = []
    dfs(0, [], res)

    if len(res) > 0:
        # 组合间按照字典序排序
        res.sort()
        return "n".join(res)
    else:
        return "None"


# 调用算法
print(getResult())