笔试题

网易 8 月 3 号研发岗笔试的第一题，也是四道题中最简单的一道。这道题涉及到前缀和的应用，所以我想借这道题给大家讲一讲前缀和相关的一些知识，以后大家遇到这道题，就可以快速秒杀了。

问题描述
下面我描述下这道题，不过我给的描述是简化版的，实际上再做笔试题的时候，每道题的描述都巨长，一般都会根据实际场景来给出问题的，有些人可能阅读了十几分钟，然后不知道自己要干嘛，我这里给出最简化的版本。

有一个班级有 n 个人，给出 n 个元素，第 i 个元素代表 第 i 位同学的考试成绩，接下来进行 m 次询问，每次询问给出一个数值 t ，表示第 t 个同学，然后需要我们输出第 t 个同学的成绩超过班级百分之几的人，百分数 p 可以这样算：p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位，并且需要四舍五入。
输入描述：第一行输入两个数 n 和 m，两个数以空格隔开，表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni，表示每个同学的分数，第三行输入 m 个数值mi，表示每次询问是询问第几个同学。（注意，这里 2<=n，m<=100000，0<=ni<=150，1<=mi<=n）
输出描述：输出 m 行，每一行输出一个百分数 p，代表超过班级百分之几的人。
示例1：
输入 ：
3 2
50 60 70
1 2
输出
33.333333%
66.666667%

第一题大致是这样，不过不是和原题完全一样哈，在输入和输出有小许区别，因为具体的输入输出我忘了。我这个描述说简化好像也挺长，不过原题就更加长了。

解答
那么这道题难吗？说实话不难，不过你可以先自己再脑子里想想怎么做比较好，或许在考场上 20分钟你还真不一
定做的出来。

有些人说，这还不简单，每次询问的时候，我都遍历一下所有人的成绩，这样的花时间复杂度是 O(n * m)，显然，如果你这样做，那么是一定通不过的，一定会超时。一般暴力法能够通过 20% ~ 30% 的测试用力，如果一道题 20 分的话，能拿到 4~6 分。如果你实在没思路，那么暴力也是个不错的选择。

1、二分法

这道题我是用二分法做的，就是先对所有人的成绩进行排序，不过排序的时候我们需要开一个新的数组来存储。然后每次查询的时候可以通过二分查找进行匹配，由于用到了排序，需要花 O(nlogn) 的时间，m 次查询花的时间大致为 O(mlogn)。所以平均时间复杂度可以算是 O((m+n)logn)。这个时间复杂度通过所有测试
用例，代码如下(没学过java的也能看懂)：

public class Main {
    // 主函数，相当于c语言的main方法
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // 存放成绩的数组
        int[] a = new int[n];
        // 存放排序过后的成绩
        int[] b = new int[n];
                // 输入 n 个人的成绩
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
            b[i] = a[i];
        }
        // 排序
        Arrays.sort(b);
        // 进行查询
        for(int j = 0; j < m; j++){
            // 输入是要查询第几个同学
            int t = in.nextInt();
            // 把这个同学的分数拿出来
            int fen = a[t - 1];
            // 通过二分查找是排在第几位
            int sum = binarySearch(b, fen) - 1;
            double t = sum * 1.0 / n * 100;
            System.out.printf("%.6f\n", t);

        }
    }

    private static int binarySearch(int[] b, int fen){
        int l = 0;
        int r = b.length - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(b[mid] > fen){
                r = mid - 1;
            }else if(b[mid] < fen){
                l = mid + 1;
            }else{
                    // 由于存在分数相同的人，所以还要往后查找
                while(mid < b.length && b[mid] == fen){
                    mid++;
                }
                return mid;
            }
        }
        return 0;
    }
}

这里说明一下，输出的时候我没有输出"%"号哈。

前缀和

不过这道题更好的做法是采用前缀和来做。题设中每个同学的分数不超过 150，不小于 0，那么我们可以用一个数组 arr，然后让 arr[i] 表示分数不超过 i 的人数。通过这种方式，我们可以把时间复杂度控制在 O(n+m)。直接看代码吧，会更好理解（这里我就不写输入的代码了，用a[]存放成绩，m[]存放m次询问）：

void f(int a[], int m[]){
    int n = a.length;
    int[] arr = new int[151];
    //先统计分数为 i 的有多少人
    for(int i = 0; i < n; i++){
        arr[a[i]]++;
    }
    // 接着构造前缀和
    for(int i = 1; i < 151; i++){
        arr[i] = arr[i] + arr[i-1];
    }
    // 进行 m 次询问
    for(int i = 0; i < m.length; i++){
        // 取出成绩
        int score = a[m[i]-1];
        // 有多少人的成绩不超过 score的
        int sum = arr[score];
        System.out.printf("%.6f\n", sum * 1.0 / n * 100 );
    }
}

这种方法就叫做前缀和，用这种方法简单了很多。当然前缀和还有其他应用，例如：

