首页 > 用友笔试-0818-附第三题代码

用友笔试-0818-附第三题代码

1、压缩字符串 - 100%
比如“aaabbbcaaa” ,压缩成“a3b3c1a3”;
如果压缩后的长度不是小于等于原字符串长度,就返回原字符串

2、上下反转二维数组 - 100%
比如 {[1,2,3],[4,5,6] ,[7,8,9]}
反转后为{[7,8,9],[4,5,6],[1,2,3]}

3、现在给定所有的城市和航班,以及出发城市src,你的任务是找到从scr城市出发到其他所有城市最便宜的机票价格列表。 假设两个城市之间机票价格不会超过Integer.MAX_VAULUE - 100%
思路:dijkstra模板题

public static int[] findAllCheapestPrice(int n, int[][] flights, int src) {
        int[][] g = new int[n + 10][n + 10];
        int[] dis = new int[n];
        boolean[] st = new boolean[n + 10];
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], 0x3f3f3f3f);
        }

        for (int i = 0; i < flights.length; i++) {
            int a = flights[i][0];
            int b = flights[i][1];
            int c = flights[i][2];
            g[a][b] = Math.min(g[a][b], c);
        }

        dijkstra(g, dis, st, src, n);
        for (int i = 0; i < dis.length; i ++) {
            if(dis[i] == 0x3f3f3f3f){
                dis[i] = -1;
            }
        }
        return dis;
    }

    public static void dijkstra(int[][] g, int[] dis, boolean[] st, int start, int n) {
        Arrays.fill(dis, 0x3f3f3f3f);
        dis[start] = 0;

        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 0; j < n; j++) {
                if (!st[j] && (t == -1 || dis[t] > dis[j])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 0; j < n; j++) {
                dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
            }
        }
    }

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