一道GOOGLE的面视题

f(0) = 0;
f(1) = 1;int ones(long unsigned n){
if(n==1)
return 1;
else if(n==0)
return 0;
else
return ones(n-1)+howmany(n);
}c++的，测试了一下，stack overflow

public class FindOne { public static void main(String[] args) {
System.out.println(find(13));
}

public static int find(int n){
int count =0;
String str;
char c;
for(int i=1;i<=n;i++){
str = Integer.toString(i);
for(int j=0;j<str.length();j++){
c = str.charAt(j);
if(c=='1') count++;
}
}
return count;
}}

第二题是要求写一个if(n==find(n)){System.out.println(n);}的算法。java没有goto，应该是考验对break和continue的理解。

第二道题如果用第一道题的结果n==f(n)，效率就太低了。
1.
int count1(int n){
   int count=0;
   for (int i=1;i<=n;i++)
   {
      count+=getOneNumber(i);
   }
}int getOneNumber(int n)
{
   int i=0;
   str = Integer.toString(n);
   for(int j=0;j<str.length();j++){
c = str.charAt(j);
if(c=='1') i++;
   }
   return i;
}2,
//注：限定找到99999,以免没有这样的数，死循环到溢出
int getMinNum(){
  int count=0;
  for(int i=1;i<=99999;i++)
    count+=getOneNumber(i);
    if (i.equals(count)) return i;
  }
}

1,的count1最后忘写return count;了

public static void countOne(int n){
        String a = "";
        for (int i = 1;i <= n;i++){
            a += i ;
        }
        System.out.println(a.length() - a.replaceAll("1", "").length());
    }

修改了5楼,做第二题,请大家指正
结果为1public class FindOne
{ public static void main(String[] args)
{

System.out.println(find());
}

public static int find()
{
int count =0;
String str=new String();
char c;
boolean b=true;
for(int i=1;b;i++)
{
str = Integer.toString(i);
for(int j=0;j<str.length();j++)
{
c = str.charAt(j);
if(c=='1') count++;
}
if(count==i) b=false;
}
return count;
}}

这是考数据结构的,不是考Java.

第二题是什么东西,根本看不懂
编写一个程序,得出最先使得 f(n)等于n的整数n;根本不知道f(n)是什么,假设f(n)=n
那么这个题目是怎么回事?

怎么这么多人看不懂第二题
f(0) = 0;//0        f(n) = n
f(1) = 1;//0,1      f(n) = n
f(2) = 1;//0,1,2    f(n) < n
f(3) = 1;//0,1,2,3  f(n) < n
...按照这样的话其实f(n)=n最小的是0，其次是1，如果是>1,则要算法实现了

我觉得第一题应该是“算”出来的，而不应该是“数”出来的。f(a)的情况： return a>=1 ? 1:0;f(a,b)的情况：return f(a,0) + f(b);
计算f(a,0): if (a>=2) return a*f(10)+10;
else return f(10)+b+1;f(a,b,c)的情况：return f(a,0,0) + f(b,c);
计算f(a,0,0): if (a>=2) return a*f(10,0)+100;
else return f(10,0)+bc+1;...f(a,b,c...n)的情况：return f(a,0,0...) + f(b,c...n);
计算f(a,0,0...): if (a>=2) return a*f(10,0...)+10^(n-1);
else return f(10,0...)+bc...n+1;递归计算，输入参数用int[], 比如12345用{1,2,3,4,5}表示。

楼上的理解也有问题:f(n)表示的是"从1到这个数字之间的出现的1的个数",所以n是不能取0的
因此符合条件的最小n应该为1看懂第一题,加一个f(n)=n的条件就是第二题了啊
应该不难理解的啊~~~~~

两种算法时间复杂度分别为：
O(n*log(n))
O(2n-2)

