挑战2
 |
fuyun
2009-08-25
描述:
挑战1的逆过程,传入一整型或只包含数字的字符串型参数(任意长度),该数表示从1到某数的每数位数之和,求解某数.(不能用枚举法)如果传入的给定数不能求解出某数,需要指出某数处于的最小整数区间. 例子: 1.输入:8 输出:8 2.输入:171 输出:90 3.输入:2592 输出:900 4.输入:2600 输出:(902,903).因为902->2598,903->2601,而2598 < 2600 < 2601(符号->表示对应关系) |
 |
suntao19830709
2010-12-31
分析：
假定输入的数为给定值，输出值为目标值。 根据分析，不难看出： 长度为1的数有1-9，共9个数 长度为2的数有10-99，共90个数 长度为3的数有100-999，共900个数，类推 因此可以设定一个i，来代表所有长度为i或小于i的数之和，称为阀值，通过比较给定值和这个阀值，可以确定目标值的位数。 假定i位的整数里，最大值是max，那么阀值和给定值的差值，再除以i这个位数，应该就是max和目标值的差值。 如果上述差值除以i有余数，说明是题目中4的情况。稍微调整一下。 因此，大致的java算法如下(未考虑n小于1的情况，读者自己加吧)：
public String getN(int n){
int i = 1;
long total = Math.round(9 * Math.pow(10, i - 1));
while(n > total){
i++;
total += i * Math.round(9 * Math.pow(10, i - 1));
}
long max = Math.round(Math.pow(10, i)) - 1;
long result = max - ((total - n)/i);
if((total - n) % i == 0 ){
return String.valueOf(result) ;
}
return String.valueOf(result-1) + "," + String.valueOf(result);
}
|
