Summary of written test questions

滴滴6.26笔试

编程题出现的问题：

第一题 难度：Easy

小明下载同时下载多个游戏，每个游戏下载速度为vi，剩余下载时间ti。

下载完一个游戏后他的下载速度会分配到其他任务上，问下载完所有游戏需要的时间

思路一：

你可能觉得解决方式就应该是顺着思路，建立两个容器，将数组1速度依次放进去，再将数组二剩余时间依次放进去，然后找出数组二中剩余时间最小的一个游戏，将他进行去除，然后所以剩下的游戏都要减去这个经过的时间（即下载完的游戏的剩余时间），这是很复杂的，而且剩余时间组里可能会出现另外n个正好也下载完的情况，这样还要将n个另外的进行剔除

题目的关键是理解速度之间其实是可以加和的（题目并不是要求我们在具体某一时间的数组二的值即他们的剩余时间，只要求我们的所有时间）

速度之间总和就是总速度，但是这里也不要想某个游戏下载完之后再将速度数组剔除一个，然后将这个游戏的下载速度/数组当前个数，再都加上再重新计算，这样又绕回了思路一，我们只需要关注结尾和开始

我们要理解在结束时总会有一个确定的消耗流量的，因为游戏总大小一定是确定的，并且每一个游戏的速度也是我们给出的，一个游戏下载完，下载速度会分配给其他游戏，但总带宽是不变的，所以只需要让总下载流量/总带宽即可

那么总流量怎么求呢？

很明显我们由于给出了剩余时间和当前某游戏下载速度，只需要将速度*剩余时间就是这个游戏的流量，进行循环遍历加和即可。

下面给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package DiDi;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double speed = 0;
        double sum  = 0;
        int[] v = new int[n];
        int[] t = new int[n];
        for (int i = 0;i<n;i++){
            v[i] = scanner.nextInt();
            speed+=v[i];
        }
        for (int i = 0;i<n;i++){
            t[i] = scanner.nextInt();
            sum+=v[i]*t[i];
        }
        System.out.println(String.format("%.4f",(sum/speed)));
    }
}

第二题 难度：mid 二维dp动态规划

1
2
3

有n个积木，每个积木长度为2，要在长度为k的空地上将这些个积木摆放下来。

每一个积木必须摆放在前一个积木之上（也就是摆放在它前一格或后一格），问一共有多少种摆法，结果对998244353取模。

因为有k的长度，并且类似于一串序列似的问题，所以考虑动态规划，那为什么要用二维的呢？

原因是一维的不够用，我们能用dp[i]表示第i空间的摆法吗，不能，因为边界不能进行限制，摆在前面后面都会超出单个空间/或者用另一种思路想，“探头”到我这个位置的积木是极难确定的，因为我的积木是下往上叠的，所以考虑i作为一层的数目，其实你会发现也是无法直接统计的，所以只能扩展到二维，二维之后其实发现i作为行空间，列空间都是无所谓的，因为dp[i] [j]都会精确到某个单位面积的空间，i作为一层比较好理解。

很明显，第i层的摆法是i层每一个空间加和，我们求的是所有层的加和，但这里是不能求dp[i] = dp[i] [0-j加和]的，因为一个空间积木基于下层的j-1或是j+1(两层重合的那个单位)，所以我们最后只能是把二维数组给遍历加和.

1
2
3

dp[i][j]如何去判断递推关系？j是一个左右关系，因为j才有可能出界，所以判断j
如果j-1>=0，说明该积木位于下层积木的右方，下层积木的index是j-1
如果j+1<k-1（或者<=k-2）,上面这两个条件只要满足，dp[i][j]就加上dp[i-1][j-1]或是第二种dp[i-1][j+1]

也就是说，当前空间的积木摆法=下一层（左边摆法+右边摆法）只有两个因素会影响dp[i] [j]，就是下一层的前和后，满足边界就加上摆法

长度是k，第一个空间index如果作为0的话，所以最后一个空间是k-1，而一个积木是占两个空间的，我们总得确定积木是位于哪一位置的，不能忽坐忽右，所以我们就规定左边是一个积木的落脚点吧，所以积木不可能落脚到k-1上，因为长度就超过了，所以上面的j+1必须是<k-1的

重要：总结自己出现的问题

1.题意看不懂

一定要花时间先看懂题，每个量的表示符号是什么，然后应该怎么输入

2.输入问题

使用Scanner输入，一定要选择好方法，对于要求在一行内获得一组数组，那么对于一行的数据，没必要直接用nextLine，这样获得的是字符串，还要进行分割，并且转Integer很麻烦，直接用nextInt而不是其他的方法，虽然nextInt以空格就能结束，不能获取一整行的

但是可以使用循环啊，在输入端数与数之间的分割是空格分开的是固定的，输入端照样还是输入一行，用循环能接收，用Line也可以接收，只不过Line是直接接受一整行，而循环一个个接受一行罢了，从输入端看来都是一样的，循环放入一个数组中不是正好吗

3.基础不扎实

要求获得的数字是四位小数，直接用long？，long代表的是长整形，应该使用double

4.知识点不全

一些题会指定输出结果的位数，而像double是可以有很多位的，如果要求以某一个确定的位数进行输出，那么应该使用format格式化

• ← Previous Post
• Next Post →