package com;public class DiGui {
public int find(int g) {
int sum = 0;
if (g == 1) {
return sum + 1;
} else { String s = String.valueOf(g);
for (int i = 0; i < s.length(); i++) {
if ('1' == s.charAt(i))
sum++;
}
}
return find(g - 1) + sum;
} /**
* @param args
*/
public static void main(String[] args) {
if (args.length == 0)
args = new String[] { "31" };
int p = Integer.parseInt(args[0]);
DiGui d = new DiGui();
System.out.println(d.find(p));
for (int i=2;i<9999;i++){
if (i==d.find(i))
System.out.println(i);

} // TODO Auto-generated method stub }}

http://htok.net/oursite/servlet/SuperFace/forum/forum2.html?htokid=c0.0.2&id=21

billpin的思路应该是正解！
Google如果和大家的思路一样，那搜索效率一定太低了；一定是有本质的算法来解决问题。

nirendao(黑山老猫)您好！总算你看懂了我的算法！知音啊！现在把我另外的一个不成熟想法和你研究，我没有时间把它成熟化了采用向上和2靠拢：
譬如：
1， f(1) =1 + 1 -(2-1) =1
10， f(10)=11 + 1 -(20-10) =2
16， f(16)=11 + 1 -(20-16+1) =8
100 f(100)=111 +1 - (200-100) =12 解释一下：就是n有多少位数，等号后面就用多少个1作为一个数字，加上1，减去补空的个数，必须注意大于1的时候需要修正，象16就是，大概这个思路，具体没有时间研究了，这样可以推出一个等式，直接计算出结果。

#include <iostream.h>int findCout1(long unsigned n)
{
int count=0;
if(0==n)
{
count=0;
}
else
{
if(1==n%10 || 0==n%10)
count=findCout1(n-1)+1;
else
count=findCout1(n-1);
}
return count;
}
void main()
{
long unsigned n=0;
cout<<"Please input the number:";
cin>>n;
cout<<"\n"<<n<<" contains "<<findCout1(n)<<" '1'\n";
}
测试通过了：）

顶，
billpin() 是数学家

billpin() 的不对，f(100)=21而不是12。

想出解法了~~~帖出来~~大家指点一下~~~：）
import java.lang.String;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.lang.Math;public class regreg {
    public regreg() {
        super();
    }    public static long find(long number,int f)throws Exception
    {
        long rs=0;
        for(long i=1;i<=number;i++){rs=rs+(String.valueOf(i)+"0").split(String.valueOf(f)).length-1;}
        return rs;
    }    public static long square(long a,long b)throws Exception
    {
        if(b==0)return 1;
        long rs=1;
        for(long i=0;i<b;i++){rs=rs*a;}
        return a;
    }    public static long find1(long number,int f)throws Exception
    {
        long rs=0,an=0,bn=0;
        int cn=0;
        String numberString=String.valueOf(number);
        for(int i=1;i<=numberString.length();i++)
        {
            an=0;bn=0;
            cn=Integer.parseInt(numberString.substring(numberString.length()-i,numberString.length()-i+1));
            try
            {
                an=Long.parseLong(numberString.substring(0,numberString.length()-i));
            }
            catch(Exception e){}
            try
            {
                bn=Long.parseLong(numberString.substring(numberString.length()-i+1));
            }
            catch(Exception e){}
            if(cn>f)an++;
            rs=rs+an*square(10,i-1);
            if(cn==f)rs=rs+bn+1;
        }
        return rs;
    }    public static void main(String[] args)throws Exception
    {
        System.out.println("rs="+find(21,1));
    }
}
我用遍历的方法是用来求正算法的正确性的~~~

补充一下~~FIND方的的二个参数第一个数大家都知道第二个是要找哪个数~~这里是1

再补充一下~``呵呵~~FIND是遍历方法FIND1才是我写的新方法：）

我说个算法：
首先设从1位数到N位数最大值之间1出现的次数为F(N)；
解释一下F(N)：F(1)就是0-9之间1出现的次数，F(2)就是0-99之间1出现的次数。
可以得到递推公式：F(N) = 10^(N-1) + 10 * F(N-1);F(0)=0;
不难得到非递推公式：F(N) = N * 10^(N-1);下面再计算f(n);设N是n的位数，head是n的最高位数，tail是n除了最高位的N-1位数；
解释一下：当n=63时，N=2，head=6，tail=3；当n=7503时，N=4，head=7，tail=503。我们分两种情况计算：当head=1时、和当head>1时；当head=1时，f(n) = F(N-1) + tail + 1 + f(tail)；
当head>1时，f(n) = head * F(N-1) + 1000 + f(tail)；后面的帖子我会解释一下这些公式的道理。

对公式的解释：递推公式我就不说了，刚才又想了一下，完全没有必要用递推。
F(N) = N * 10^(N-1):
从1位数到N位数最大值的全体数字，在第1位取1时其它N-1位有10^(N-1)种组合，同理其余几位取1时，也有10^(N-1)种组合，所以每一位上1出现的次数都是10^(N-1)次，加起来就是N * 10^(N-1)次。再看当head=1时，f(n) = F(N-1) + tail + 1 + f(tail)；
对于N位数，先计算出从1位数到N-1位数最大值间1出现的次数，显然就是F(N-1)；公式的第一项。
然后计算从N位数的最小值到n之间，最高位出现1的次数：显然，除了最高位的N-1位数有tail+1个，所以最高位出现1的次数就是tail+1；公式的中间项。
现在还需要计算从N位数的最小值到n之间，除了最高位的其余N-1位1出现的次数，显然就是f(tail)了。
这里f(0)=0；

对公式的解释：当head>1时，f(n) = head * F(N-1) + 1000 + f(tail)；
以n=7503为例：从0-6999间，除了第4位的另外3位1出现的次数应为7 * F(3)，当最高位（第4位）为1时有1000个数字，从7000-7503间1出现的次数等于f(503)。
所以他们的累加就是全部1出现的次数：7*F(3) + 1000 + f(503)。

用C#写的算法：
    static public double F(double N)
    {
      if(N == 0)
        return 0;
      else
        return N * Math.Pow(10, N-1);
    }    static public double f(double n)
    {
      if(n == 0)
        return 0;
      double N = Math.Floor(Math.Log10(n)) + 1;
      double head =  Math.Floor(n / Math.Pow(10, N - 1));
      double tail = n - head * Math.Pow(10, N - 1);      if(head == 1)
      {
        return F(N - 1) + tail + 1 + f(tail);
      }
      else
      {
        return head * F(N - 1) + Math.Pow(10, N - 1) + f(tail);
      }
    }
//用二分法查找该数值；结果是1111111110
    static public double Find()
    {
    //f(0)=0;f(1)=1;全体2位数的f(n)都比n小，所以该算法从2位数开始查找
      double y = 2;
      while(F(y) < Math.Pow(10, y))
        y++;      double left = Math.Pow(10, y -1);
      double right = Math.Pow(10, y);
      double center = left + Math.Floor((right - left)/2);
      double fcenter;      while((fcenter = f(center)) != center)
      {
        if(fcenter > center)
        {
          right = center;
        }
        else
        {
          left = center;
        }
        center = left + Math.Floor((right - left)/2);
      }
      return center;
    }

1.
int getnum(int n){
   String buffer = "";
   int count = 0;
   for(int i = 0;i < n;i++){
     buffer + = String.valueOf(i+1);
}
  for(int i = 0;i<buffer.length;i++)
     if(buffer.charAt(i) == '1')
       count ++; return count;
}
2.
for(int i = 0;i<n;i++){
  if(getnum(i)==i)
System.out.println("n is:"+i)
}

我大概测了一下，在搜索2000以内的整数时，楼上那位大哥的算法比我下面这个直接算得要慢很多啊，因为反复的用数据转换和取子串要浪费好多的运算时间的啊，你还不如直接按下面的做得了，下面的是直接搜索的，算法我还在想，见笑了。
package count;public class TestCount {
public static void main(String[] args) {
int result = getFirstNumber();
System.out.println("Result = "+result);
}
public static int  getFirstNumber()
{
int number = 2;
for(; ;number++)
{
  int result = 0;
   for(int i = 1;i<=number;i++)
   {
String s = Integer.toString(i);
    result += getNumOf(s,'1');
    }

   if(result == number)break;
}
System.out.println("Result = "+number);
return number;
}
public static  int getNumOf(String s,char ch)
{
int a=0;
for(int i = 0;i<s.length();i++)
if(s.charAt(i)==ch)a++;
return a;
}
}

求f(n)显然不能用从1到n一个一个搜索累加1的方法，这种算法的时间复杂度是O(n)。
我上面写的f(n)的时间复杂度是O(log10(n))。第二题的时间复杂度也不过是O(log10(n) * log2(n))

第一题
public class TestCount {
   public static void main(String[] args)
   {
int result = findOne(13);
System.out.println("Result = "+result);
   }
   public static int findOne(int n)
   {
int curVal;
int curLevel;
int count;
int tmp; String s = Integer.toString(n);

if(n <= 0)
{
return 0;
}
else
{
curLevel = s.length() - 1;
curVal = n / (int)Math.pow(10,curLevel);
count = 0;
for(int i = 0; i < curLevel; i++)
    count = count * 10 + (int)Math.pow(10,i);
if(curLevel == 0)
    count = 0;
else if (count == 0)
    count = 1;

tmp = n - (int)Math.pow(10,curLevel) * curVal;
if(curVal == 1)
    count = count + tmp + 1 + findOne(tmp);
else
    count = (int)Math.pow(10,curLevel) + count * curVal + findOne(tmp);
return count;
}
    }
}
第二题没看明白什么意思

believefym(暮色，miss，迷失，miss)
怎么这么多人看不懂第二题
f(0) = 0;//0        f(n) = n
f(1) = 1;//0,1      f(n) = n
f(2) = 1;//0,1,2    f(n) < n
f(3) = 1;//0,1,2,3  f(n) < n
...按照这样的话其实f(n)=n最小的是0，其次是1，如果是>1,则要算法实现了

还是不知道什么意思，用个循环从零开始找？

用来用去，还是C好。
小弟献丑了/*
* 1:编写一个程序,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1;
* 2:编写一个程序,得出最先使得 f(n)等于n的整数n;
*/
#include <stdio.h>
int f(int n){
        int times=0;               /*记录数字中出现1的次数*/
        if(n==0)return 0;
        if(n==1)return 1;
        while(n!=0)
        {
                if((n%10)==1)
                {
                        times++;                }
                n/=10;
        }
        return times;
}int main(void){
    int i;
    int times=0;
    int n=11;
    for(i=1;i<=n;i++){
       times+=f(i);
    }
    printf("%d",times);
    getche();
     return 0;
}

第一题
  public long calcOnes(final long n){
    long count=0,theN=n;
    String n_str=Long.toString(n);
    int length=n_str.length();
    if(length==1){
      if(n>=1){
        count=1;
      }
      return count;
    }else{
      char[] n_char_array=n_str.toCharArray();
      char first_num_char=n_char_array[0];
      if(first_num_char>'1'){
        count = (int) Math.pow(10, length - 1);
        theN=n-(first_num_char-'0')*count;
        count=count+calcOnes(theN)+(first_num_char-'1')*calcOnes(count-1);
      }else if(first_num_char=='1'){
        theN=n-(first_num_char-'0')*(int)Math.pow(10, length - 1);
        count=theN+1;
        if(theN==0)theN=(int)Math.pow(10, length - 1)-1;
        count=count+calcOnes(theN);
      }
      return count;
    }
  }

weinickli(weili) 和几个人提供的算法都是遍历从1到n的所有数字，然后通过字符串拆分或者其他方式拆分来比较每一位来统计1的个数的。
这种算法是最慢的，道理和穷举一个样。Google的面试题显然不是考这样的程序怎么编写，而是考如何构造一个好的算法来编写。我的算法已经贴出来了，估计大家要仔细看才能明白，也可能我的表达有点问题。
我认为自己的算法是正确的，而且时间复杂度也是足够好的，不过更希望有高人能写出更好的算法。

to: viking2001(Viking)
你的算法应该是正确的，其实我们的算法都是类似的，还有billpin() 的算法，应该思路也是一样的，具体实现起来可能有些小差别，基本思路都一样，复杂度都是logN，也就是和数字的位数相关，而不是数字的大小，当数字很大时，效率提高是非常明显的。

同意viking2001的算法，应该是比较快的

第2个题的意思就是:
f(1) = 1;
f(n) = n;
求n

weinickli(weili) 和几个人提供的算法都是遍历从1到n的所有数字，然后通过字符串拆分或者其他方式拆分来比较每一位来统计1的个数的。
这种算法是最慢的，道理和穷举一个样。Google的面试题显然不是考这样的程序怎么编写，而是考如何构造一个好的算法来编写。我的算法已经贴出来了，估计大家要仔细看才能明白，也可能我的表达有点问题。
我认为自己的算法是正确的，而且时间复杂度也是足够好的，不过更希望有高人能写出更好的算法。
------------------------------------
呵呵很显然你可能还没看懂我的算法~~我是遍历的位数~~并非每一个数~~~~~
也就是说一个五位数我只循还了5次而不是10^5次
试想一下每一位上出现‘1’的规律就应该知道我的算法了~~

结果是f(199981) = 199981
java下，8秒//test.java
public class test{
public static void main( String args[] ){
long start = System.currentTimeMillis();
int i = 1;
int cnt = 0;
while( true ){
cnt = getOne( i ) + cnt;
p.println( "f(" + i + ") = " + cnt );
if( i == cnt && i != 1 ){
break;
}
i++;
}
long time = System.currentTimeMillis() - start;
System.out.println( "use " + time/1000 + " seconds");
}

//get the number of "1" exist between 1 and n
static int f( int n ){
int res = 0;
if( n <= 0 ){
return res;
}
for( int i = 1; i <= n; i++ ){
res += getOne( i );
}
return res;
}

//get the number of "1" exist in n
static int getOne( int n ){
int res = 0;
if( n <= 0 ){
return res;
}
while( n >= 10){
if( n%10 == 1 ){
res++;
}
n = n/10;
}
if( 1 == n ){
res++;
}
return res;
}
}

犯傻了，去掉print语句，1秒都不要

google的题肯定是考算法。
viking2001(Viking)兄正解，不可能有常数时间复杂度算法吧，这应该就是最优解。

weinickli(weili) ( ) 信誉：100 //get the number of "1" exist in n
static int getOne( int n )
你的GetOne算法有问题，不能获得N以下包括的所有1的个数。测试了一下getOne（13）= 1，正确答案应该是6

int f(int n)
        {
            int count = 0;
            int num = 1;
            int div = 1;
            while (n >= div)
            {
                count += n / (div * 10) * div;
                if (n / div % 10 > num) count += div;
                else if (n / div % 10 == num) count += n % div + 1;
                div *= 10;
            }
            return count;
        }

int getMin(){
            int n = 2;
            int i = n;
            while (n != f(n))
            {
                while (n > f(i))
                {
                    i += (n-f(i)) / length(i) + 1;
                }
                n = i;
            }
            return n;
}int length(int n)
        {
            int i = 0;
            while (n > 0)
            {
                n /= 10;
                i++;
            }
            return i;
        }
================
有个问题就是，很难证明确实存在这么一个值n，使得n=f(n)，所以这个方法只是有可能能得到最小的值。如果这个方法得出了结果，那可以保证这个结果肯定就是最小的n。
实际上确实得出了结果，就是199981。

believefym(暮色，miss，迷失，miss)
怎么这么多人看不懂第二题
f(0) = 0;//0        f(n) = n
f(1) = 1;//0,1      f(n) = n
f(2) = 1;//0,1,2    f(n) < n
f(3) = 1;//0,1,2,3  f(n) < n
...按照这样的话其实f(n)=n最小的是0，其次是1，如果是>1,则要算法实现了
f(0) = 1;//0        f(n) < n

第一题，我的方法比较笨，望指点
import java.io.*;
class Google_test
{
public static void main(String[] args)
throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str;
int n=0;
int time=0;
System.out.println("Please enter a number.");
str=br.readLine();
try{
n=Integer.parseInt(str);
}
catch(NumberFormatException exc){
System.out.println("请正确输入数字.");
}

for(int i=1;i<=n;i++)
{
int x;
for(x=1;(i/(10*x))!=0;)
x++;
for(int j=0;j<=x;j++)
{
if((i/(int)(Math.pow(10,j)))%10==1)
time++;
}
}
System.out.println("从1到"+n+"之间1出现的次数是"+time);
}
}

第2题
class GoogleTest2
{
public static void main(String[] args)
{
int time=0;
one: for(int i=1;i<9;i++)
{
int x;
for(x=1;(i/(10*x))!=0;)
x++;
for(int j=0;j<=x;j++)
{
if((i/(int)(Math.pow(10,j)))%10==1)
time++;
}
System.out.println(i+" "+time);
if(i==time)
{
System.out.println("f("+i+")="+time);
break one;
}
}
}

上面更正下如下
class GoogleTest2
{
public static void main(String[] args)
{
int time=0;
one: for(int i=1;;i++)
{
int x;
for(x=1;(i/(10*x))!=0;)
x++;
for(int j=0;j<=x;j++)
{
if((i/(int)(Math.pow(10,j)))%10==1)
time++;
}
System.out.println(i+" "+time);
if(i==time)
{
System.out.println("f("+i+")="+time);
break one;
}
}
}

改正一下，第二题可以只用一个循环，用2个循环就多此一举了。int getMin(){
            int n = 2;
            int i = n;
            while (n != f(n))
            {
                  n += (n-f(n)) / length(n) + 1;

            }
            return n;
}int length(int n)
        {
            int i = 0;
            while (n > 0)
            {
                n /= 10;
                i++;
            }
            return i;
        }

yjukh(小虫) ( ) 信誉：100  2006-04-27 17:28:00  得分: 0

   都喜欢在这种小问题上纠缠


所有问题都是小问题。

这种贴看了过后觉得CSDN还是大有希望的

调试易

一道GOOGLE的面视题

解决方案 »