用友Java后端笔试2023-8-5

简介: 用友Java后端笔试2023-8-5

计算被直线划分区域

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

img

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

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

B轴平行坐标Y轴, B(x = 20);

输入描述

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

1,4,20,100 - 表两个点,点t1的坐标为(1,4),点t2坐标为(20,100)

输出描述

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

示例1

输入

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

输出

4

备注

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

思路

几何题,当两条线在这一区域内不相交时,区域空间增加1,当两条线的交点在这一区域内时,空间增加2,所以我们判断交点是否在区域内即可

代码

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        List<int[]> edges = new ArrayList<>();
        int res = 1;
 
        while(in.hasNextLine()){
            String inputLine = in.nextLine();
            if (inputLine.isEmpty()) {
                break; // 如果输入为空行,退出循环
            }
 
            res+=1;
            String[] line = inputLine.split(",");
            if(line[0]=="") continue;
 
            int[] nodes = new int[4];
            for(int i=0;i<4;i++){
                nodes[i] = Integer.parseInt(line[i]);
            }
            for(int[] edge:edges){
                double x = getIntersection(nodes[0],nodes[1],nodes[2],nodes[3],edge[0],edge[1],edge[2],edge[3]);
                if(x<20 && x>1) res+=1;
            }
            edges.add(nodes);
 
        }
 
        System.out.println(res);
    }
 
    static double getIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
        double k1 = (y1-y2)/(x1-x2);
        double b1 = y1 - k1*x1;
        double k2 = (y4-y3)/(x4-x3);
        double b2 = y3 - k2*x3;
        double x = (b2-b1)/(k1-k2);
        return x;
    }

最佳面试策略

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

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

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

示例1

输入

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

输出

5

说明

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

示例2

输入

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

输出

6

说明

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

思路

对于这道题,我们先定义dp的状态,dp[i][j]为面对i这个时间段的面试,已经面试了j次,决策后的最大可能值

先对interviews根据左端的值进行排序。

然后从后往前遍历interviews,使用二分搜索的方法算出当前面试i的下一场面试,然后我们逐次消耗面试次数,记录消耗j次面试机会的最大可能值,与进行下一次面试的值做比较,得到最终的最大值

注意,这里我们记录了dp[i+1][j]的值,就是当这个可能值 > i加上后面的面试的可能值时,会保留更大的那个可能值的结果

代码

import java.util.Arrays;
 
public class algorithm {
    public static void main(String[] args) {
        int[][] s = { {1,2,3},{3,4,2},{2,4,6} };
        System.out.println(maxValue(s,2));
 
    }
 
    public static int maxValue(int[][] interviews,int k){
        Arrays.sort(interviews,(a,b)->a[0]-b[0]);
 
        int n = interviews.length;
        int[][] dp = new int[n+1][k+1];
        for(int i=n-1;i>=0;i--){
            int l=i,r=n;
            while (l<r){
                int mid = (l+r)>>1;
                if(interviews[i][1]<interviews[mid][0]) r=mid;
                else l=mid+1;
            }
            for(int j=0;j<=k;j++){
                dp[i][j] = dp[i+1][j];
                if(j>0) dp[i][j] = Math.max(dp[i][j],dp[r][j-1]+interviews[i][2]);
            }
        }
 
        return dp[0][k];
    }
    
}

星球间的最短通路

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

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

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

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

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

示例1

输入

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

输出

6

备注

1 ≤ N ≤ 100

思路

使用kruskal (克鲁斯卡尔)算法求最小图,先将所有的边按照从小到大的顺序排序,然后通过并查集将他们组合为一个最小图

代码

import java.util.Arrays;
 
public class Main {
 
    int[] fa;
 
    void init(int n){
        fa = new int[n];
        for(int i=0;i<n;i++) fa[i] = i;
    }
 
    int find(int x){
        return x == fa[x]? x: (fa[x] = find(fa[x] ));
    }
 
    void union(int x,int y){
        fa[find(x)] = find(y);
    }
 
    public int minimumCost(int n,int[][] connections){
        init(20000);
        Arrays.sort(connections,(a,b)->a[2]-b[2]);
        int ans = 0;
        for(int[] arr:connections){
            int a = arr[0],b=arr[1],w=arr[2];
            if(find(a)!=find(b)){
                union(a,b);
                ans+=w;
 
            }
        }
 
        return ans;
 
    }
 
 
    public static void main(String[] args) {
        Main a = new Main();
        int[][] s = {
                {1, 2, 5}, {1, 3, 6}, {2, 3, 1}
        };
 
        System.out.println(a.minimumCost(3,s))
        ;
 
 
    }
}

python

m = int(input())
 
map1 = []
for i in range(m):
    x,y,z = map(int,input().split(" "))
    map1.append((x,y,z))
 
