浅浅记录一次用友笔试「2023-08-06」

计算被直线划分区域

在笛卡尔坐标系，存在区域[A, B]，被不同线划分成多块小的区域，简单起见，假设这些不同线都直线并且不存在三条直线相交于一点的情况

那么，如何快速计算某个时刻，在 X 坐标轴上[A, B]区间面积被直线划分成多少块？

• A 轴平行坐标Y轴，A (x = 1)

• B 轴平行坐标Y轴，B (x = 20)

如下图所示，区域[A, B]被三条划分为 7 个块！！

输入描述

• 输入采用多行输入，一行 4 个数据，分别表示两个坐标点，一行一条直线

• 如：[1,4,20,100]表示两个点，点 t1 的坐标为(1, 4)，点 t2 坐标为(20, 100)

输出描述

• 输出为整数，表示被输入线段划分的面积个数

示例 1

• 输入

xxxxxxxxxx
1,37,20,4
1,7,20,121

• 输出

xxxxxxxxxx
4

备注

• AB 之间的线段不平行于 Y 轴

思路

最初，只有 1 个块，当添加第一条直线后，整个区域被划分为 2 个块

当添加第二天直线后，如果与之前的直线无相交，则整个区域被划分为 3 个块；如果与之前的直线有相交，则整个区域被划分为 4 个块

总结：若有 n 交点，则区域会新增 n 个块

代码

x
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<int[]> g = new ArrayList<>();
        int ans = 1;
        // 注意多行输入
        // hasNextLine() 必须和 nextLine() 配合
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String[] sp = s.split(",");
            int[] v = new int[4];
            for (int i = 0; i < 4; i++) v[i] = Integer.parseInt(sp[i]);
            ans++;
            for (int[] prev : g) {
                Double[] p = f(prev, v);
                if (p[0] != null && 1 < p[0] && p[0] < 20) ans++;
            }
            g.add(v);
        }
        System.out.println(ans);
    }
    // 求交点 (此模版比较万能)
    private static Double[] f(int[] s, int[] v) {
        double x1 = s[0], y1 = s[1], x2 = s[2], y2 = s[3];
        double x3 = v[0], y3 = v[1], x4 = v[2], y4 = v[3];
        
        // y = a1 * x + b1
        double a1 = (y2 - y1) / (x2 - x1);
        double b1 = y1 - a1 * x1;
        // y = a2 * x + b2
        double a2 = (y4 - y3) / (x4 - x3);
        double b2 = y3 - a2 * x3;
        // 平行，无交点 (注意：即使重合，也不算有交点)
        if (a1 == a2) return new Double[]{null, null};
        double x = (b2 - b1) / (a1 - a2);
        double y = a1 * x + b1;
        return new Double[]{x, y};
    }
}

最佳面试策略

小明最近在找工作，收到了许多面试邀约，可参加的面试由interviews数组表示，其中interviews[i] = [startTimei, endTimei, possibilityi]，表示第 i 个面试在startTimei开始，endTimei结束，面试成功的可能性是possibilityi，该值越大，通过面试的可能性越大，由于精力限制，小明最多可以参加k场面试

小明同一时间只能参加一场面试，如果要参加某场面试，必须完整参加这场面试才可能通过面试，即不能同时参加一个开始时间和另一个结束时间相同的两场面试

请给出小明面试成功可能性的最大和

示例 1

• 输入

xxxxxxxxxx
[[1,2,3],[3,4,2],[2,4,4]],2

• 输出

xxxxxxxxxx
5

• 说明

xxxxxxxxxx
小明参加 [1, 2, 3]， [3, 4, 2] 两场面试，面试通过可能性的和为 3 + 2 = 5

示例 2

• 输入

xxxxxxxxxx
[[1,2,3],[3,4,2],[2,4,6]],2

• 输出

xxxxxxxxxx
6

• 说明

xxxxxxxxxx
只参加面试 [2, 4, 6]，面试通过的可能性的和最大，为 6

相似题目

• 1751. 最多可以参加的会议数目 II

