|
锁定老帖子 主题：一道关于Ruby的面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-05-10
int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
int count = 0;
for(int i = 0; i < array.length; i ++)
{
int value = array[i];
while(value > 0)
{
count += value % 10 == 1? 1 : 0;
value = value / 10;
}
}
System.out.println(count);
|
| 返回顶楼 | |
|
发表时间：2012-05-28
最后修改：2012-05-28
module NumberChecker
module Cache
def __cached_result_get(num, key)
__cache(key)[num]
end
def __cached_result_set(num, key,result)
__cache(key)[num] = result
result
end
def __cache(key)
@__cache ||= {}
@__cache[key] ||= {}
end
end
def self.included(klass)
klass.extend(NumberChecker::Cache)
end
def has_number?(num)
return num == self if self < 10
before_num = self/10
last_num = self - (before_num*10)
last_num == num ? true : before_num.has_number?(num)
end
def number_size(num)
self.class.__cached_result_get(self, num) || self.class.__cached_result_set(self, num, _number_size(num))
end
def _number_size(num)
return (self == num ? 1 : 0) if self < 10
before_num = self/10
last_num = self - (before_num*10)
before_num.number_size(num) + (last_num == num ? 1 : 0)
end
end
Fixnum.send(:include, NumberChecker)
require 'benchmark'
end_number = 1000000
Benchmark.bmbm do |x|
x.report{ puts (0..end_number).inject(0) {|result, n| result + n.number_size(1)} }
end
写道
Rehearsal ------------------------------------ 600001 7.580000 0.050000 7.630000 ( 7.680408) --------------------------- total: 7.630000sec
user system total real 600001 4.010000 0.010000 4.020000 ( 4.038076)
|
| 返回顶楼 | |
|
发表时间：2012-06-05
最后修改：2012-06-06
简单思路：
设： n为k位数 ( k = log10（n）+1 ） f(n)为0到n中含1的个数 （也就是题目所要求的解） f1（n）为n的最高位含1的个数 f9（k）为0到k位数最大值（k个9）中含1的个数。 tail(n)为n去掉最高位后的尾数 （ tail(n) = n - 10^(log10(n)) ) 显然有：f（n）=f9（k-1）+ f1(n) + f(tail(n)) 其中： f9(k) = 10 * f9(k-1) + 10^(k-1) f9(0) = 0 f1(n) = (n的最高位为1）? tail(n)+1 : 10^(k-1) 另，当k=1 (0<=n<10)时，f(n)= (n > 0) ? 1 : 0 按上面的函数递归即可。 例如： f(13) = 9中含1的个数 + 13的最高位含1的个数 + 3中含1的个数 = （10*0+1） + (tail(13) + 1) + f(3) = 1 + 4 + 1 = 6 注： 9中含1的个数 = f9(1) = 10*f9(0) + 10^0 = 0 + 1 = 1 13的最高位（十位）上出现1的个数为3+1=4个（10到13） ---------------------- f(113) = 99中含1的个数 + 113的最高位含1的个数 + 13中含1的个数 = 20 + 14 + 6 = 40 注： 99中含1的个数 = f9(2) = 10*f9(1) + 10^1 = 20 (10至19中十位上的10个1加上1、11、21、31、41直到91中个位上的10个1） ----------------------- f(213) = 99中含1的个数 + 213的最高位含1的个数 + 13中含1的个数 = 20 + 100 + 6 = 126 注： 213的最高位（百位）含1的个数为10^2 = 100个（100到199） |
| 返回顶楼 | |
|
发表时间：2012-06-06
最后修改：2012-06-06
kidneyball 写道 简单思路：
设： n为k位数 ( k = log10（n）+1 ） f(n)为0到n中含1的个数 （也就是题目所要求的解） f1（n）为n的最高位含1的个数 f9（k）为0到k位数最大值（k个9）中含1的个数。 tail(n)为n去掉最高位后的尾数 （ tail(n) = n - 10^(log10(n)) ) 显然有：f（n）=f9（k-1）+ f1(n) + f(tail(n)) 其中： f9(k) = 10 * f9(k-1) + 10^(k-1) f9(0) = 0 f1(n) = (n的最高位为1）? tail(n)+1 : 10^(k-1) 另，当k=1 (0<=n<10)时，f(n)= (n > 0) ? 1 : 0 按上面的函数递归即可。 例如： f(13) = 9中含1的个数 + 13的最高位含1的个数 + 3中含1的个数 = （10*0+1） + (tail(13) + 1) + f(3) = 1 + 4 + 1 = 6 注： 9中含1的个数 = f9(1) = 10*f9(0) + 10^0 = 0 + 1 = 1 13的最高位（十位）上出现1的个数为3+1=4个（10到13） ---------------------- f(113) = 99中含1的个数 + 113的最高位含1的个数 + 13中含1的个数 = 20 + 14 + 6 = 40 注： 99中含1的个数 = f9(2) = 10*f9(1) + 10^1 = 20 (10至19中十位上的10个1加上1、11、21、31、41直到91中个位上的10个1） ----------------------- f(213) = 99中含1的个数 + 213的最高位含1的个数 + 13中含1的个数 = 20 + 100 + 6 = 126 注： 213的最高位（百位）含1的个数为10^2 = 100个（100到199） 漏算了一部分，更正一下： 再设：fn(n) = n的最高位上的数字 = n / 10^(log10(n)) 则： f（n） = f9（k-1）+ f1(n) + (fn(n)-1)*f9(k-1) + f(tail(n)) = f1(n) + fn(n)*f9(k-1) + f(tail(n)) 例如： 213中含1数 f(213) = 0-99中含1数 + 百位上含1数 + 100-199之间除百位上的含1数（也就是 99中的含1数） + 13中的含1数 = 20 + 100 + 20 + 6 = 146 313中含1数 = 99中含1数 + 百位上含1数 + 100到299之间除百位上的的含1数（也就是 99中含1数*2） + 13中的含1数 = 20 + 100 + 40 + 6 = 166 |
| 返回顶楼 | |
|
发表时间：2012-06-06
最后修改：2012-06-06
再提供一种非递归的更简单的思路：
设k为n任意一位数（k=1,2,3,4。。。） a为n中第k位上的数字 head为n中第k位前面的数字（当k为最高位时，head为0） tail为n中第k位后面的数字（当k为1时，tail为0） 即 n = head *(10^k) + a*(10^(k-1)) + tail 那么，对于任意k，在k位上出现1的次数fn(k)为 fn(k) = 0到head*(10^k)中k位上出现1的次数 + head*(10^k)到n之间k位上出现1的次数 “0到head*(10^k)中k位上出现1的次数”很容易算出，是head*(10^(k-1))。（head每加1，则n中会出现一段k位为1的连续区间，该区间所包含数字的个数为10^(k-1) ） 而"head*(10^k)到n之间k位上出现1的次数"则根据a的不同而不同： 当a=0时，为0 当a=1时，为tail+1 当a>1时，为10^(k-1) 把k从1循环到n的最高位，累加fn（k）的结果即得最终解。 ======================= 例如 13： fn（1） = 1*10^0 + 10^0 = 2 fn（2） = 0*10^1 + 3 + 1 = 4 最终解为6 ------- 113： fn(1) = 11*10^0 + 10^0 = 12 fn(2) = 1*10^1 + 3 + 1 = 14 fn(3) = 0*10^2 + 13 + 1 = 14 最终解为：40 ------- 213： fn(1) = 21*10^0 + 10^0 = 22 fn(2) = 2*10^1 + 3 + 1 = 24 fn(3) = 0*10^2 + 10^2 = 100 最终解为：146 ------ 313： fn(1) = 31*10^0 + 10^0 = 32 fn(2) = 3*10^1 + 3 + 1 = 34 fn(3) = 0*10^2 + 10^2 = 100 最终解为：166 |
| 返回顶楼 | |
|
发表时间：2012-06-20
cttnbcj 写道 小的献丑了
组合问题，就是有个n数，X位，当他全部为空小于n时候的，1放置的全部组合方法 假如是n<100 就是有当他是两位 () () 情况一： 第一空格可以放1 然后第二空格放0-9 情况二： 第一空格可以放0-9（去1） 然后第二空格放1 就可推出任何数的组合的公式：其实上面0到9数字的个数，是平均分布的。 记得几天前有个题目也是算 1.......n 的所有数，每个位分开后的数值。 一个求值一个是计数，类似的题目。 n=13 就更加简单，脑算就行了 1() ()有0-3可能 0() 有一种可能 一共6种 我觉得这个不错，抽象出来了 |
| 返回顶楼 | |
|
发表时间：2012-06-26
归根结底是考数学嘛
|
| 返回顶楼 | |
|
发表时间：2012-06-26
object Mianshi extends App {
//获得十进制数组方法 def getScienceList(n: Int): List[Int] = { def helper(a: Int, xs: List[Int]): List[Int] = a match { case n if n / 10 != 0 => helper(a % 10, n / 10 :: xs) case n if n % 10 != 0 => helper(0, n % 10 :: xs) case _ => xs } helper(n, Nil).reverse } //获得一个数1的个数的数量 def num1Count(n: Int): Int = getScienceList(n) filter ((_:Int)==1) size //获得0到Range的1的个数 def range1Count(range: Int): Int = { var count = 0 for (i <- 0 to range) { count += num1Count(i) } count } println(range1Count(13)) } |
| 返回顶楼 | |
|
发表时间：2012-06-26
上面那个是scala代码，list的reverse是多余的.手贱多写9个字母
|
| 返回顶楼 | |
|
发表时间：2012-08-10
来个循环＋递归的.本机没有IDE，盲写的没调试，有bug请见谅。
public class OneCounter {
private int n ;
private int result;
public OneCounter(int n){
this.n = n;
this.result = 0;
count();
}
private void count(){
for(int i=0;i<=n;i++){
count(i,10);
}
}
private void count(int m,int seed){
if(m > seed/10){
return;
}
if(m % seed / (seed / 10) == 1){
this.result ++;
}
count(m,seed*10);
}
public void printResult(){
System.out.println("input ["+this.n+"] , the result is ["+this.result+"] .");
}
}
invoke： new OneCounter(13).printResult();//the result is 6. |
| 返回顶楼 | |
