阿里巴巴笔试题2021/06/04场

算法 Java
算法
发布日期:   2021-06-04
文章字数:   1.7k

阿里巴巴笔试题2021/06/04场

简介

共有两道编程题。

采用牛客网，ACM模式，需要自己手写输入输出。

可以采用本地IDE，我用的IDEA。

会后台录屏，开摄像头，手机扫码监控后在小程序界面不能切屏（如果我有俩手机那他是不是也没办法……）

考试须知

放几个官方说明，如果不了解牛客网的ACM模式的话可以先看一下：

牛客在线笔试常见问题_猿生活_牛客网 (nowcoder.com)

牛客网在线判题系统使用帮助_站内公告_牛客网 (nowcoder.com)

oj的java输入hasNext和hasNextLine区别_技术交流_牛客网 (nowcoder.com)

a+b__ACM模式练习

接下来就是2021/06/04的两道编程题复盘。

自己第一道题用例都通过了，第二道题只过了20%。总体感觉难度不算难？主要是自己太菜了。

  • 第一道题貌似是数学题/脑筋急转弯。。。或者有更高深的说法我不知道。
  • 第二道题就是图的遍历，其中边是带权重的。

1. 小区划分

题目

目前没有在网上找到原题与题解。

题目描述

输入输出描述

示例1

自己思路

下面是我的解法，思路很简单，从给的示例里看出来的。

要使得俩小区平均价值最大，那么肯定找最高的鸭，排序，从大到小。

然后钱多人少的放在一个小区，钱多人也多的放在一个小区。

  • 钱多人少，这样平均财富值肯定高鸭，传说中的高档小区；

  • 钱不够那就人来凑呗，勉强也能搞点财富值，算是个中档小区吧；

总结一下核心思路如下：

  1. 首先就是先排序，从大到小；
  2. 之后再选，钱最多的几个人，放在人数少的第一个小区里；
  3. 然后再选，钱很多但没有那么多的几个人，放在人数多的第二个小区里。剩下的人就可以拜拜了（没钱买房子的就是我TAT）

Java代码

代码（个人习惯把题目写道注释里了）：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    /**
     * 1. 住小区问题
     * n个人，每个人有个财富值 a[i]
     * 两个小区,分别住 n1 和 n2 个人
     * 两个小区的平均财富值尽可能大
     * 小区人口财富总和 / 总人数
     * 第一行：n,n1,n2
     * 共n个人，第一个小区n1，第二个小区n2
     * 第二行：每个人的财富值
     *
     * 例子：
     * 4 2 1
     * 1 4 2 3
     * out:
     * 6.500000 (结果保留6位有效小数)
     *
     * 6.5 = (2+3)/2 + 4/1
     * **/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int n1 = in.nextInt();
            int n2 = in.nextInt();

            ArrayList<Integer> a = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                a.add(in.nextInt());
            }

            Collections.sort(a);
            Collections.reverse(a);

            ArrayList<Integer> a1 = new ArrayList<>();
            ArrayList<Integer> a2 = new ArrayList<>();

            // 第一个小区
            for (int i = 0; i < Math.min(n1, n2); i++) {
                a1.add(a.get(i));
            }
            // 第二个小区
            for (int i = Math.min(n1, n2); i < Math.max(n1, n2)+Math.min(n1,n2); i++) {
                a2.add(a.get(i));
            }

            Double res = 0.00000;
            Double tempSum = 0.0;
            for (int i = 0; i < a1.size(); i++) {
                tempSum += Double.valueOf(a1.get(i));
            }
            res = Double.valueOf(tempSum/a1.size());
            tempSum = 0.0;
            for (int i = 0; i < a2.size(); i++) {
                tempSum += Double.valueOf(a2.get(i));
            }
            res += Double.valueOf(tempSum/a2.size());

            System.out.println("a1"+a1.toString());
            System.out.println("a2"+a2.toString());

            System.out.println(res.toString());


        }
    }
}

最后还有个幺蛾子，就是自己打印的调试信息里，倒数两个 System.out.println 忘了删除，导致第一次调试没通过。。。

然后删了就可以了，直接通过全部用例。

通过

2. 重建网络

题目

题目描述

输入输出描述

示例1

输入：

1
2
3
4
5
6
4 5 7
4 1 3
1 2 5
2 3 8
2 4 1
3 4 4

示例2

输入：

1
2
3
4
5
6
7
4 6 5
1 2 1
1 3 1
1 4 2
2 4 1
4 3 1
3 2 1

自己画了一下图：

示例1

示例2

修改结果

自己思路与改进

图的遍历，但是不会写。

于是瞎写，用邻接矩阵数组存的。矩阵matrix这个单词也忘了怎么拼，于是瞎写了个mux。

自己最初的思路，只考虑了下面的前3步，代码只实现了前两步……果然还是太菜了。

  1. 存入邻接矩阵
  2. 遍历邻接矩阵，如果两个点之间的边小于最小速度，修改其权重，并将 最小速度-权重 加入结果
  3. 还要进行进一步的判断，如果这两个点之间，已经存在一条路径，而且路径的权重均大于最小速度，那么这个就不需要计算了
  4. 进一步思考，如果存在多条路径，而且这几条路径上，都有几条边不满足最小速度，则要进行计算比较：
    选择变化最小，也就是其选择 最小速度*路径中的边条数 - 路径权重之和 的路径，修改其每条边的值，并加入结果

注意，我这里说的路径是是包含多条边的，而边只是两点之间的一条边。

自己代码 (错误，仅通过20%测试用例)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.Scanner;

public class Main {
    /**
     * n节点，m条边
     * 每条边有个网络速度 w_i
     * 删掉 m-(n-1) 条边
     * 任意两点有且仅有一条简单路径
     * 网络最低速度要等于k
     * 可以调节一些边的网络速度，每一次操作，可以把网络速度+1或者-1
     * 问：最少需要的操作次数
     *
     * 保证给出的是连通图
     *
     * 第一行：n,m,k
     * n条边，m个节点，k网络速度最低
     * 每行：u_i, v_i , w_i
     * 节点 u 到 v 的一条速度为 w_i 的双向边
     *
     * 输出：
     * sum，最少操作次数
     *
     * **/

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();

            int res = 0;

            // 邻接矩阵
            int[][] mux = new int[n][n];
            for (int i = 0; i < m; i++) {
                int v1 = in.nextInt();
                int v2 = in.nextInt();
                int w = in.nextInt();

                mux[v1-1][v2-1] = w;
                mux[v2-1][v1-1] = w;
            }
            for (int i = 0; i < mux.length; i++) {
                for (int j = i; j < mux[i].length; j++) {

                    if(mux[i][j] !=0){
                        mux[j][i] =0;
                        if (mux[i][j] < k){
                            res += (k-mux[i][j]);
                            mux[i][j] = -1;
                        }
                    }
//                    System.out.print(mux[i][j]+" ");
                }
//                System.out.println();
            }
            System.out.println(res);
        }
    }
}

20%通过

感觉这20%的case，应该都是多条路径中，只更改直接相连的那条边的情况，省去了我上面说的比较的步骤。

补充

貌似可以用回溯算法解决？

暂时还没写出代码来。

6.27：淦，这不就是最小生成树算法的改版？这里应该叫最大生成树。

图的最小生成树 - 智者侬哥 - 博客园 (cnblogs.com)

文章作者: SongX64
文章链接: https://SongX64.github.io/2021/06/04/20210604%E9%98%BF%E9%87%8C%E7%AC%94%E8%AF%95/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 SongX64 !
算法 Java
赏
  目录