parent = [i for i in range(m+1)]
def find(i):
    if parent[i] != i:
        return find(parent[i])
    return parent[i]
 
def union(x,y):
    parent[find(y)] = find(x);
 
map1 = sorted(map1,key=lambda x:x[2])
 
ans = 0
for i in range(m):
    if find(map1[i][0]) != find(map1[i][1]):
        union(map1[i][0],map1[i][1])
        ans += map1[i][2]
 
print(ans)


目录
相关文章
|
4天前
|
前端开发 小程序 Java
uniapp上传图片 前端以及java后端代码实现
uniapp上传图片 前端以及java后端代码实现
86 0
|
4天前
|
弹性计算 前端开发 小程序
微信小程序上传文件至阿里云OSS直传(java后端签名+前端直传)
当前的通用文件上传方式是通过前端上传到服务器,再由服务器转存至对象存储。这种方式在处理小文件时效率尚可,但大文件上传因受限于服务器带宽,速度较慢。例如,一个100MB的文件在5Mbps带宽的阿里云ECS上上传至服务器需160秒。为解决此问题,可以采用后端签名的方式,使微信小程序直接上传文件到阿里云OSS,绕过服务器中转。具体操作包括在JAVA后端引入相关依赖,生成签名,并在微信小程序前端使用这个签名进行文件上传,注意设置正确的请求头和formData参数。这样能提高大文件上传的速度。
|
4天前
|
消息中间件 Java 微服务
构建高性能微服务架构:Java后端实践
【4月更文挑战第8天】 在当今互联网应用的快速迭代与高并发挑战下,微服务架构以其灵活性和扩展性成为众多企业技术选型的宠儿。本文将深入探讨在Java后端开发中,如何构建一个高性能的微服务系统,涵盖从基础架构设计、关键技术选型到性能优化策略的全方位分析。我们将透过实际案例,剖析微服务实践中的最佳模式与常见陷阱,为后端开发人员提供一份实操指南。
|
3天前
|
Dubbo Java 应用服务中间件
Java外包是如何进入阿里的熬夜整理出Java后端学习路线
Java外包是如何进入阿里的熬夜整理出Java后端学习路线
|
4天前
|
缓存 NoSQL Java
构建高性能微服务架构:Java后端的实践之路
【5月更文挑战第5天】在当今快速迭代和高并发需求的软件开发领域,微服务架构因其灵活性、可扩展性而受到青睐。本文将深入探讨如何在Java后端环境中构建一个高性能的微服务系统,涵盖关键的设计原则、常用的框架选择以及性能优化技巧。我们将重点讨论如何通过合理的服务划分、高效的数据存储策略、智能的缓存机制以及有效的负载均衡技术来提升整体系统的响应速度和处理能力。
|
4天前
|
安全 Java 开发者
构建高效微服务架构:后端开发的新范式Java中的多线程并发编程实践
【4月更文挑战第29天】在数字化转型的浪潮中,微服务架构已成为软件开发的一大趋势。它通过解耦复杂系统、提升可伸缩性和促进敏捷开发来满足现代企业不断变化的业务需求。本文将深入探讨微服务的核心概念、设计原则以及如何利用最新的后端技术栈构建和部署高效的微服务架构。我们将分析微服务带来的挑战,包括服务治理、数据一致性和网络延迟问题,并讨论相应的解决方案。通过实际案例分析和最佳实践的分享,旨在为后端开发者提供一套实施微服务的全面指导。 【4月更文挑战第29天】在现代软件开发中,多线程技术是提高程序性能和响应能力的重要手段。本文通过介绍Java语言的多线程机制,探讨了如何有效地实现线程同步和通信,以及如
|
4天前
|
JSON 前端开发 Java
⚠⚠⚠java后端开发中,前后端联调过程一些常见的低级/低端问题汇总⚠⚠⚠
⚠⚠⚠java后端开发中,前后端联调过程一些常见的低级/低端问题汇总⚠⚠⚠
|
4天前
|
安全 Java 持续交付
构建高性能微服务架构:Java后端的实践之路
【4月更文挑战第8天】 在现代软件开发领域,微服务架构已经成为提高系统可维护性、扩展性和技术栈独立性的关键解决方案。本文将深入探讨如何利用Java后端技术构建一个高性能的微服务系统。我们将重点讨论微服务设计原则、系统拆分策略、关键性能优化技巧以及安全性考虑。通过实际案例分析,揭示如何在保证系统稳定性的同时实现敏捷开发和部署。
|
4天前
|
SQL 前端开发 Java
Java后端进阶之路: JavaWeb(四)
Java后端进阶之路: JavaWeb
35 1
|
4天前
|
XML SQL Java
Java后端进阶之路: JavaWeb(三)
Java后端进阶之路: JavaWeb
35 1