给定一个数字数组0-9和一个整数n，找到可以由输入数组形成且小于n的所有整数 [英] Given an array of digits 0-9 and an integer n, find all the integers which can be formed from the input array and are less than n

问题描述

这是问题所在：

为您提供了一个数字数组0-9和一个整数 n 。该数组可以包含任何给定数字的重复项。从输入数组中找出所有可以包含数字的整数，这些整数应小于 n 。输入数组中的数字可以在输出的元素中重复。

You are given an array of digits 0-9 and an integer n. The array may contain duplicates of any given digit. Find all the integers which can be formed by contatenating digits from the input array and are less than n. Digits from the input array can be repeated in an element in the output.

例如，给定输入[2，5，8]且n = 223，则输出应该如下：

For example, given as inputs [2, 5, 8] and n = 223, then the following should be the output:

[2、5、8、22、25、28、52、55、58、82、85、88、222]

[2, 5, 8, 22, 25, 28, 52, 55, 58, 82, 85, 88, 222]

很显然，任何数字少于 n 的整数都可以被接受，而任何数字被拒绝的整数都可以被接受。但是如何最有效地找到位数相同的数字呢？我知道的一个解决方案是嵌套for循环，输入整数中的每个数字一个，然后从输入数组中形成数字的每个可能组合并检查它针对 n 。但是，这似乎很笨拙，我想知道是否还有更好的方法。

Obviously any integer with fewer digits than n would be accepted and any with more denied. But how to most efficiently find those with the same number of digits?A solution I know of would be to have nested for loops, one for each digit in the input integer, and form every possible combination of digits from the input array and check it against n. This seems clunky though and I'm wondering if there's a better way.

推荐答案

使用递归。

编写一个函数，该函数输出与 n 位数相同的所有答案。将此函数称为 doit（n）。然后，为其提供一个伪代码：

Write a function that outputs all answers with the same number of digits as n. Call this function doit(n). Then, a pseudo-code for it:

1. 找出 n ，将其称为 d


2. 对于所有小于 d1 的数字c $ c> d ，输出以 d1
开头的所有数字

3. 删除数字 d 来自 n ；调用结果 n1


4. 调用 doit（n1）;在结果列表中的每个数字之前，在数字 d

1. Find the most significant digit of n, call it d
2. For all digits d1 smaller than d, output all numbers starting with d1
3. Remove the digit d from n; call the result n1
4. Call doit(n1); to each number in the resulting list, prepend the digit d

这篇关于给定一个数字数组0-9和一个整数n，找到可以由输入数组形成且小于n的所有整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！