2018-08-11网易互联网笔试

1.高数课打瞌睡，总共n分钟，唤醒持续k分钟，求最大收益
利用滑动窗口寻找最大收益唤醒区间

public class Doze {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] score = new int[n];
        int[] listen = new int[n];
        int res=0;
        for (int i = 0;i < n;i ++){
            score[i] = sc.nextInt();
        }
        for (int i = 0;i < n;i ++){
            listen[i] = sc.nextInt();
        }
        res = helper(score,listen,n,k);
        System.out.println(res);
    }
    
    public static int helper(int[] score,int[] listen,int n,int k) {
        int res=0;
        int improve = 0;
        int low=0;
        int high=0;
        int temp=0;
        for (int i = 0; i < n; i++) {
            if(listen[i]==1)
                res +=score[i];
        }
        for (int i = 0; i < k; i++) {
            if(listen[i]==0)
                temp +=score[i];
            high=i;
        }
        improve=Math.max(improve, temp);
        while (high<n-1) {
            low++;
            high++;
            if(listen[high]==0)temp+=score[high];
            if(listen[low-1]==0)temp-=score[low-1];
            improve=Math.max(improve, temp);
        }
        return res+improve;
    }
    
}

2.从左到右有n堆苹果，给一个数字qi；判断第qi个苹果在第几堆
利用TreeMap记录苹果堆数量上限，直接获取qi的位置

public class Apple {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {//注意while处理多个case
            int n = in.nextInt();
            int last = 0;
            TreeMap<Integer,Integer> map = new TreeMap<>();
            for(int i = 0;i<n;i++){
                last = last+in.nextInt();
                map.put(last, i+1);
            }
            int m = in.nextInt();
            for(int i = 0;i<m;i++){
                int qi = in.nextInt(); 
                if(map.ceilingKey(qi)==null) {
                    System.out.println(-1);
                    break;
                }       
                System.out.println(map.get(map.ceilingKey(qi)));
            }
        }
        in.close();
    }
    
}

3.由n个a，m个z组成的字符串按字典序排序，输出第k个字符串

public class aazz{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {//注意while处理多个case
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            double max = getMax(n, m);
            if(k>max){
                System.out.println(-1);
            }else {
                helper(n,m,k);
                System.out.println();
            }
        }
    }
    static void helper(int n,int m,int k){
        if(n == 0 && m == 0){
            return;
        }
        if(n == 0){//a已用完，后面全是z
            for(int i = 0;i<m;i++){
                System.out.print("z");
            }
            return;
        }else if (m == 0) {//z已用完，后面全是a
            for(int i = 0;i<n;i++){
                System.out.print("a");
            }
            return;
        }
        double max = getMax(n-1, m);
        if(max>=k){//n-1个a和m个z可以有k种以上可能的字符串，说明a开头
            System.out.print("a");
            helper(n-1, m, k);
        }else {
            System.out.print("z");
            helper(n, m-1, (int)Math.round(k-max));
        }
    }
        //(n+m)!/n!*m!(字符串总数)
    static double getMax(int n,int m){
        double max = 1;
        for(int i = 0;i<n;i++){
            max *= (m+n-i);
        }
        for(int i = 0;i<n;i++){
            max /= i+1;
        }
        return max;
    }
}
//方法二
public class StringDp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = 1;   // 重要
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <=  m; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        StringBuffer sb = new StringBuffer();
        if (k > dp[n][m]) {
            System.out.println(-1);
        } else {
            int len = n + m;
            for (int i = 0; i < len; i++) {
                if (n > 0 && k <= dp[n-1][m]) {
                    sb.append("a");
                    n--;
                } else {
                    if (n > 0) {
                        k -= dp[n-1][m];
                    }
                    sb.append("z");
                    m--;
                }
            }
            System.out.println(sb.toString());
        }
    }
}