应届生求职网手机APP

应届生求职招聘论坛

QQ登录

只需一步,快速开始

查看: 813|回复: 0

[面试] 网易笔试题详细解答(Java)【转载】,2018-08

[复制链接]

主题

好友

1030

积分

TP

发表于 2018-8-22 16:35 |显示全部楼层
对于下面公式不显示的问题,可以看这个链接
[a href="https://fengxc.me/2018%E7%BD%91%E6%98%93%E7%AC%94%E8%AF%95%E9%A2%98%E5%8F%8A%E8%A7%A3%E7%AD%94-Java.html#more" target="_blank"]https://fengxc.me/2018%E7%BD%91%E6%98%93%E7%AC%94%E8%AF%95%E9%A2%98%E5%8F%8A%E8%A7%A3%E7%AD%94-Java.html#more[/a])
显示效果更好。

题目一

题目描述

小易觉得高数课太无聊了,决定睡觉。不过他对课上的一些内容挺感兴趣,所以希望老师讲到有趣的地方的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度,并以分数量化,以及他在这堂课上每分钟是否会睡着,你可以叫醒他一次,这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

输入描述

第一行n,k, (1 <= n, k <= $10^5$),表示这堂课持续多少分钟,以及叫醒小易一次使他能够保持清醒的时间。
第二行 n个数,$a{1},a{2},..., a{n} (1<= a{i} <= 10^4)$,表示小易对每分钟知识点的感兴趣评分。
第三行 n个数,$t{1}, t{2}, ..., t_{n}$,表示每分钟小易是否清醒,1表示清醒。

输出描述

小易这堂课听到的知识点的最大兴趣值。

示例

输入

6 3
1 3 5 2 5 4
1 1 0 1 0 0

输出

16

解题思路1

首先对示例进行分析,输出16是在第3分钟将小易唤醒。所以小易的分值为1+3+5+2+5 = 16。
其次我们可以考虑一种比较暴力的解法,即我们先把醒着的分值和sum计算出来,然后我们再遍历每分钟是否醒着,如果为0,那么我们就遍历接下来k个值,把这k个值未醒着的分值加到前面的sum上,然后再去与最大值进行比较更新,直到遍历结束。不过这样由于超时只能过90%的测试用例。

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = sc.nextInt();
        }
        int[] sleep = new int[n];
        for (int i = 0; i < n; i++) {
            sleep[i] = sc.nextInt();
        }
        int sum = 0;
        int max = -1;
        for (int i = 0; i < n; i++) {
            if (sleep[i] == 1) {
                sum += scores[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (sleep[i] == 0) {
                int temp = sum;
                for (int j = i; j < Math.min(i + k, n); j++) {
                    if (sleep[j] == 0) {
                        temp += scores[j];
                    }
                }
                if (temp > max) {
                    max = temp;
                }
            }
        }
        System.out.println(max);
    }
}

解题思路2

我们可以考虑在遍历每分钟是否醒着时,不去遍历后面的k个值,而采取利用下标进行计算的方式。这个时候我们就需要利用到累加和的思想了。
我们首先定义3个数组,长度都为n。
leftScore: 表示从左到右醒着的分值的累加和。
rightScore: 表示从右到左醒着的分值的累加和。
total: 表示从左到右分数的累加和。
然后当我们遍历到为未醒着的位置i时,那么这时的总体分数为3部分之和:leftScore[i-1] + rightScore[i+k] + (total[i+k-1] - total[i-1])。
当然还要加上一些边界处理。

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = sc.nextInt();
        }
        int[] sleep = new int[n];
        for (int i = 0; i < n; i++) {
            sleep[i] = sc.nextInt();
        }
        int sum = 0;
        int[] leftscore = new int[n];
        for (int i = 0; i < n; i++) {
            if (sleep[i] == 1) {
                sum += scores[i];
            }
            leftscore[i] = sum;
        }
        int[] rightscore = new int[n];
        sum = 0;
        for (int i = n-1; i > -1; i--) {
            if (sleep[i] == 1) {
                sum += scores[i];
            }
            rightscore[i] = sum;
        }
        int[] total = new int[n];
        sum = 0;
        for (int i = 0; i < n; i++) {
            sum += scores[i];
            total[i] = sum;
        }
        int max = -1;
        for (int i = 0; i < n; i++) {
            if (sleep[i] == 0) {
                int temp = 0;
                temp += (i - 1) < 0 ? 0 : leftscore[i-1];
                temp += (i + k) >= n ? 0 : rightscore[i+k];
                temp += total[Math.min(i+k-1, n-1)] - (i - 1 < 0 ? 0 : total[i-1]);
                if (temp > max) {
                    max = temp;
                }
            }
        }
        System.out.println(max);
    }
}