如果给你一个数组 arr[]，然后进行 m 次询问，每次询问输入两个数 i，j（i <= j）。要求你输出 arr[i] ~ arr[j] 这个区间的和。这个时候就可以使用前缀和的方式了。前缀和的构造也是很好构造的，例如 arr[] 变成前缀和的构造方式如下

for(int i = 1; i < arr.length; i++){
   arr[i] = arr[i] + arr[i-1];
}

前缀和看起来还是挺简单的，不过在做题中，或许会有意想不到的作用，例如这次的笔试，所以今天给大家讲解一下。

最后我再问你一个和前缀和类似的问题，给你一串长度为n的数列a1,a2,a3……an，要求对a[i]~a[j]进行m次操作：

操作一：将a[i]~a[j]内的元素都加上P

操作二：将a[i]~a[j]内的元素都减去P

最后再给出一个询问求a[i]-a[j]内的元素之和。

这个你会怎么做呢？这个时候就涉及到差分的知识了，不过它和前缀和类似，感兴趣的可以研究一下。

最后
这里关于笔试题有几点建议，由于笔试题大多数都需要我们处理输入输出，而像 leetcode，剑指 offer 都是不需要我们处理这些的，所以会不熟悉，所以我建议可以去刷下往年的真题熟悉一下。

还有就是大部分都是可以直接暴力的，然后能拿 20%~30%的分数，想了十分钟还是没好的思路的，建议直接暴力。

还有就是有时候笔试是不准你用本地 IDE 的，所以我建议平时刷题的时候，直接在网页打代码，别跑到本地 IDE 打好再粘贴过来。

前几天有个朋友去面试字节跳动，面试官问了他一道链表相关的算法题，不过他一时之间没做出来，就来问了我一下，感觉这道题还不错，拿来讲一讲。

题目
这其实是一道变形的链表反转题，大致描述如下

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

解答
这道题的难点在于，是从链表的尾部开始组起的，而不是从链表的头部，如果是头部的话，那我们还是比较容易做的，因为你可以遍历链表，每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起。不过这道题肯定是用递归比较好做，对递归不大懂的建议看我之前写的一篇文章 为什么你学不会递归？告别递归，谈谈我的一些经验 ，这篇文章写了关于递归的一些套路。

先做一道类似的反转题
在做这道题之前，我们不仿先来看看如果从头部开始组起的话，应该怎么做呢？例如：链表:1->2->3->4->5->6->7->8->null, K = 3。调整后：3->2->1->6->5->4->7->8->null。其中 7，8不调整，因为不够一组。

对于这道题，如果你不知道怎么逆序一个单链表，那么可以看一下我之前写的如何优雅着反转单链表

这道题我们可以用递归来实现，假设方法reverseKNode()的功能是将单链表的每K个节点之间逆序(从头部开始组起的哦);reverse()方法的功能是将一个单链表逆序。

那么对于下面的这个单链表，其中 K = 3。

我们把前K个节点与后面的节点分割出来：

temp指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。再调用reverse()方法把head指向的那3个节点进行逆序，结果如下：

再次声明，如果对这个递归看不大懂的，建议看下我那篇递归的文章

接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：

代码如下：

    //k个为一组逆序
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
        for (int i = 1; i < k && temp != null; i++) {
            temp = temp.next;
        }
        //判断节点的数量是否能够凑成一组
        if(temp == null)
            return head;

        ListNode t2 = temp.next;
        temp.next = null;
        //把当前的组进行逆序
        ListNode newHead = reverseList(head);
        //把之后的节点进行分组逆序
        ListNode newTemp = reverseKGroup(t2, k);
        // 把两部分连接起来
        head.next = newTemp;

        return newHead;
    }

    //逆序单链表
    private static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }

回到本题

这两道题可以说是及其相似的了，只是一道从头部开始组起，这道从头部开始组起的，也是 leetcode 的第 25 题。而面试的时候，经常会进行变形，例如这道字节跳动的题，它变成从尾部开始组起，可能你一时之间就不知道该怎么弄了。当然，可能有人一下子就反应出来，把他秒杀了。

其实这道题很好做滴，你只需要先把单链表进行一次逆序，逆序之后就能转化为从头部开始组起了，然后按照我上面的解法，处理完之后，把结果再次逆序即搞定。两次逆序相当于没逆序。

例如对于链表（其中 K = 3）

我们把它从尾部开始组起，每 K 个节点为一组进行逆序。步骤如下

1、先进行逆序

逆序之后就可以把问题转化为从头部开始组起，每 K 个节点为一组进行逆序。

2、处理后的结果如下

3、接着在把结果逆序一次，结果如下

代码如下

public ListNode solve(ListNode head, int k) {
    // 调用逆序函数
    head = reverse(head);
    // 调用每 k 个为一组的逆序函数（从头部开始组起）
    head = reverseKGroup(head, k);
    // 在逆序一次
    head = reverse(head);
    return head;

}

类似于这种需要先进行逆序的还要两个链表相加，这道题字节跳动的笔试题也有出过，如下图的第二题

这道题就需要先把两个链表逆序，再节点间相加，最后在合并了。