我的问题如下; 对于数字N,我需要找出我可以计算的最大值,每个数字可以使用N次.
例如,如果N = 5,则最大值为12,因为此时数字1已被使用了5次.
我最初的方法是简单地遍历所有数字,并记录到目前为止每个数字的使用次数.当N很大时,这显然是非常低效的,所以我正在寻找关于实现这一目标的更聪明(和更有效)方法的建议.
public class Counter {
private static Hashtable numbers;
public static void main(String[] args){
Counter c = new Counter();
c.run(9);
}
public Counter() {
numbers = new Hashtable();
numbers.put(0, 0);
numbers.put(1, 0);
numbers.put(2, 0);
numbers.put(3, 0);
numbers.put(4, 0);
numbers.put(5, 0);
numbers.put(6, 0);
numbers.put(7, 0);
numbers.put(8, 0);
numbers.put(9, 0);
}
public static void run(int maxRepeat) {
int keeper = 0;
for(int maxFound = 0; maxFound <= maxRepeat; maxFound++) {
keeper++;
for (int i = 0; i < Integer.toString(keeper).length(); i++) {
int a = Integer.toString(keeper).charAt(i);
//here update the tally for appropriate digit and check if max repeats is reached
}
}
System.out.println(keeper);
}
}
David Z.. 6
对于初学者而言,不是Counter用a 支持你,而是Hashtable使用int[]代替.当你确切地知道地图必须有多少元素时,特别是当数字是数字时,数组是完美的.
话虽如此,我认为最有效的加速可能来自更好的数学,而不是更好的算法.通过一些实验(或者可能很明显),您会注意到1始终是第一个使用给定次数的数字.所以N,如果您能找到第一个使用该数字的数字1 N+1次,您知道您的答案就是之前的数字.这可以让你解决问题而不必实际计算那么高.
现在,让我们来看看有多少1用于计算各种数字.在这篇文章中,我将n用来指定一个数字,当我们试图弄清楚有多少1用于计算一个数字时,而资本N指定用多少1来计算一些数字.
从一位数字开头:
1: 1 2: 1 ... 9: 1
显然,计算一位数字所需的1的数量是...... 1.嗯,实际上我们忘记了一个:
0: 0
这在以后会很重要.所以我们应该这样说:计算一位数字所需的1的数量X是X > 0 ? 1 : 0.让我们定义一个数学函数f(n),它代表"数到1的数量n".然后
f(X) = X > 0 ? 1 : 0两位数字
对于两位数字,有两种类型.对于表格的数字1X,
10: 2 11: 4 12: 5 ... 19: 12
你可以这样想:数到1X1需要等于1的数
f(9) (从最多计数到9)加上
1(从10)加
X(从11开头的第一个数字1X,if X > 0)加上
然而,要求很多1才需要 X
或者数学上,
f(1X) = f(9) + 1 + X + f(X)
然后有两位数字高于19:
21: 13 31: 14 ... 91: 20
数到两位数要求1的数量YX与Y > 1为
f(19) (从数到19)加上
f(9) * (Y - 2)(从1到20的数字到(Y-1)9包含 - 比如if Y = 5,我的意思是20-49中的1,来自21,31,41)加上
然而,要求很多1才需要 X
或者数学上来说Y > 1,
f(YX) = f(19) + f(9) * (Y - 2) + f(X)
= f(9) + 1 + 9 + f(9) + f(9) * (Y - 2) + f(X)
= 10 + f(9) * Y + f(X)
三位数字
一旦你得到三位数的数字,你可以扩展模式.对于表格的任何三位数字1YX(现在Y可以是任何数字),从计数到该数字的总计数为1
f(99) (从最高计数到99)加上
1(从100)加
10 * Y + X(从101开头的第一个数字1YX)加上
然而,要求YX两位数的数字需要很多1
所以
f(1YX) = f(99) + 1 + YX + f(YX)
注意平行于f(1X).将逻辑继续到更多数字,对于以1开头的数字,模式是
f(1[m-digits]) = f(10^m - 1) + 1 + [m-digits] + f([m-digits])
用[m-digits]表示的长度的数字序列m.
现在,对于ZYX不以1开头的三位数字,即Z > 1,计算它们所需的1的数量是
f(199) (从数到199)加上
f(99) * (Z - 2)(从200的1开始(Z-1)99)加上
然而,要求很多1才需要 YX
所以
f(ZYX) = f(199) + f(99) * (Z - 2) + f(YX)
= f(99) + 1 + 99 + f(99) + f(99) * (Z - 2) + f(YX)
= 100 + f(99) * Z + f(YX)
现在,以1开头的数字模式似乎很清楚:
f(Z[m-digits]) = 10^m + f(10^m - 1) * Z + f([m-digits])一般情况
我们可以将最后的结果与以1开头的数字的公式结合起来.您应该能够验证以下公式是否等同于上面给出的所有数字Z1-9 的适当情况,并且它在正确的情况下做了正确的事情.Z == 0:
f(Z[m-digits]) = f(10^m - 1) * Z + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
对于表格的数字10^m - 1,如99,999等,您可以直接评估该功能:
f(10^m - 1) = m * 10^(m-1)
因为数字1将10^(m-1)在每个m数字中使用次数- 例如,当计数到999时,将在数百个地方使用100个1,在数十个地方使用100个1,并且使用100个1在那些地方.所以这就成了
f(Z[m-digits]) = Z * m * 10^(m-1) + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
对于这种特殊的方法,你可以修改确切的表达式,但我认为这非常接近于它.你在这里得到的是一个递归关系,它允许你通过在每一步去掉一个前导数字来评估f(n)计数所需的1的数量n.它的时间复杂度是对数的n.
鉴于上面的最后一个公式,实现此功能很简单.在技术上,你可以在递归中使用一个基本案例:空字符串,即定义f("")为0.但是它会为你节省一些调用以处理单个数字和表单的数字10^m - 1.这是我如何做到的,省略了一些参数验证:
private static Pattern nines = Pattern.compile("9+");
/** Return 10^m for m=0,1,...,18 */
private long pow10(int m) {
// implement with either pow(10, m) or a switch statement
}
public long f(String n) {
int Z = Integer.parseInt(n.substring(0, 1));
int nlen = n.length();
if (nlen == 1) {
return Z > 0 ? 1 : 0;
}
if (nines.matcher(n).matches()) {
return nlen * pow10(nlen - 1);
}
String m_digits = n.substring(1);
int m = nlen - 1;
return Z * m * pow10(m - 1) + f_impl(m_digits)
+ (Z > 1 ? pow10(m) : Z * (Long.parseLong(m_digits) + 1));
}
反相
这个算法解决了你问的问题的反转:也就是说,它计算了一个数字用于计算的次数n,而你想知道n你可以用给定N的数字位数(即1)来达到.所以,正如我在开头提到的回来,你要寻找的第一个n针对f(n+1) > N.
最直接的方法是从n = 0你开始计算并查看你何时超过N.
public long howHigh(long N) {
long n = 0;
while (f(n+1) <= N) { n++; }
return n;
}
但当然,与在数组中累积计数相比,这并不是更好(实际上可能更糟).完整的观点f是你不必测试每个数字; 您可以跳过很长的间隔,直到找到n这样的间隔f(n+1) > N,然后使用跳转缩小搜索范围.我推荐的一个相当简单的方法是指数搜索将结果置于上限,然后进行二分搜索以缩小范围:
public long howHigh(long N) {
long upper = 1;
while (f(upper + 1) <= N) {
upper *= 2;
}
long lower = upper / 2, mid = -1;
while (lower < upper) {
mid = (lower + upper) / 2;
if (f(mid + 1) > N) {
upper = mid;
}
else {
lower = mid + 1;
}
}
return lower;
}
由于f上面的实现是O(log(n))而指数+二进制搜索也是O(log(n)),最终的算法应该像O(log ^ 2(n)),我认为N和n之间的关系足够线性,您也可以将其视为O(log ^ 2(N)).如果您在日志空间中搜索并明智地缓存该函数的计算值,则可能将其降低到大致为O(log(N)).可能提供显着加速的变体是在确定上限之后坚持一轮插值搜索,但是编码正确是很棘手的.尽管如此,完全优化搜索算法可能是另一个问题.
对于初学者而言,不是Counter用a 支持你,而是Hashtable使用int[]代替.当你确切地知道地图必须有多少元素时,特别是当数字是数字时,数组是完美的.
话虽如此,我认为最有效的加速可能来自更好的数学,而不是更好的算法.通过一些实验(或者可能很明显),您会注意到1始终是第一个使用给定次数的数字.所以N,如果您能找到第一个使用该数字的数字1 N+1次,您知道您的答案就是之前的数字.这可以让你解决问题而不必实际计算那么高.
现在,让我们来看看有多少1用于计算各种数字.在这篇文章中,我将n用来指定一个数字,当我们试图弄清楚有多少1用于计算一个数字时,而资本N指定用多少1来计算一些数字.
从一位数字开头:
1: 1 2: 1 ... 9: 1
显然,计算一位数字所需的1的数量是...... 1.嗯,实际上我们忘记了一个:
0: 0
这在以后会很重要.所以我们应该这样说:计算一位数字所需的1的数量X是X > 0 ? 1 : 0.让我们定义一个数学函数f(n),它代表"数到1的数量n".然后
f(X) = X > 0 ? 1 : 0两位数字
对于两位数字,有两种类型.对于表格的数字1X,
10: 2 11: 4 12: 5 ... 19: 12
你可以这样想:数到1X1需要等于1的数
f(9) (从最多计数到9)加上
1(从10)加
X(从11开头的第一个数字1X,if X > 0)加上
然而,要求很多1才需要 X
或者数学上,
f(1X) = f(9) + 1 + X + f(X)
然后有两位数字高于19:
21: 13 31: 14 ... 91: 20
数到两位数要求1的数量YX与Y > 1为
f(19) (从数到19)加上
f(9) * (Y - 2)(从1到20的数字到(Y-1)9包含 - 比如if Y = 5,我的意思是20-49中的1,来自21,31,41)加上
然而,要求很多1才需要 X
或者数学上来说Y > 1,
f(YX) = f(19) + f(9) * (Y - 2) + f(X)
= f(9) + 1 + 9 + f(9) + f(9) * (Y - 2) + f(X)
= 10 + f(9) * Y + f(X)
三位数字
一旦你得到三位数的数字,你可以扩展模式.对于表格的任何三位数字1YX(现在Y可以是任何数字),从计数到该数字的总计数为1
f(99) (从最高计数到99)加上
1(从100)加
10 * Y + X(从101开头的第一个数字1YX)加上
然而,要求YX两位数的数字需要很多1
所以
f(1YX) = f(99) + 1 + YX + f(YX)
注意平行于f(1X).将逻辑继续到更多数字,对于以1开头的数字,模式是
f(1[m-digits]) = f(10^m - 1) + 1 + [m-digits] + f([m-digits])
用[m-digits]表示的长度的数字序列m.
现在,对于ZYX不以1开头的三位数字,即Z > 1,计算它们所需的1的数量是
f(199) (从数到199)加上
f(99) * (Z - 2)(从200的1开始(Z-1)99)加上
然而,要求很多1才需要 YX
所以
f(ZYX) = f(199) + f(99) * (Z - 2) + f(YX)
= f(99) + 1 + 99 + f(99) + f(99) * (Z - 2) + f(YX)
= 100 + f(99) * Z + f(YX)
现在,以1开头的数字模式似乎很清楚:
f(Z[m-digits]) = 10^m + f(10^m - 1) * Z + f([m-digits])一般情况
我们可以将最后的结果与以1开头的数字的公式结合起来.您应该能够验证以下公式是否等同于上面给出的所有数字Z1-9 的适当情况,并且它在正确的情况下做了正确的事情.Z == 0:
f(Z[m-digits]) = f(10^m - 1) * Z + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
对于表格的数字10^m - 1,如99,999等,您可以直接评估该功能:
f(10^m - 1) = m * 10^(m-1)
因为数字1将10^(m-1)在每个m数字中使用次数- 例如,当计数到999时,将在数百个地方使用100个1,在数十个地方使用100个1,并且使用100个1在那些地方.所以这就成了
f(Z[m-digits]) = Z * m * 10^(m-1) + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
对于这种特殊的方法,你可以修改确切的表达式,但我认为这非常接近于它.你在这里得到的是一个递归关系,它允许你通过在每一步去掉一个前导数字来评估f(n)计数所需的1的数量n.它的时间复杂度是对数的n.
鉴于上面的最后一个公式,实现此功能很简单.在技术上,你可以在递归中使用一个基本案例:空字符串,即定义f("")为0.但是它会为你节省一些调用以处理单个数字和表单的数字10^m - 1.这是我如何做到的,省略了一些参数验证:
private static Pattern nines = Pattern.compile("9+");
/** Return 10^m for m=0,1,...,18 */
private long pow10(int m) {
// implement with either pow(10, m) or a switch statement
}
public long f(String n) {
int Z = Integer.parseInt(n.substring(0, 1));
int nlen = n.length();
if (nlen == 1) {
return Z > 0 ? 1 : 0;
}
if (nines.matcher(n).matches()) {
return nlen * pow10(nlen - 1);
}
String m_digits = n.substring(1);
int m = nlen - 1;
return Z * m * pow10(m - 1) + f_impl(m_digits)
+ (Z > 1 ? pow10(m) : Z * (Long.parseLong(m_digits) + 1));
}
反相
这个算法解决了你问的问题的反转:也就是说,它计算了一个数字用于计算的次数n,而你想知道n你可以用给定N的数字位数(即1)来达到.所以,正如我在开头提到的回来,你要寻找的第一个n针对f(n+1) > N.
最直接的方法是从n = 0你开始计算并查看你何时超过N.
public long howHigh(long N) {
long n = 0;
while (f(n+1) <= N) { n++; }
return n;
}
但当然,与在数组中累积计数相比,这并不是更好(实际上可能更糟).完整的观点f是你不必测试每个数字; 您可以跳过很长的间隔,直到找到n这样的间隔f(n+1) > N,然后使用跳转缩小搜索范围.我推荐的一个相当简单的方法是指数搜索将结果置于上限,然后进行二分搜索以缩小范围:
public long howHigh(long N) {
long upper = 1;
while (f(upper + 1) <= N) {
upper *= 2;
}
long lower = upper / 2, mid = -1;
while (lower < upper) {
mid = (lower + upper) / 2;
if (f(mid + 1) > N) {
upper = mid;
}
else {
lower = mid + 1;
}
}
return lower;
}
由于f上面的实现是O(log(n))而指数+二进制搜索也是O(log(n)),最终的算法应该像O(log ^ 2(n)),我认为N和n之间的关系足够线性,您也可以将其视为O(log ^ 2(N)).如果您在日志空间中搜索并明智地缓存该函数的计算值,则可能将其降低到大致为O(log(N)).可能提供显着加速的变体是在确定上限之后坚持一轮插值搜索,但是编码正确是很棘手的.尽管如此,完全优化搜索算法可能是另一个问题.
京公网安备 11010802040832号 | 京ICP备19059560号-6 