一道google的面试题。

Question

问题：编写一个程序,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1;
编写一个程序,得出最先使得 f(n)等于n的整数n;
下面是我自己编写的程序，不知道哪位有没有更好，更高效的方法。。
public static void main(String[] args)
    {
        long n = 200000;
        int count = 1;        for (int i = 1; i <= n; i++)
        {
            int l = (int) (Math.log10(i) + 1);//n的位数
            long s = (long) Math.pow(10, l - 1);//10的n次幂
            for (int j = 1; j <= l - 1; j++)
            {
                if (i % s == 1)
                {
                    count++;
                }
            }
            for (int k = 1; k <= l - 1; k++)
            {
                if (i / s == 1)
                {
                    count++;
                }
            }
            if (count == i)
            {
                System.out.println("count = " + count + ", number = " + i);
            }
        }
答案是：
count = 1, number = 1
count = 176, number = 176
count = 224, number = 224
count = 1378, number = 1378
count = 3247, number = 3247
count = 43281, number = 43281

Answer 1

可以将数字转换成string，然后用char比较会简单一点

Answer 2

首先需要总结4楼所说的公式，其次要证明在n之前没有一个数使f(x)=x

Answer 3

int total = 0;
for (int i = 1; i < 200000; i++) {
int n = i;
while (n > 0) {
if (n % 10 == 1)
total++;
n /= 10;
}
if (i == total)
System.out.println("i = " + i + ", total = " + total);
}输出结果：
i = 1, total = 1
i = 199981, total = 199981
i = 199982, total = 199982
i = 199983, total = 199983
i = 199984, total = 199984
i = 199985, total = 199985
i = 199986, total = 199986
i = 199987, total = 199987
i = 199988, total = 199988
i = 199989, total = 199989
i = 199990, total = 199990lz的程序貌似有问题啊………………

Answer 4

只输出一个数那么就在输出后break就好了啊

Answer 5

LZ的确实有问题，我用了另一种办法，不过还是楼上的兄弟写得效率高的多：public int f(int n){
int count=0;
for(int i=1;i<=n;i++){
String s=String.valueOf(i);
int fromIndex=-1;
while((fromIndex=s.indexOf("1",fromIndex+1))!=-1){
count++;
}
}
return count;
}

Answer 6

    (x%10=1)
    (x%100=1)
    (x%1000=1)……

Answer 7

public static int count1(int number)
        {
            int value = 0;
            if (number > 0)
            {
                int mod = number % 10;
                value = (number /= 10) + ((mod + 15) >> 4);
                for (int nextMod, mul = 10; number > 0; mul = (mul << 3) + (mul << 1))
                {
                    nextMod = number % 10;
                    value += (number /= 10) * mul;
                    if (nextMod > 1) value += mul;
                    else if (nextMod == 1) value += mod + 1;
                    mod += nextMod * mul;
                }
            }
            return value;
        }

Answer 8

得出最先使得 f(n)等于n的整数n
这个必然就一个答案1啊用得着程序吗？

Answer 9

public static int getOneCount(int n) {
int count = 0;
for (int i = 0; i <= n; i++) {
String str = String.valueOf(i);
if (str.contains("1")) {
count++;
}
}
return count;
}
不难啊

Answer 10

我的代码public class test
{
public static void main(String []args)
{
func f1=new func();
System.out.println(f1.f(9));
System.out.println(f1.f(12));
System.out.println(f1.f(13));
}
}
class func
{
int f(int n)
{
int i,j,len,sum=0;
String s;
char [] c=new char[10];
for(i=1;i<=n;i++)
{
s=String.valueOf(i);
len=s.length();
c=s.toCharArray();
for(j=0;j<len;j++)
if(c[j]=='1')
sum++;
}
return sum;
}
}运行结果

Answer 11

我对19楼的代码整理后如下。int total = 0;
        for (int i = 1; i <= 200000000; i++)
        {
            String x = String.valueOf(i);
            char[] s = x.toCharArray();
            for (int j = 0; j < s.length; j++)
            {
                char c = s[j];
                if (c == '1')
                {
                    total++;
                }
            }
            if(total == i)
            {
                System.out.println("count = " + total + ", i = " + i);
            }
        }在我电脑上当i＝200000000时运行
     19楼用时61418ms
     7楼的用时84712ms
19楼的更高效，足足快了20秒，不明白哪里快了20秒。。期待更高效的算法。

Answer 12

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public  class  Num1
{
public static void main(String []args)
{
System.out.println("请输入数字N：");
try
{
BufferedReader bufread=new BufferedReader(new InputStreamReader(System.in));
String input=bufread.readLine();
bufread.close();
int result=Integer.parseInt(input);
     StringBuffer sf=new StringBuffer();
     for(int i=1;i<=result;i++)
    {
   sf.append(i);
     }
    int num1=0;
   for(int i=0;i<sf.length();i++)
   {
 if(sf.charAt(i)=='1')
num1++;
   }
  System.out.println("the results is："+num1);

}
catch(IOException e)
{
e.printStackTrace();
}
} 

}

Answer 13

刚看了一下这本书,书上的代码如下:int n = 2000000000;
int iCount = 0;
int iFactor = 1;
int iLowerNum = 0;
int iCurrNum = 0;
int iHigherNum = 0;
while (n / iFactor != 0) {
iLowerNum = n - (n / iFactor) * iFactor;
iCurrNum = (n / iFactor) % 10;
iHigherNum = n / (iFactor * 10);
switch (iCurrNum) {
case 0:
iCount += iHigherNum * iFactor;
case 1:
iCount += iHigherNum * iFactor + iLowerNum + 1;
break;
default:
iCount +=(iHigherNum+1)*iFactor;
break;
}
iFactor *=10;
}
System.out.println("count = " + iCount);运行效率比7楼和19楼的要快40000到50000倍.
不知道大家还有没有更优,更快的算法.

Answer 14

package project;
public class Count1Num{
public static void main(String[] args) 
{ 
int total = 0;
for (long i = 1; i < 2000000000; i++) {
    long n = i;
    while (n > 0) {
        if (n % 10 == 1)
            total++;
        n /= 10;
    }
    if (i == total)
        System.out.println("i = " + i + ", total = " + total);
}
     System.out.println(total);
}
}i < 2000000000 你的电脑性能算不！

Answer 15

public class ContainNumber { /**
 * @param args
 */
public static void main(String[] args) {
ContainNumber number = new ContainNumber();
System.out.println(number.search(1909090));
}
public int search(int _n)      
{      
    int N = _n/10;      
    int a1 = _n%10,a2;      
    int x = 1;   
    int ten = 10;   
    int c = a1 == 0?0:1;   
    while(N > 0)      
    {      
        a2 = N%10;   
        if(a2 == 0);   
        else if(a2 == 1)c = a1 + 1 + x + c;      
        else c = a2*x + c + ten;      
        a1 = 10*a1 + a2;        
        N /=10;      
        x = 10*x + ten;   
        ten *= 10;
    }      
    return c;      
}
}
时间复杂度O（lgn）