完美世界笔试编程题AC一道

第一道题要计算的是最小漂流船,已知每艘船最多可以承载2人,但是重量不能超过limit,求最少需要多少船只?
第一行输入的是参与人员的体重数组,第二行输入的是漂流船承载的最大重量。求最小船只数?
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] str = sc.nextLine().split(" ");
            int limit = Integer.parseInt(sc.nextLine());
            int n = str.length;
            int[] weight = new int[n];
            for(int i=0;i<n;i++){
                weight[i] = Integer.parseInt(str[i]);
            }
            Arrays.sort(weight);
            System.out.println(minchip(weight,limit));
        }
    }

    private static int minchip(int[] weight, int limit) {
        int sum =0;
        int i=0,j=weight.length-1;
        while(i<=j){
            if(weight[i]+weight[j]<=limit){
                sum++;
                i++;
                j--;
            }else{
                sum++;
                j--;
            }
        }
        return sum;
    }
}
第二道要计算主城之间的最小距离,应该是要用迪杰斯塔拉算法。时间不太够,没写出来。有大神AC出来的吗?

#完美世界##笔试题目#
全部评论
class Node{ int[] dis; int val = Integer.MAX_VALUE; public Node(int[] dis) { this.dis = dis; } } public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int[][] dis = new int[6][6];         Node[] node = new Node[6];         for (int i = 0; i < 6; i ++) {             String[] temp = sc.nextLine().split(" ");             for (int j = 0; j < 6; j ++) {                 dis[i][j] = Integer.parseInt(temp[j]);             }             node[i] = new Node(dis[i]);         }         Queue<Node> queue = new LinkedList<>();         queue.offer(node[0]);         node[0].val = 0;         while (! queue.isEmpty()) {          Node temp = queue.poll();          for (int i = 0; i < 6; i ++) {          if (temp.dis[i] != 0 && temp.dis[i] != -1) {          node[i].val = Math.min(node[i].val, temp.val + temp.dis[i]);          queue.offer(node[i]);          }          }         }         for (Node x: node) {          System.out.println(x.val);         }     } } 第二题仅作参考🙁
点赞 回复
分享
发布于 2019-08-23 21:26
有面试通知了吗,23号笔试完没消息
点赞 回复
分享
发布于 2019-08-28 20:47
饿了么
校招火热招聘中
官网直投
第二道不会写。。
点赞 回复
分享
发布于 2019-08-23 20:18
过了60%
点赞 回复
分享
发布于 2019-08-23 20:19
第二道60%
点赞 回复
分享
发布于 2019-08-23 20:19
这第一题不是华为的原题嘛
点赞 回复
分享
发布于 2019-08-23 20:29
import java.util.Scanner; public class Main{     public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] times = new int[6][6]; for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { times[i][j] = sc.nextInt(); if (times[i][j] == -1) { times[i][j] = Integer.MAX_VALUE; } } } int[] dist = distence(times); for (int i = 1; i < 6; i++) { System.out.println(dist[i]); } } public static int[] distence(int[][] times) { int maxTime = Integer.MAX_VALUE; int N = 6; int[] dist = new int[N]; boolean[] isVisited = new boolean[N]; for (int i = 0; i < N; i++) { dist[i] = times[0][i]; } isVisited[0] = true; for (int i = 0; i < N; i++) { int min = maxTime; int k = 0; for (int j = 0; j < N; j++) { if (!isVisited[j] && dist[j] < min) { min = dist[j]; k = j; } } isVisited[k] = true; for (int j = 0; j < N; j++) { if (!isVisited[j] && times[k][j] != maxTime) { if (dist[j] >= times[k][j] + dist[k]) { dist[j] = times[k][j] + dist[k]; } } } } return dist; } } ac了,按回忆写的,有些可能有问题,但是大概思路就是这个
点赞 回复
分享
发布于 2019-08-23 20:39
投得什么岗?
点赞 回复
分享
发布于 2019-08-23 20:51
你们第一题不超时么?我和你一样的思路超时了啊
点赞 回复
分享
发布于 2019-08-23 20:57
第二题图论我都没复习过,直接暴力递归做出来的,竟然都能ac
点赞 回复
分享
发布于 2019-08-23 21:06
我的题好像和你不一样 全ac
点赞 回复
分享
发布于 2019-08-23 21:09
1.6,第一题ac,第二题迪杰斯特拉只过了0.6
点赞 回复
分享
发布于 2019-08-23 21:14
第一题跟楼主思路一致,但只ac20%,有没有大佬指教下本菜鸡import java.util.Arrays;import java.util.Scanner; public class exam { public static void main(String[] args) { Scanner in =new Scanner(System.in); while(in.hasNext()){ int n=in.nextInt(); int[] nums=new int[n]; for(int i=0;i<n;i++){ nums[i]=in.nextInt(); } int limit=in.nextInt(); int res=0,i=0,j=n-1; Arrays.sort(nums); while(j>=i){ if(j>i){ if(nums[j]+nums[i]>limit){ res++;j--; }else{ i++;j--;res++; } }else{ res++; break; } } System.out.print(res); } }}
点赞 回复
分享
发布于 2019-08-23 21:17
我跟你差不多一样,AC不过去,奇怪了
点赞 回复
分享
发布于 2019-08-23 21:19
import java.util.ArrayList;import java.util.LinkedList;import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); } private void solve() { Scanner scanner = new Scanner(System.in); int n = 6; int adj[][] = new int[n][n]; for (int i = 0; i < n; i++) { String[] strings= scanner.nextLine().split(" "); for (int j = 0; j < n; j++) { adj[i][j] =Integer.valueOf(strings[j]); } } Graph graph = new Graph(adj); graph.bfs(0); } static class Graph { int[][] adj; int nVerts; boolean[] visited; private Graph(int[][] adj) { this.adj = adj; this.nVerts = adj.length; this.visited = new boolean[nVerts]; } private void bfs(int start) { int[] dis=new int[nVerts]; for (int i = 0; i < nVerts; i++) { dis[i]=Integer.MAX_VALUE; } visited[start] = true; LinkedList<Integer> queue = new LinkedList<>(); queue.add(start); dis[start]=0; while (!queue.isEmpty()) { int v = queue.remove(); ArrayList<Integer> vs; vs =getNextVertex(v); for (Integer v1:vs){ int distance=adj[v][v1]; if (distance+dis[v]<dis[v1]) dis[v1]=distance+dis[v]; if (!visited[v1]) { queue.add(v1); visited[v1] = true; } } } for (int i = 0; i <nVerts; i++) { if (i!=0){ System.out.println(dis[i]); } } } private ArrayList<Integer> getNextVertex(int v) { ArrayList<Integer> adjVs = new ArrayList<>(); for (int i = 0; i < adj.length; i++) { if (i!=v&&adj[v][i] != -1) adjVs.add(i); } return adjVs; } }}
点赞 回复
分享
发布于 2019-08-23 22:13
第二题一眼肯定了是地接克拉斯算法,奈何写错了,哭泣
点赞 回复
分享
发布于 2019-08-23 23:45
深度遍历0.80😂😂
点赞 回复
分享
发布于 2019-08-27 11:27

相关推荐

点赞 16 评论
分享
牛客网
牛客企业服务