184 腾讯 1、怎么最快找出出现过最多次的 QQ 号 2、求根号2的值，指定小数位

时间：2023-02-20 07:59:20


腾讯 
1.服务器内存 1G，有一个 2G 的文件，里面每行存着一个 QQ 号（5-10 位数），
怎么最快找出出现过最多次的 QQ 号。（此题与稍后下文的第 14 题重复，思路参考请
见下文第 14 题）。
       首先你要注意到，数据存在服务器，存储不了（内存存不了），要想办法统计每一个qq出现的次数。
比如，因为内存是1g，首先  你用hash的方法，把qq分配到10个（这个数字可以变动，比较）文件（在硬盘中）。
相同的qq肯定在同一个文件中，然后对每一个文件，只要保证每一个文件少于1g的内存，
统计每个 qq 的次数，可以使用 hash_map(qq, qq_count)实现。
然后，记录每个文件的最大访问次数的qq，最后，从10个文件中找出一个最大，即为所有的最大。

那若面试官问有没有更高效率的解法之类的?
这时，你可以优化一下，但是这个速度很快，hash函数，速度很快，他肯定会问，你如何设计，用bitmap 也行。

2.如何求根号2的值，并且按照我的需要列出指定小数位，比如根号2是1.141，
我要列出1位小数就是1.1，2位就是1.14，1000位就是1.141......等； 

方法1：二分逼近 ，解方程，用折中法或者直线法逼近
但是这种达不到很高的位数 
方法2：用微积分函数展开，即将x^(1/2)展开

解：√(1+x)=(1+x)^(1/2)(按泰勒公式展开) 
=1+(1/2)x+(1/2)[(1/2)-1]x^2)/2!+(1/2)[(1/2)-1][(1/2)-2]x^3)/3!+…+(1/2)[(1/2)-1][(1/2)-2]…[(1/2)-n+1](x^n)/n!+o(x^n) 
=1+(x/2)-(x²/8)+(x³/16)-…+[(-1)^(n-1)](2n-3)!!(x^n)/(2n)!! +o(x^n) 

(2n)!!=(2n)×(2n-2)×(2n-4)×…×4×2，即隔一个相乘，一直乘到能取到的最小正整数。 
则√2=(1+1)^(1/2) 
=1+(1/2)-(1/8)+(1/16)-…+[(-1)^(n-1)](2n-3)!!/(2n)!!+o(1) 
如按前四项展开，则√2≈1+(1/2)-(1/8)+(1/16)=1.4375 
十分位是精确值，取的项越多，近似程度越高。

//方法1： 

#include<iostream>
#include<stdio.h>
#include<math.h> 
#include<stdlib.h>
#include<string.h>
using namespace std; 

double sqrtN(int n, int m)
{
    double left=0;
    double right=n*1.0;
    double err=1,mid;
    for(int i=0;i<m;i++)
        err*=0.1;

    while(fabs(left-right)>err)
    {
        mid=(left+right)/2;
        if(mid*mid>(double)n)
            right=mid;
        else if(mid*mid<(double)n)
            left=mid;
    }
    return left;
}

int main()
{
    double res=sqrtN(2,8);
    printf("%.8lf\n",res);
    return 0; 
}
标签：

相关文章