[算法]Google的面试题

brotherhao

看一看后再说

bingbuidea

累计除以10
余数或者商为1 ,++

ballpen

#include <iostream>
using namespace std;

int getMaxBate(int i)
{
   int step = 1;
   int tmp = i;
   for(;(tmp/step)>=10;step =step *10);
   return step;
}
int f(int i)
{
   if ((i<10) && (i>0))
      return 1;
   else if (i<=0)
      return 0;

   int step = getMaxBate(i);
   int hcount = f(i/step);
   int lcount = f(step-1);
   int leftCount =  f(i%step);

   if ((i/step) == 1)
   {
       hcount =  (i+1)%step;
       if (hcount ==0) hcount = step;

       return hcount + (lcount *(i/step)+ leftCount);
   }
   else
   {
       return hcount*step+ (lcount *(i/step)+ leftCount);
   }
}


int oneOf(int n)
{
int result =0;
int tmp = n;

    for(;tmp!=0;)
    {
      if ((tmp %10) == 1 )
         result ++;
      tmp = tmp/10;
    }

return result;
}
int f1(int n)
{
int result = 0 ;
   for (int i=0;i<=n;i++)
   {
     result = result + oneOf(i);
   }
return result;
}

int test(int i)
{
   for(i=0;i<10000;i++)
   {
     if (f(i)!=f1(i))
     {
      cout <<"num:"<<i<<endl;
      cout <<"f1("<<i<<"):"<<f1(i)<<" !=f("<<i<<"):"<<f(i)<<endl;
      break;
     }
   }
}
int main()
{
   int i;

   test(10000);
   cout <<"please enter a  number"<<endl;
   cin >>i;
   cout <<"the result is :"<<f(i)<<endl;

   cout <<"the result is :"<<f1(i)<<endl;
   return 0;
}

ballpen

#include <iostream>
using namespace std;

int getMaxBate(int i)
{
   int step = 1;
   int tmp = i;
   for(;(tmp/step)>=10;step =step *10);
   return step;
}
int f(int i)
{
   if ((i<10) && (i>0))
      return 1;
   else if (i<=0)
      return 0;

   int step = getMaxBate(i);
   int hcount = f(i/step);
   int lcount = f(step-1);
   int leftCount =  f(i%step);

   if ((i/step) == 1)
   {
       hcount =  (i+1)%step;
       if (hcount ==0) hcount = step;

       return hcount + (lcount *(i/step)+ leftCount);
   }
   else
   {
       return hcount*step+ (lcount *(i/step)+ leftCount);
   }
}


int oneOf(int n)
{
int result =0;
int tmp = n;

    for(;tmp!=0;)
    {
      if ((tmp %10) == 1 )
         result ++;
      tmp = tmp/10;
    }

return result;
}
int f1(int n)
{
int result = 0 ;
   for (int i=0;i<=n;i++)
   {
     result = result + oneOf(i);
   }
return result;
}

int main()
{
   int i;

   cout <<"please enter a  number"<<endl;
   cin >>i;
   cout <<"the result is :"<<f(i)<<endl;

   cout <<"the result is :"<<f1(i)<<endl;
   return 0;
}

ballpen

两个函数效率相差很大一个是log10(n)
一个是O(n) = n*log10(n);

FlyToMoon

有点意思，我给出了一个递归算法，请参考。

#include <iostream>

using namespace std;

int countOne(int n) {
        if(n < 10)
                return 1;
        int lft = n;
        int tens = 1;
        do {
                lft = lft / 10;
                tens = tens * 10;
        } while(lft > 10);
        if(lft != 1)
                return lft * countOne(tens - 1)  + countOne(n - lft * tens) + tens;
        else
                return countOne(tens -1) + countOne(n - tens) + n - tens + 1;

}


int main()
{
        int n;
        cout << "lease input the number:";
        cin >> n;
        cout << "the number of ones is:" << countOne(n) << endl;
        return 0;
}

FlyToMoon

递归算法：
#include <iostream>

using namespace std;

int countOne(int n) {
        if(n < 10)
                return 1;
        int lft = n;
        int tens = 1;
        do {
                lft = lft / 10;
                tens = tens * 10;
        } while(lft > 10);
        if(lft != 1)
                return lft * countOne(tens - 1)  + countOne(n - lft * tens) + tens;
        else
                return countOne(tens -1) + countOne(n - tens) + n - tens + 1;

}


int main()
{
        int n;
        cout << "lease input the number:";
        cin >> n;
        cout << "the number of ones is:" << countOne(n) << endl;
        return 0;
}

leung252

int fun( int n )
{
    char str[64];
    int num = 0;
    int i = 0;
    int j = 0;          
   
    for ( i=1; i<=n; i++)
    {
        memset( str, 0x00, sizeof(str) );
        snprintf( str, sizeof(str), "%d", i );
               
        for ( j=0; j<strlen(str); j++ )
        {
            if ( '1' == str[j] )
            {
                num++;
            }              
        }
    }
   
    return num;       
}

leung252

感觉还是转成字符串后好一点,只需考虑长度,而不需考虑加减乘除问题

cqpwx

1. /*Consider a function which, for a given whole number n,
   
2. returns the number of ones required when writing out all
   
3. numbers between 0 and n. For example, f(13)=6. Notice th
   
4. -at f(1)=1.
   
5. What is the next largest n such that f(n)=n?  
   
6. */
   
7. 
   
8. public class Google{
   
9.         public static void main(String[] args){
   
10.                 for(int n=0;n<=1111111110;n++){
    
11.                         String txt=Int.toString(n);
    
12.                         Byte[] byt=txt.toByte();
    
13.                         int result=0;
    
14.                         for(int i=0;i<byt.length();i++){
    
15.                                 if(byt[i]='1'){
    
16.                                         result+=1;
    
17.                                 }
    
18.                         }
    
19.                         System.out.println("When n="+n+",f(n)="+result);
    
20.                 }
    
21.         }
    
22. }

复制代码

这台电脑没有jdk，等下javac看看，好像类型转换哪儿有点问题