毛泽西

«	七月 2009	»
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

google的那道数1的面试题

silver6 | 11 十月, 2005 15:38

有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？

为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.

请大家写出自己的算法，并统计一些在你机器上计算出1111111110的时间。为了不影响大家的思路，我最后贴上我的程序。
原贴http://community.csdn.net/expert/topic/4211/4211591.xml

对于用字符串s表示的整数z，小于等于它的数中包含多少个1可以简单的分析s的各个位上的数值来表示出来。方法如下：
取字符串为a0a1a2a3a4a5，数字表示下标，简要举6位作为示例。比如a3位，它右边a4a5，我的算法只考虑该位对于它右边各位的影响。
定义一个递归函数int CountOne（string s）求结果
若a3＝0，则对右面的贡献为CountOne（a4a5）；

若a3＝1，则对右面的贡献为：a4a5的值＋1＋CountOne（a4a5）＋CountOne（a3位的权值－1）。上式中a4a5的值＋1表示从100－1a4a5这些数在a3所在的百位的1的个数，CountOne（a4a5）表示从100－1a4a5这些数中a3右边各位中1的个数，CountOne（a3位的权值－1）的值表示从000－099这些数中a3右边各位中含有的1的个数。

若a3>＝2则对右边的贡献为：a3本位权值＋CountOne（a4a5），＋CountOne（a3位的权值－1）×a3的值。上式中本位权值表示从100－199这个100个数，CountOne（a4a5）表示从a300－a3a4a5这些数中a3右边各位中1的个数，CountOne（a3位的权值－1）×a3的值表示从000－（a300－1）这些数中a3右边各位中含有的1的个数。例如a3＝4，则表示从000－099，100－199，200－299，300－399这400个数中各位和十位包含的1的个数。

例如求54321中千位4对右边各位的影响，则是case3，1000＋CountOne（321）＋CountOne（999）×4，结果我没有算，估计正确。我测试原题中1111111110，结果正确，时间为0.012秒，硬件为p43.0,512M内存,硬件较好，不过我觉得我的算法也不麻烦，大家评议。欢迎批评，qq83508052，msn：boylezhang@hotmail.com

代码：
using System;
using System.IO;
using System.Xml;
using System.Xml.XPath;
using System.Threading;
using System.Timers;

public class Sample
{
static void Main()
{
//Application.Run(new PagingSample());
string s="";
System.Console.Write("Input N:");
s = System.Console.ReadLine();

DateTime dt1 = DateTime.Now;

int count = CountOne(s);
System.Console.WriteLine("f("+s+")={0}",count);

DateTime dt2 = DateTime.Now;
TimeSpan ts = dt2.Subtract(dt1);
System.Console.WriteLine("{0:d}",ts.ToString());
System.Console.ReadLine();
}

public static void OnTimer(Object source, ElapsedEventArgs e)
{
Console.WriteLine("Hello World!");
}

public static int CountOne( string s )
{
s= TrimZeroAHead(s);
char[] array = s.ToCharArray();
int i=0,length=array.Length ;
int n = int.Parse(s);

if(n==0)
return 0;
if(n<10&&n>0)
return 1;

char c=array[length-1];
string sub="";

int count=0;

i=0;
sub=s.Substring(i+1);
c = array[i];
if(c=='0')
{
count+=CountOne(sub);
return 0;
}
else
{
if(c=='1')
{
int a = (int)Math.Pow(10,length-i-1)-1;
string temp = a.ToString();
count += 1+int.Parse(sub)+CountOne(sub)+CountOne(temp);
//return count;

}
else
{//c>=2
int multi = int.Parse(c.ToString());
int a = (int)Math.Pow(10,length-i-1)-1;
string temp = a.ToString();
count += (a+1)+CountOne(sub)+CountOne(temp)*multi;
//return count;
}
}
return count;
}

public static string TrimZeroAHead(string s)
{
int i=0;
for(i=0;i<s.Length-1;i++)
if(s[i]!='0')
break;
return s.Substring(i);
}
}

我也用pl/sql 写了一个 [回复]

ops$admin@CRMM>select fn(1111111110) from dual;

FN(1111111110)
--------------
1111111110

Elapsed: 00:00:00.00
ops$admin@CRMM>select fn(2111111110) from dual;

FN(2111111110)
--------------
2899999999

Elapsed: 00:00:00.00

create or replace function f(n in number) return number is
n_len number;
n_l_num number;
cnt number;

begin
n_len := length(to_char(n));
if n_len = 1 then
return 1;
end if;

cnt := 1;
for i in 1..n_len - 2 loop

cnt := power(10,i)+10*cnt;

end loop;
return cnt;
end f;

create or replace function fn(n in number) return number is
n_len number;
n_l_num number;
cnt number;

begin
n_len := length(to_char(n));
cnt := 0;

if n_len = 1 then
return 1;
end if;
for i in 1..n_len - 1 loop

cnt := f(power(10,n_len - i))* to_number(substr(n,i,1)) + cnt ;

if substr(n,i,1) = 1 then
cnt := cnt + to_number(substr(n,i+1)) + 1;
elsif substr(n,i,1) > 1 then
cnt := cnt + power(10,n_len - i );
end if;

end loop;
if mod(n,10) > 0 then
cnt := cnt + 1;
end if;
return cnt;
end fn;

biti_rainy | 12/10/2005, 16:49

sorry [回复]

没注意是寻找这个值。这样需要解决外层算法的变补长问题了。

biti_rainy | 12/10/2005, 17:37

好文章 [回复]

海是无边无际的,朋友是QQ438885983

hseoudf | 28/10/2006, 08:56

博客日历

最新发表

google的那道数1的面试题

发表评论

搜索

文章归档

文章分类

我的链接

新闻聚合

«	七月 2009					»
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31