• 1235. 规划兼职工作

• 2008. 出租车的最大盈利

代码

x
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算小明面试成功可能性的最大和
     * @param interviews int整型二维数组 interviews[i] = [startTime_i, endTime_i, possibility_i]
     *        第 i 个面试在 startTime_i 时间开始， endTime_i 时间结束，通过的可能性是 possibility_i
     * @param k int整型 最多参加的面试次数
     * @return int整型
     */
    public int maxValue (int[][] interviews, int k) {
        // write code here
        int n = interviews.length;
        Arrays.sort(interviews, (a, b) -> a[1] - b[1]);
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            int l = 0, r = i - 1, target = interviews[i - 1][0];
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (interviews[m - 1][1] < target) l = m;
                else r = m - 1;
            }
            for (int j = 1; j <= k; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[l][j - 1] + interviews[i - 1][2]);
            }
        }
        return dp[n][k];
    }
   
}

星球间的最短通路

在一个遥远的银河中，有 N 个星球 (编号从 1 到 N)，这些星球之间通过星际门进行连接。每个星际门都连接两个星球，并且可以双向通行

每个星际门的开启需要消耗一定的能量，这个能量由星际门上的数字表示。每个星际门上的数字都是唯一的

现在，由于某种原因，所有的星际门都处于关闭状态。作为一个探索者，你的任务是找出一种方式，开启最少的星际门，使得所有的星球都至少通过一个开启的星际门与其他星球连接

给你一些可连接的选项connections，其中connections[i] = [Xi, Yi, Mi]表示星球Xi和星球Yi之间可以开启一个星际门，并消耗Mi能量

计算联通所有星球所需的最小能量消耗。如果无法联通所有星球，则输出 -1

示例 1

• 输入

xxxxxxxxxx
3,[[1, 2, 5], [1, 3, 6], [2, 3, 1]]

• 输出

xxxxxxxxxx
6

备注

• 1 <= N <= 100

思路

最小生成树，推荐使用 Kruskal 算法，配合并查集

相似题目

• 最小生成树

代码

x
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    private int count;
    private int[] parent;
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        Arrays.sort(cost, (a, b) -> a[2] - b[2]);

        int ans = 0;
        for (int i = 0; i < m; i++) {
            int v = cost[i][0] - 1, u = cost[i][1] - 1, c = cost[i][2];
            if (connected(v, u)) continue;
            union(v, u);
            ans += c;
        }
        if (count != 1) return -1;
        return ans;
    }

    private int find(int x) {
        if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }
    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return ;
        parent[rootP] = rootQ;
        count--;
    }
    private boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
}

反思

由于这是本人第一次笔试，有点自乱阵脚，虽然之前也模拟写过笔试 (😈)，但亲自上场该慌还是慌！！！

一开始以为只有三个编程题，但点开一看，居然还有 10 个单选题和 10 个多选题，时间一共 90 分钟，这一波出其不意更慌了，完全打乱了阵脚。在写完选择题后，已经花费了 30 分钟，还剩 60 分钟

看了第一个编程题，接着又看了第二个编程题，一看认出之前写过，所以直接先写第二个编程题，大概花了 10 多分钟写完了第二题然后直接看第三题，脑海里回想起貌似写过类似的，然后直接一波 DFS

当第三题代码写到一半时，不知电脑咋回事，突然卡了，点啥都没反应，索性直接重启，真是雪上加霜，一波三折！！当时已经花了 60 分钟，还剩 30 分钟

重启后，继续按照 DFS 的思路把剩下的代码写完了，但运行时直接报错，但是又很赶时间，就越找不出错误，诶！！心态太重要了，而且我还不停的在关注右下角的时间，越看越慌

总之，这是一次体验感极差的笔试，也是一次失败的笔试，自己的心态太容易被影响！！！！

改进：

• 在笔试前几分钟，把字签了

• 尽量不要跳题，一般前面的题目简单些

• 先把所有题目浏览一遍，这样可以在写题时简单思考思考

• 以后练习时，计时每题 20 分钟！！