睡前重做网易笔试题，菜鸡的愤怒，大神帮忙看下

网易笔试做的很差，屋里在安网线，一直被打扰，做题的时候思路一直被打断，大脑一片空白

交卷之后感觉很烦，吃了个饭，玩了会儿游戏，躺着准备睡觉了却一直想着这个事，手机都玩不下去

于是决定趁还记得题目过来重做一遍

第一道，小易打瞌睡

记得数据设定是

n m (n为课堂时间，m为叫醒时间)

n个数

m个数

做题的时候直接暴力，现在想其实只需贪心便利一遍打瞌睡的兴趣最大值就行，醒着的时候兴趣值是必加的

代码如下

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n],b = new int[n];
        for(int i = 0;i < n;i++) a[i] = in.nextInt();
        for(int i = 0;i < n;i++) b[i] = in.nextInt();
        int max = 0; // 打瞌睡叫醒的最大收益
        int re = 0; // 没睡觉时候的收益
        for(int i = 0;i < n;i++){
            if(b[i] == 0){
                int temp = 0;
                for(int j = i;j < i+m;j++){
                    if(j >= n) break;
                    if(b[j] == 0)temp+=a[j];
                }
                if(temp > max)
                    max = temp;
            }
            else re+=a[i];
        }
        System.out.println(re+max);

第二题苹果堆

我记得题目就是给出许多堆苹果，每堆有若干个，找出第n个苹果在哪一个堆

数据是

n （n个苹果堆）

每个堆的苹果数

k (k个数据)

第几个苹果

思路，做题是暴力直接遍历超时了，现在回头一想，干嘛要遍历查那么多次啊，二分查找就是啦啊，真的很气

       public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] heap = new int[n];
        for(int i = 0;i < n;i++){
            if(i == 0) heap[i] = in.nextInt();
            else heap[i] = heap[i-1]+in.nextInt();
        } // 每个heap的值就是本身苹果数量加前面的总苹果数量，之后就直接二分查找了
        int k = in.nextInt();
        for(int i = 0;i < k;i++){
            System.out.println(findIndex(heap,in.nextInt(),0,n)+1);
        }
    }
    
    public static int findIndex(int[] heap,int k,int l,int h){
        if(heap[l] > k) return l;
        if(h - l == 1)
            return h;
        int mid = (l+h)/2;
        int re = 0;
        if(heap[mid] > k) re = findIndex(heap,k,l,mid);
        else if(heap[mid] < k) re = findIndex(heap,k,mid,h);
        else return mid;
        return re;
    }

第三题小易的字典

n个a和m个z组成的字典序字符串集，查找第k个字是什么

前面的题都是很简单的题，这道需要一点分析

暴力是拿这个题没办法的了，因为数量是阶乘级别的n个‘a’m个‘z’，可以组成的字符串就是 $C_{n+m}^{n}$ 个

那么就要探索一下字典序的字符串产生规律了以aaazzz为例

aaazzz 可以有 $C_{6}^{3}$ =20个字符串依次来梳理

a azzz zazz zzaz zzza

a aazzz - >

z aazz -> ....

aaazzz ->

a aazz -> ....

z aaazz ->

z aaaz aaza azaa zaaa

a azz zaz zza

aazz ->

z aaz aza zaa

我想这足以看出来规律了，我觉得可以说是动态规划也可以说是二分查找

代码：

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int z = in.nextInt();
        int k = in.nextInt();
        StringBuilder sb = new StringBuilder();
        findStr(sb,a,z,k);
        System.out.println(sb.toString());

    }
    
    public static void findStr(StringBuilder s,int a,int z,int k){
        
        
        if(a == 1){ 
            for(int i = 0;i < z+a;i++){
                if(i == k-1) s.append('a');
                else s.append('z');
            }
        }
        else if(z == 1){
            for(int i = 0;i < a+z;i++){
                if(i == a+z-k) s.append('z');
                else s.append('a');
            }
        }
        else{
            int u = 1,d = 1;
            for(int i = a+z-1;i > z;i--) u*=i;
            for(int i = a-1;i > 0;i--) d*=i;
            int asum = u/d;
            if(k > asum){
                z--;
                s.append('z');
                k-=asum;
                findStr(s,a,z,k);
            }
            else {
                a--;
                s.append('a');
                findStr(s,a,z,k);
            }
        }
    }

前两道写了20分钟？

第三题写了半个小时

反正做完没到一个小时，做出来舒服多了，可以去睡觉了

自己测试，都没有问题，但确实是记不到题目，不能保证是真的没问题，发上来求各位大佬帮忙看一下吧

每个代码都没有加意外情况比如n大于已有的苹果数量啊，第k个字符，k超出了字典容量啊。毕竟马后炮加这些没啥意思

唉，主要还是太菜了

#网易#