面试难题:一个破碎的计算器
时间限制:2秒/堆栈限制:256 Memory /内存限制:256 Memory
问题戴夫的计算器坏了。当显示超过K个不同的数字时，它就停止了。
Dave想输入一个整数A，但是如果他输入了这个数字，计算器可能会停止。相反，他输入最接近的整数，不会停止计算器。
输出Dave的输入和整数A之间的差额。
输入
输入将以标准输入的下列格式提供。
A K- 在第一行中，您将得到整数A(1≦A≦10^15)，整数Dave希望输入一个空格和K(1≦K≦10)，这是他的计算器可以识别的不同数字的数目。
输出
在一行中输出Dave的输入和整数A之间的最小差。确保在输出的末尾插入一个中断行。
输入示例1
1234 2输出示例1
12在这种情况下，Dave只能使用两个不同的数字。他将输入最接近的整数1222，因此差额为12。
输入示例2
7328495 10输出示例2
0在这种情况下，戴夫的计算器一点也不坏。他可以按原样输入给定的整数A。
输入示例3
800000 1输出示例3
22223戴夫只能使用一个数字，所以777777是最接近的整数。
输入示例4
262004 2输出示例4
218最接近的整数是262222。
我用武力解决了这个问题.
我尝试所有可能的情况，在1<= i
我将得到由K个不同数字组成的两个解，并找出A和解之间的最小差。
这是一个简单的解决方案。
当A更大时，执行将超过2秒的阈值。
有什么聪明有效的方法来解决这个问题？
回答 6
Stack Overflow用户
发布于 2014-10-20 08:08:43
第一部分是:选择结果中使用的k位(在10个可能的数字中)。
只要一点数学(二项数)，就可以很容易地计算出这个数字。
在给定的k中可能出现不同的数字组合。
有多达252个可能性可供选择(252个如果k=5，否则不那么多)。
如果不清楚我说的是什么:对于k=2，有01,02,03,...09,12,13,...,19,23,24,...,89
不，例如。11因为它只有1，但是k=2允许两个不同的数字。
也没有。90因为它和09，91=19等一样。
对于k=5来说，这些可能的组合数是252，不会变大。
找出当前k的所有252种可能性
在循环中迭代它们应该不会太难。
对于，各种可能性的每个都执行以下操作：
{
在循环中，我们有A、K和当前选择的有效数字
对于解决方案(当然，在循环的每一次迭代中后者是不同的)
让我们以A=12899，K=3，位123为例。
现在搜索不允许的(从左到右)的第一个数字。
在这个示例中，这将是12899，因为其中的1和2是允许的。
将此(8)替换为下一个允许的数字(2) (如果有一个)。
并用尽可能高的数字替换它的所有权利(也是3)。
12899=>12399=>12333
将结果12333保存在数组中的某个位置等。
如果没有下一个较低的可能数字，什么也不做(什么也不去数组)
(适当地加上进位，则会在已更改的数字的左边加上一个新数字，
即。无效。我们将找到一个使用这个新数字的解决方案
当循环到那个数字时)
然后，在另一个方向上，同样的事情：
将找到的数字替换为更高的数字。
每样东西都是最低的。这个也在数组里，
当然，只有当有一个更高的可能数字。
如果是12899，8的唯一更高的替代数是9，
但9是不可能的(只有123)。
}
在整个循环完成之后(每一次迭代都产生了
最多两个新的数组条目)，您有最多502个可能的问题解决方案。
只剩下一件事要做的就是检查哪一种解决办法是最好的。计算差
对于每个条目，取最小差的解)
Stack Overflow用户
发布于 2014-10-20 09:01:41
在每一步，你都可以使用你需要的数字，那个数字+1 (mod 10)，那个数字-1 (mod 10)，或者你以前使用过的任何数字。一旦用完了数字，就只能使用以前使用过的数字。
这就创造了一棵树。在每一步中，取当前状态，并计算下一级中所有可能的新状态。
您可以在执行过程中修剪树，方法是删除与任何后续步骤中最小的增量超过一定距离的任何后续步骤。
这本质上是一个线性规划问题。
下面是完整的算法！也许有人可以微调决定修剪哪些枝条，以使它更快。
using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;
public static class Converter
{
public static int ToInt(this IEnumerable<int> values)
{
return values.Aggregate(0, (total, v) => total * 10 + v);
}
public static IEnumerable<int> ToList (this int value)
{
if (value == 0) return Enumerable.Empty<int>();
else return value.ToString().Select(x => (int)x - '0').ToList();
}
}
class Program
{
static void Main(string[] args)
{
//int desired = 262004;
//int digits = 2;
int desired = 800000;
int digits = 1;
IEnumerable<State> currentStates = new[] { new State(0, 0, desired, digits) };
foreach (var digit in desired.ToList())
{
var nextStates = currentStates.SelectMany(x => x.NextPossibleStates());
foreach (var state in nextStates.OrderBy(s => s.Delta()).Take(10))
{
Console.WriteLine(state.ToString());
}
currentStates = nextStates;
Console.WriteLine("------------");
}
Console.ReadKey();
}
public class State
{
int index;
int current;
int desired;
int digitsRemaining;
private int desiredToNow()
{
return desired.ToList().Take(index).ToInt();
}
public int Delta()
{
return Math.Abs(desiredToNow() - current);
}
public State(int index, int current, int desired, int digitsRemaining)
{
this.index = index;
this.current = current;
this.desired = desired;
this.digitsRemaining = digitsRemaining;
}
private State Next (int nextDigit, int digitsRemaining)
{
return new State(this.index + 1, this.current * 10 + nextDigit, this.desired, digitsRemaining);
}
private IEnumerable<int> NextPossibleDigitsWithDuplicates()
{
if (this.digitsRemaining > 0)
{
int nextDesiredDigit = desired.ToList().Skip(index).First();
yield return nextDesiredDigit;
yield return (nextDesiredDigit + 9) % 10;
yield return (nextDesiredDigit + 1) % 10;
}
// Any previously used digit is OK
foreach (int i in this.current.ToList())
yield return i;
}
public IEnumerable<State> NextPossibleStates()
{
var possibles = this.NextPossibleDigitsWithDuplicates().Distinct();
var possiblesUsingExistingDigits = possibles.Where(p => this.current.ToList().Contains(p));
var possiblesUsingNewDigits = possibles.Where(p => !this.current.ToList().Contains(p));
var states = possiblesUsingExistingDigits.Select(p => Next(p, this.digitsRemaining))
.Concat(possiblesUsingNewDigits.Select(p => Next(p, this.digitsRemaining - 1)))
.ToList();
var bestDelta = states.Min(s => s.Delta());
// Now reject any that can never be better
// Guessing on the '2' here ...
var validStates = states.Where(s => s.Delta() < bestDelta + 2);
return validStates;
}
public override string ToString()
{
return this.current + " d=" + this.Delta() + " remaining " + this.digitsRemaining;
}
}
}Stack Overflow用户
发布于 2014-10-20 09:34:53
在考虑了这个问题之后，我认为从左到右分配数字的A*算法是最好的。为此，我们需要估计部分解的误差的下界。一个简单的可能性是：
- 如果已经设置的数字与问题中的数字完全相同，则边界为0。
- 如果已经设置的数字较低(如问题中所示)，则将缺失的数字替换为9，以获得下限。
- 如果已经设置的数字较高，如问题中所示，则将缺失的数字替换为0，以获得下限。
以12899 3问题为例，该算法的工作方式如下：
启动节点
node best error
xxxxx 12899 0最有前途的部分解的展开xxxxx
node best error
0xxxx 09999 2900
1xxxx 12899 0
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101最有前途的部分解1 1xxxx的展开
node best error
0xxxx 09999 2900
10xxx 10999 1900
11xxx 11999 900
12xxx 12899 0
13xxx 13000 101
14xxx 14000 1101
15xxx 15000 2101
16xxx 16000 3101
17xxx 17000 4101
18xxx 18000 5101
19xxx 19000 6101
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101最有前途的部分解12 the的展开
node best error
0xxxx 09999 2900
10xxx 10999 1900
11xxx 11999 900
120xx 12099 800
121xx 12199 700
122xx 12299 600
123xx 12399 500
124xx 12499 400
125xx 12599 300
126xx 12699 200
127xx 12799 100
128xx 12899 0
129xx 12900 1
13xxx 13000 101
14xxx 14000 1101
15xxx 15000 2101
16xxx 16000 3101
17xxx 17000 4101
18xxx 18000 5101
19xxx 19000 6101
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101最有希望的部分解128 of的扩展(现在只允许数字1、2和8)
node best error
0xxxx 09999 2900
10xxx 10999 1900
11xxx 11999 900
120xx 12099 800
121xx 12199 700
122xx 12299 600
123xx 12399 500
124xx 12499 400
125xx 12599 300
126xx 12699 200
127xx 12799 100
1281x 12819 80
1282x 12829 70
1288x 12889 10
129xx 12900 1
13xxx 13000 101
14xxx 14000 1101
15xxx 15000 2101
16xxx 16000 3101
17xxx 17000 4101
18xxx 18000 5101
19xxx 19000 6101
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101最有希望的部分解决方案129 of的扩展(现在只允许数字1、2和9)
node best error
0xxxx 09999 2900
10xxx 10999 1900
11xxx 11999 900
120xx 12099 800
121xx 12199 700
122xx 12299 600
123xx 12399 500
124xx 12499 400
125xx 12599 300
126xx 12699 200
127xx 12799 100
1281x 12819 80
1282x 12829 70
1288x 12889 10
1291x 12910 11
1292x 12920 21
1299x 12990 91
13xxx 13000 101
14xxx 14000 1101
15xxx 15000 2101
16xxx 16000 3101
17xxx 17000 4101
18xxx 18000 5101
19xxx 19000 6101
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101最有希望的部分解决方案1288x的扩展(现在只允许数字1、2和8)
node best error
0xxxx 09999 2900
10xxx 10999 1900
11xxx 11999 900
120xx 12099 800
121xx 12199 700
122xx 12299 600
123xx 12399 500
124xx 12499 400
125xx 12599 300
126xx 12699 200
127xx 12799 100
1281x 12819 80
1282x 12829 70
12881 12881 18
12882 12882 17
12888 12888 11 <-- optimal solution found
1291x 12910 11
1292x 12920 21
1299x 12990 91
13xxx 13000 101
14xxx 14000 1101
15xxx 15000 2101
16xxx 16000 3101
17xxx 17000 4101
18xxx 18000 5101
19xxx 19000 6101
2xxxx 20000 7101
3xxxx 30000 17101
4xxxx 40000 27101
5xxxx 50000 37101
6xxxx 60000 47101
7xxxx 70000 57101
8xxxx 80000 67101
9xxxx 90000 77101这仍然不包括最优解可能比原始数字有更多的数字(不确定这是否可能)的情况，但您可以理解.
https://stackoverflow.com/questions/26459815
复制相似问题
腾讯云开发者
