滴滴9.13笔试

岗位是安卓开发。由于不太会图相关的算法,所以都是用BFS解决的,运气好都A了。
第一题,修桥。
import java.util.*;

public class Q1_20200913 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = sc.nextInt();
        for (int o = 0; o < times; o++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int limit = sc.nextInt();
            List<Integer>[] bridges = new List[n + 1];
            for (int i = 0; i < n + 1; i++) {
                bridges[i] = new LinkedList<>();
            }
            for (int i = 0; i < m; i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                int cost = sc.nextInt();
                if (cost <= limit) {
                    bridges[l].add(r);
                    bridges[r].add(l);
                }
            }

            HashSet<Integer> arrived = new HashSet<>();
            Deque<Integer> list = new LinkedList<>(bridges[1]);
            while (!list.isEmpty()) {
                int cur = list.poll();
                arrived.add(cur);
                for (Integer i : bridges[cur]) {
                    if (!arrived.contains(i)) {
                        arrived.add(i);
                        list.add(i);
                    }
                }
            }

            if (arrived.size() == n) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

第二题,巴黎旅行。
import java.util.*;

public class Q2_20200913 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            List<int[]>[] ways = new List[n + 1];
            for (int i = 0; i < n + 1; i++) {
                ways[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                int cost = sc.nextInt();
                int[] lr = {r, cost};
                ways[l].add(lr);
                int[] rl = {l, cost};
                ways[r].add(rl);
            }
            int start = sc.nextInt();
            int tar = sc.nextInt();
            String time = sc.next();

            int[] arrived = new int[n + 1];
            Arrays.fill(arrived, Integer.MAX_VALUE);
            Deque<int[]> list = new LinkedList<>();
            list.add(new int[]{start, 0});
            while (!list.isEmpty()) {
                int[] cur = list.poll();
                int pos = cur[0];
                int cost = cur[1];
                if (cost < arrived[pos]) {
                    arrived[pos] = cost;
                    for (int[] arr : ways[pos]) {
                        if (arr[1] + cost < arrived[arr[0]]) {
                            list.add(new int[]{arr[0], arr[1] + cost});
                        }
                    }
                }
            }
            int res = arrived[tar];
            String out = help(res, time);
            System.out.println(out);
        }
    }

    static int[] months = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public static String help(int res, String time) {
        String[] temp = time.split("\\.");
        int month = Integer.parseInt(temp[0]);
        temp = temp[1].split("/");
        int day = Integer.parseInt(temp[0]);
        int hour = Integer.parseInt(temp[1]);

        hour += res;
        if (hour >= 24) {
            day += hour / 24;
            hour = hour % 24;
        }
        while (day > months[month]) {
            day -= months[month];
            month++;
        }
        StringBuilder arrive = new StringBuilder();
        arrive.append(month).append(".")
                .append(day).append("/").append(hour);

        return arrive.toString();
    }
}



#滴滴##笔试题目#
全部评论
ios和安卓题居然不一样
点赞 回复 分享
发布于 2020-09-13 20:50
和算法一样,最后一题输出没时间搞完了,惨烈。就非要搞那个形式的输出干嘛...
点赞 回复 分享
发布于 2020-09-13 20:52
第二题有python AC的吗?用python写dijkstra从来没AC过
点赞 回复 分享
发布于 2020-09-13 20:57
大佬666,我算出最短路之前就没了
点赞 回复 分享
发布于 2020-09-13 20:58
枯了 
点赞 回复 分享
发布于 2020-09-13 20:59
大佬强呀
点赞 回复 分享
发布于 2020-09-13 21:04
第一题就是去掉无效边,求图的连通数,可以套并查集模板,第二题直接最短路径算法
点赞 回复 分享
发布于 2020-09-13 21:07
兄弟笔试都没完,你就把答案贴出来了啊。。。不怕别人抄了雷同吗
点赞 回复 分享
发布于 2020-09-13 21:08

相关推荐

2 13 评论
分享
牛客网
牛客企业服务