google的一道JAVA面试题 求大虾帮帮

Question

题目：
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. 
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? 
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？这是小弟写的程序：public class Test12 {
public static void main(String[] args) {
int n = 2;
while(f(n) != n) {
++n;
}
System.out.println(n);
}

public static int f(int x) {
int sum =0;
for(int i=0; i<=x; i++) {
String s = Integer.toString(i);
for(int j=0; j<s.length(); j++) {
char c = s.charAt(j);
if(c == '1') {
++sum;
}
}

}
return sum;
}}我运行起来就一直没有显示结果了
不知是不是进入死循环了
请大家帮助解决一下 
小弟先在这里谢谢大家了另外谁有更好更高效 的方法写写出来让小弟学习一下啊
谢谢了！！

Answer 1

while(f(n) != n) {
++n;
} 
只要不等于就一直执行下去，肯定死循环了感觉应该有个限制，好像超过10以后就不可能再有f(n)=n了把，而且数字越大越不可能，最大的值可能就是n=1
没仔细想，大家发表下意见

Answer 2

要找的数字是 199981//FindN.java
/*
题目： 
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. 
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? 
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？
*/
public class FindN
{
public static void main(String[] args)
{
//System.out.println("-_-");
//todo
int n = 2;//从2开始找
int sum = 1;//f(1)=f(2)=f(3)=1
boolean ok = false;
while ((!ok)&&(n<1000000001))
{
n++;
//算数字n中包含的数码1的个数
String s = Integer.toString(n);
for(int i = 0;i < s.length();i++)
{
if (s.charAt(i) == '1')
{
sum++;
}
}
ok = (sum == n);
}
System.out.println("the number:" + n);
}
}

Answer 3

补充一下，题目中Consider a function我的理解不是说要写出这样一个函数，而是说在数学中有这样一个函数。所以用递推的方法f(n)=f(n-1)+g(n)，其中g(n)表示数字n中包含的数码1的个书。我业余爱好，刚开始自学，中间一段Integer.toString()还没学到，抄楼上的，呵呵，还有charAt也是抄楼上的。

Answer 4

private static int f(int n)
{
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;
break;
case 1:
iCount += iHigherNum * iFactor + iLowerNum + 1;
break;
default:
iCount += (iHigherNum + 1) * iFactor;
break;
} iFactor *= 10;
} return iCount;
}
你的复杂度是O(N*log2N)
而这个的复杂度是O(ln(n)/ln(10)+1),更好一些

Answer 5

http://topic.csdn.net/u/20091026/23/7d034ebe-dbd4-4244-80cf-bba21d061bd0.html

Answer 6

public class test214 { /**
 * @param args
 */
static int  sum=0;

public static void main(String[] args) {

int n=13;
count(n);
System.out.println(sum);
} private static void count(int n) {
if(n>0){
String nString=String.valueOf(n);
char[] chr=nString.toCharArray();
for(int i=0;i<chr.length;i++)
{
if('1'==chr[i])
sum++;
}
n--;
count(n);
} }}

Answer 7

package zgq;
/**
 * 有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,
 * 现在f(1)=1,问下一个最大的f(n)=n的n是什么？
 * @author Administrator
 *
 */
public class Test12 {
public static void main(String[] args) {
int n = 2;
int res=1;
while((getOnly(n)+res) != n) {
res+=getOnly(n);
    ++n;
}
System.out.println(n);
}
    static String retStr(int num){
    
     String s=num+"";
     return s;
    }
    
    static int getOnly(int num){
     int number=0;
     int len=retStr(num).length();
     String s=retStr(num);
     if(len!=0){
     for(int i=0;i<len;i++){
     char a=s.charAt(i);
     if(a=='1'){
     number++;
     }
     }
     }return number;
    }
} 

Answer 8

这样简洁些
public class Test12 {
public static void main(String[] args) {
int n = 2;
int res=1;
while((getOnly(n)+res) != n) {
res+=getOnly(n);
    ++n;
}
System.out.println(n);
}    
    static int getOnly(int num){
     int number=0;
     String s=num+"";
     int len=s.length();
     if(len!=0){
     for(int i=0;i<len;i++){
     char a=s.charAt(i);
     if(a=='1'){
     number++;
     }
     }
     }return number;
    }
} 

Answer 9

public static int f(int x) 
你没给x赋值就对他进行赋值，可不一直循环下去被，给它赋值你试试，应该就可以了

Answer 10

没有错误，只是效率不怎么样
你可以用print的方式去看n和f(n)的变化，其实是一只在进行的，但是效率不佳，所以很慢

Answer 11

你的程序逻辑没错，只是太耗时间了。要不你改成这样看看
        while(f(n) != n) {
System.out.println(n);
        ++n;
      }
  System.out.println(n+"finally");
}

Answer 12

public static void main(String[] args) {
int[][] aa = { { 68, 36, 22 }, { 59, 77, 39 }, { 81, 20, 17 } };
int [][]pos = new int[3][3];
for(int i=0;i<aa.length;i++){
for(int j=0;j<3;j++){
pos[i][j] = 1;
}
}

//找排序后的位置位置
for(int i=0;i<3;i++){

for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
if( k != j && aa[k][i]<aa[j][i]){
pos[j][i]++;
}
}
}

}

for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
System.out.print(pos[i][j]+"");
System.out.println();
}


}

Answer 13

这个题貌似， 考的是数学知识啦， 举个例子 ABCDEF 每个字母代表一个数字， 主要就是判断每个字母与1的比较，给你举个例子吧， 如果F>=1那么 这个数字 各位出现的1 则为 ABCDE + 1;
如果是小于1则ABCDE ，
如E 则为十位 每出现一个1则多了10个1；
逐次考虑我觉得这样子，简化运行的效率了， 因为每次执行的知识循环数字的位数，剩下的就是与1的比较了！ 

Answer 14

    int find()
    {
        int j =3;
        int f_pre = 0;
        int g_j =0;
        f_pre = f(2);
        g_j = g(3);
        while(j!=f_pre+g_j)
        {
            f_pre +=g_j;
            ++j;
            g_j = g(j);
        }
        return j;
    }
分析下复杂度：
1，g()函数 取决于位数 ：整数类型 24亿或者40多亿 <=10位 
2，find()函数 跟n的大小有关，迭代n次。（n为要找的数）
3，总共 上界10*n ，为log(n)
4，用c的话 瞬间的事情(java通用)
....基于算法中常用的假设，要求f(n),则基于假设f(n-1)已知，利用前此跌打，减小复杂度
边界还望拍砖。