今天进行了人生中的第一次面试，就遇到了地狱难度的头条后端，面完自我感觉超级差，但是还是过了，
面完把两道问题重新解决了一下，做做经验总结吧,毕竟面试无论结果都是对自己一次很好的查漏补缺~

第一道 经典到不能再经典的 TOPK

TOPK 比较暴力的方法就不写了
主要我说了两种方法，一种是利用堆排序，建立一个大小为k的小顶堆，以及一个length-k的大顶堆，然后循环取出大顶堆的堆头与小顶堆的堆头比较，
如果比小顶堆的堆头大，则覆盖小顶堆堆头，然后再把两个堆进行siftdown直到大顶堆遍历完。此时的小顶堆堆头就是TOPK，整个小顶堆就是前K大。

堆排思想

private static int getTopKByHeap(int[] input,int k){
    //获得最小堆
    int len = input.length;
    //复制备份进新数组 小顶堆
    //当然你可以不用复制沿用旧数组，
    //只是在去除时就要判断堆顶的位置是在哪里
    int [] newInput = new int[k];
    for(int i = 0;i<k;i++){
        newInput[i] = input[i];
    }
    //复制备份进新数组 大顶堆
    int [] newInput2 = new int[len-k];
    for(int i = 0;i<len-k;i++){
        newInput2[i] = input[i+k];
    }
    //小顶堆初始化
    heapify(newInput,0,k-1,false);
    //大顶堆初始化
    heapify(newInput2,k,len-1,true);
    //遍历大顶堆 进行比较
    for(int i = 0;i<len-k;i++){
        int temp = take(newInput2,true);
        if(newInput[0]<temp){
            newInput[0] = temp;
            siftDown(newInput,0,temp,false);
        }
    }
    //返回小顶堆头
    return newInput[0];
}

private static void heapify(int [] input,int beginIndex,int endIndex,boolean isBigHeap){
    //(endIndex-beginIndex+1>>>1)-1就是拿出所有非叶节点的索引进行siftDown
    for(int i = ((endIndex-beginIndex+1)>>>1)-1;i>=0;i--){
        siftDown(input,i,input[i],isBigHeap);
    }
}

//其实堆排我是学习了优先级队列的源码实现的
private static void siftDown(int [] input,int i,int e,boolean isBigHeap) {
    int len = input.length;
    int half = len >> 1;
    while (i < half) {
        //找出左子节点的索引
        int child = (i << 1) + 1;
        //找出右子节点的索引
        int right = child + 1;
        //小顶堆大顶堆不同条件
        if (isBigHeap) {
            //大顶堆是要找出子节点的最大值，将其索引赋予child
            if (right < len && input[child] < input[right]) {
                child = right;
            }
            //遇到最大子节点都比自己小的，就可以停止下沉了
            if (e > input[child]) {
                break;
            }
        } else {
            //与大顶堆相反，找最小子节点
            if (right < len && input[child] > input[right]) {
                child = right;
            }
            //子节点都比较自己大，则停止下沉
            if (e < input[child]) {
                break;
            }
        }
        //把满足条件的子节点和当前节点交换位置，当前节点下沉
        input[i] = input[child];
        i = child;
    }
    //到达叶 停止 赋值
    input[i] = e;
}

private static int take(int[] input,boolean isBigHeap){
    //小顶堆 填充最大值 优先级队列源码是size减小，填充null
    int replaceNum = Integer.MAX_VALUE;
    if(isBigHeap)
    {
        //大顶堆 填充最小值
        replaceNum = Integer.MIN_VALUE;
    }
    //去除堆头
    int result = input[0];
    //把最尾部拿到最前进行一次下层
    input[0] = input[input.length-1];
    //填充占位值
    input[input.length-1] = replaceNum;
    //下沉
    siftDown(input,0,input[0],isBigHeap);
    return result;
}

快排思想

