[算法]Google的面试题

wangyb

this is a very simple question.
num=13; echo $(($(seq -s',' $num | sed s/[0,2-9]//g|wc -m) - 1))

tonny.cun

高深........................

sxzzsf

[PHP]
#include <stdio.h>

int base[10];                                                // 10
int data[10];

int x10(int m)
{
        int i = 0;
        int sum = 1;

        for (i = 0; i < m; i++)
                sum *= 10;
        return sum;
}

int calc(int m)
{
        if (m == 0) {
                base[0] = 1;
                return 1;
        }
        base[m] = 10 * calc(m - 1) + x10(m);
        return base[m];
}

int main()
{
        int n, m = 0;
        int i, j, sum = 0;

        scanf("%d", &n);

        while (n / 10) {
                data[m] = n - n / 10 * 10;
                m++;
                n /= 10;
        }

        if (m >= 10) {
                printf("Overflow!\n");
                return -1;
        }

        data[m++] = n;

        calc(m);

        n = 0;

        for (i = m - 1; i > 0; i--) {
                n = data + n * 10;                // rebuild n

                sum += data * base[i - 1];                // get base sum value

                if (data == 1) {                // get other sum
                        j = i;
                        while (j-- > 0) {
                                sum += data[j] * x10(j);                // + 1;
                        }
                        sum++;
                }
                else if (data)
                        sum += x10(i);
        }

        if (data[0] != 0)
                sum++;

        printf("%d - %d\n", n, sum);
        return 0;
}
[/PHP]

lucifer

用C的bitfield加上强制类型转换很简单。考虑到不同平台移植的话，用条件编译应该也足够了。

jrfei01

c新手，写个最基础的

#include "stdio.h"

main()
{
  long i,a,sum;
  long n=1111111110;
  sum=0;
  printf("%d\n",sizeof(a));
  for(i=1;i<=n;i++)
  {
    a=i;
    while(a>0)
    {
      if(a%10==1)
        sum++;
      a=a/10;
    }
    if(i==sum)
      printf("f(%d)=%d\n",i,sum);
  }
}

yongjian

个人感觉用计算1的位子或是转成字符计算1的位子有弊端。如果这么问：给出任意的一个数，求从1到这个数中1的含量？枚举算法将比较吃亏。我的算法有点不一样，我是用自己推的公式算的。对于上面的问题，我的算法复杂度是O(1)，而枚举仍是O(n).

1. 
   
2. def countOne(num):
   
3.   count = 0
   
4.   prevnum = 0
   
5.   bits = []
   
6.   def _getbits(num):
   
7.     bits.append(num%10)
   
8.     n = num/10
   
9.     if n > 10:
   
10.       _getbits(n)
    
11.     else:
    
12.       if n != 0:
    
13.         bits.append(n)
    
14.   _getbits(num)
    
15.   for i, j in enumerate(bits):
    
16.     if i == 0:
    
17.       if j > 0:
    
18.         count += 1
    
19.     else:
    
20.       if j == 1:
    
21.         count += (prevnum + 1) + j*(i*pow(10, (i-1)))
    
22.       elif j > 1:
    
23.         count += pow(10, i) + j*(i*pow(10, (i-1)))
    
24.     prevnum += j*pow(10, i)
    
25.   return count
    

复制代码

huayanghao

;first, the recursive way, redundant work, very slow
(define (fr n)
  (define (c n)
    (cond ((< n 1) 0)
          (else (+ (c (/ n 10))
                   (if (= (remainder (floor n) 10) 1)
                       1
                       0)))))
  (if (< n 10)
      1
      (+ (fr (- n 1)) (c n))))
;second the tail-recursive way (the iterative way)
;much more efficient
(define (ff n)
  (define (c n result)
    (cond ((< n 1) result)
          (else (let ((delta (remainder (floor n) 10)))
                     (c (/ n 10) (+ result (if (= delta 1) 1 0)   ))))))
  (define (cc n) (c n 0))
  (define (f n s)
    (if (< n 10)
        s
        (f (- n 1) (+ s (cc n)))))
  (f n 1))
;But, still, the above way is not the best way
;Here is a more efficient way to do it.
;With a little analysis of this problem, it can be seen that each bit will
;contribute 10% of 1, well roughly.
;take the number "abcd", if d > 1, then there's "ab(c+1)0"*10% 1 in the least
;significant bit. if c > 1, then there's "a(b+1)00"*10% 1 in the second least
;significant bit, so on and so forth.
;But, whenever there is digit "1", it's a special case and need to be delt with
;serparately.
(define (the-best-f n s c)
  (let* ((rest (floor (/ n (expt 10 c))))
        (lsb (remainder rest 10)))
    (if (< n (expt 10 c))
        s
        (the-best-f n
                    (cond ((= lsb 0) (+ s (* rest (expt 10 (- c 1)))))
                          ((= lsb 1) (+ 1 s (remainder n (expt 10 c))
                                          (* 0.1 (floor (/ rest 10)) (expt 10 (1+ c)))))
                          (else (+ s (* 0.1 (+ 1 (floor (/ rest 10))) (expt 10 (1+ c))))))
                    (1+ c)))))
(define (best-ff n)
  (the-best-f n 0 0))
(define (findit n)
  (if (not (= (best-ff n) n))
      (findit (+ 1 n))
      n))
-------------------------------
没人用scheme, 我就给一个用scheme的好了

lshan_2008

刚刚开始学习java编程,写了段代码，感觉很快的，望高手指导。
由于我不是学计算机的，对算法这个术语不了解，大家不要笑我！
  public static void main(String[] args)
    {
        int num=0;
        for(int i=0;;i++)
        {
            String tmp=Integer.toString(i);
            for(int j=0;j<tmp.length();j++)                           
                if(tmp.charAt(j)=='1')                                   
                    num++;
            if(num==i&&num>1)
                break;
        }
        System.out.println(num);
    }

ziwarlee

Post by xiaoarly;1584600
牛，这种题目，没几个人能够做得出来

数学系专业的，做这种题目，还好一点，计算机系，不适合做这种题目。

那google招聘的都是学数学的，而不是招计算机的学生嘛

iDay

Post by frank55555;1768581
怎么大家把這個題目做的這么復雜呀?我不會編程.但我想也不用這么算呀?這不是很累.你以為計算機這樣工作不累嗎?我認為這個很好算嗎?比如說2345有我少個?答案是234*1+235*1+245*1+345*1=1059個.用口算就可以算出來呀?個位不等于0就去掉個位+1(等于0則減10再去掉個位+1).再加上十位不等于0去掉十位(十位等于0則減100再去掉十位+1).............總共加起來就可以了.

比如:5203----------(520+1)*1+(513+1)*1+(503+1)*1+(203+1)*1=1743
       1003---------(100+1)*1+(93+1)*1+(3+1)*1+(3+1)*1=203
       13-----------(1+1)*1+(3+1)*1=6

这个是咋归纳出来滴，讲一下思路好哇？