题目二

题目描述

又到了丰收的季节,恰好小易去牛牛的果园里游玩。 牛牛常说他多整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛。 在果园里有N堆苹果,每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。 牛牛觉得问题太简单了,所以希望你来替他回答。

输入描述

第一行 一个数 n (1<= n <= $10^5$)
第二行 n个数 $a{i}$ (1<=$a{i}$<=1000),表示从左往右数第i堆有多少苹果
第三行 一个数m (1<= m <= $10^5$),表示有m次询问
第四行 m个数$q{i}$, 表示小易希望知道第$q{i}$个苹果属于哪一堆。

输出描述

m行,第i行输出第$q_{i}$个苹果属于哪一堆。

示例

输入

5
2 7 3 4 9
3
1 25 11

输出

1
5
3

解题思路

这个题目题意比较好理解,思路也比较简单。首先对苹果数进行累加和。然后再对查询进行二分查找。

解题代码

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] appleNums = new int[n];
        for (int i = 0; i < n; i++) {
            appleNums[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] query = new int[m];
        for (int i = 0; i < m; i++) {
            query[i] = sc.nextInt();
        }
        int[] leftsum = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += appleNums[i];
            leftsum[i] = sum;
        }
        for (int i = 0; i < m; i++) {
            System.out.println(binSearch(leftsum, query[i]) + 1);
        }
    }

    public static int binSearch(int[] arr, int k) {
        int mid = arr.length / 2;
        if (k == arr[mid]) {
            return mid;
        }
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            mid = (end - start) / 2 + start;
            if (k < arr[mid]) {
                end = mid - 1;
            } else if(k > arr[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return start;
    }
}

题目三

题目描述

给你n个a,m个z组成所有可能的字符串,并将字符串按字典序从小到大排列,输出第k个字符串。
若不存在,输出-1。

输入描述

第一行为三个数,分别为a的个数n,z的个数m,第k个字符串。

输出描述

第k个字符串

示例

输入

2 2 6

输出

zzaa

解题思路

这个题我在笔试的时候是采用全排列的方式做的,时间复杂度很高,只过20%,没有利用只有a,z,且很多重复的这些信息。
下面的思路是自己后来想的以及结合一些网上的思路。
现在我们来算给定n和m后,总共有多少中情况:我们很容易得到是$C{m+n}^m = \frac{(m+n)!}{m!n!}$,如果k大于这个数,即可返回-1。
接下来我们用动态规划来做这个题目,假设dp[i][j]表示i个a和j个z的方案数,根据上面这个公式列表计算我们可以发现:d[i][j] = dp[i-1][j] + dp[i][j-1];
这样我们就可以求出方案数。然后我们来求输出字符串。
假设我们现在考虑输出字符串的第i个字符,如果当前选了a字符,假设后面剩余字符a和z的个数是$m
{1},n{1}$,那么后面所能组成的字符串总数为$dp[m{1}][n{1}]$。如果k小于$dp[m{1}][n{1}]$,那么我们就能选a,因为后面组成的数目大于k,我们要选字符a来缩小这个组合数。
否则,就选z,这时k -= $dp[m
{1}][n_{1}]$,这是因为要减去a形成的方案数。

解题代码

public class Main {
    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 n1 = n;
            int m1 = m;
            for (int i = 0; i < n+m; i++) {
                if (n1 > 0 && k <= dp[n1-1][m1]) {
                    sb.append("a");
                    n1--;
                } else {
                    if (n1 > 0) {
                        k -= dp[n1-1][m1];
                    }
                    sb.append("z");
                    m1--;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

From:[a href="https://www.nowcoder.com/discuss/93285" target="_blank"]Nowcoder[/a])
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /1 下一条


应届生求职网APP扫码下载

应届生APP|Archiver|应届生求职网YingJieSheng.COM ( 沪ICP备12015550号-13 )

GMT+8, 2019-12-12 08:54

Powered by Discuz!

© 2001-2012 Comsenz Inc.

           

快速回复 返回顶部 返回列表