//快排实现
private static int quickSort(int begin,int end,int [] input,int k){
    if(begin>=end){
        return -1;
    }
    int mid = (begin+end)>>>1;
    int midValue = input[mid];
    //Part的选择用了一个优化防止快排退化成O(N^2),取头尾中间数然后拿中位数
    int part = getMidNum(input[begin],input[end],midValue);
    int partIndex = part == input[begin] ? begin : part == input[end] ? end : mid;
    swapNum(input,partIndex,begin);
    int i = begin;
    int j = end;
    while(i!=j){
        while (i<j && input[j]>=part){
            j--;
        }
        while(i<j && input[i]<=part){
            i++;
        }
        if(i<j){
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }
    input[partIndex]=input[j];
    input[j] = part;
    //和常规不同的跳出点 就是j的右边刚刚好是k-1个数
    if(input.length==j+k){
        return input[j];
    }

    int result1 = quickSort(begin,j-1,input,k);
    int result2 = quickSort(j+1,end,input,k);
    return result1 == -1?result2:result1;
}

static int getMidNum(int a,int b,int c)//优化1：三数取中法
{
    if(a>b){
        if(a>c){
            if(b>c){
                return b;
            }else{
                return c;
            }
        }else{
            return a;
        }
    }else{
        if(b>c){
            if(a>c){
                return a;
            }else{
                return c;
            }
        }else{
            return b;
        }
    }
}

static void swapNum(int[] input,int i,int j){
    int temp = input[i];
    input[i] = input[j];
    input[j] = temp;
}

第二题 统计1~10^5内有多少个1(o(N)实现)

其实一开始我的思路就对剑指offer一道题先入为主了，其实很简单，面试官给出了公式我由于太紧张
自我否定也没写出来，后面想了一下无非就是分奇偶然后采用DP优化。

假设i=偶数，那么他的1的个数会等于i>>>1里面二进制1的个数，(如4的二进制是100,2的二进制是010),
因此可以知道num[i]=num[i/2];

假设i=奇数，那么他的1的个数会等于i>>>1里面的二进制的个数再加1，(如5的二进制是101,2的二进制是010),其实就是右移把最低位的1给移动没了再补上。

所以得出公式就可以写出

//num[i*2] = num[i] i*2就一定是一个偶数，那么他仅仅就只是i的二进制左移，所以1的个数的一样的
//num[i*2+1] = num[i]+1 i*2+1就一定是一个奇数，那么因为可以看出i的二进制左移再加一，所以1的个数是num[i]+1
int k = 100000;
int [] a = new int[k+1];
int ans = 0;
for(int i = 1;i<=k;i++){
    //所以用i%2也可以
    //i&1也是在判奇偶
    a[i] = a[i/2]+(i&1);//i&1 如果i是奇数，那么就加1，如果i是偶数，那么就不加
    ans += a[i];
}

期间跟面试官还谈到了统计10进制下的1个数

int ones = 0;
for (int m = 1; m <= n; m *= 10) {
    int a = (int)n/m, b = n%m;
    ones += (a + 8) / 10 * m + (a % 10 == 1? 1 : 0) * (b + 1);
    // +8就是为了除10的时候+1,因为算上0~n一共有n+1个数，但是1是需要特殊计算的，加8
    // 特殊计算部分就是如 11000 到 11999 期间 这999+1个数都要加上去 因为 千位数的 1
}
return ones;

以下为解决方法
链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6

我画张表如下：

当n = 3141592时:

m a b ones
1 3141592 0 (3141592+8)/10*1+0=314160
10 314159 2 (314159+8)/10*10+0=314160
100 31415 92 (31415+8)/10*100+0=314200
1000 3141 592 (3141+8)/101000+1(592+1)=314593

当然后面还有m=10000,100000,1000000三种情况，对应着万位，十万位， 百万位为1时的情况

下面说下a+8的意义：

当考虑个位，十位，百位这三位为1的情况时：

个位 2 ，当个位取值1时，前面的六位数字可由0~314159组成，即314160种情况

十位9，当十位取值1时，前面的五位数字可由0\~31415组成，十位之后的一位可由0~9组成，组合情况31416*10=314160种情况

百位5，当百位取值为1时，前面的四位数字可由0\~3141组成，百位之后的两位可由0~99组成，组合情况为3142*100=314200种情况

注意：当考虑千位1时：

千位1，千位取值即1，前面的三位数字可由0\~314组成，但是当前面的值为314时，后面的三位只有0\~592种情况(特殊情况)，其余的情况即为前面的值为0\~313,后面三位有0\~999,情况数为3141000，所以总情况数为3141000 + 593=314593种情况

这时可发现和代码中的公式算的情况是吻合的，a+8的巧妙之处在于当a的最后一位(当前分析位)为0或1时，加8不产生进位，这是为需要单独算的特殊情况做准备，而当前分析位为2~9时，不需要考虑特殊情况，所以允许加8产生的进位。

KAI 面试题
关于Mysql之索引命中情况或EXPLAIN TYPE探讨
20190308头条二面