注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(73)-最多转机K次的最便宜航线[算法]  

2018-03-15 07:26:59|  分类: 动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:n城市之间有m条航线,每条航线从城市u出发到达城市v,票价为w。给你若干城市的航线信息,一个出发城市src和一个目标城市dst,请问从城市src飞到城市dst最多转机K次的最便宜的价格是多少?如果不存在从城市src飞到城市dst的线路,返回-1

例如:如果n=3,flights = [[0,1,100],[1,2,100],[0,2,500]],那么这3个城市之间的航班可以用下图表示:

程序员面试题精选100题(73)-最多转机K次的最便宜航线[算法] - 何海涛 - 微软、Google等面试题

如果src=0,dst=2,也就是从城市0出发飞往城市2,当K=0时(中间不能转机),那么最便宜的票价是500;当K=1时(中间最多转机1次),那么最便宜的票价是200(从城市0经过城市1转机到达城市2)。


分析:这是LeetCode的第787题。


解法一:深度优先搜索

 

首先,我们可以考虑简化的问题:如何求出从城市src到城市dst的所有线路的价格?这用回溯法(也就是深度优先搜索)不难求出。也就是从城市src出发,根据输入的城市之间的航线信息,找出src能够到达的每个城市i,按照深度优先的搜索顺序从每个城市i出发前往城市dst。

 

接下来再考虑中间转机的次数。我们每转机一次,则剩余的能够转机的次数就减去1。如果已经转机了K次还没有到达城市dst,则没有必要再搜索下去了。我们可以利用这个转机次数来为回溯法剪枝。

 

由于需要求出最便宜的票价,我们每通过某一路径到达城市dst之后都更新当前的已知的最便宜票价。如果到达某一城市的时候票价已经超过了当前已知的最便宜票价,也没有必要再搜索下去了。也就是说我们还可以利用票价来为回溯法剪枝。

 

以下是上述思路的参考代码:

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    int[][] graph = new int[n][n];
    for (int[] flight : flights) {
        graph[flight[0]][flight[1]] = flight[2];
    }
   
    boolean[] visited = new boolean[n];
    int[] minCost = {Integer.MAX_VALUE};
    findCheapestPrice(graph, visited, src, dst, K, minCost, 0);
   
    return minCost[0] == Integer.MAX_VALUE ? -1 : minCost[0];
}

private void findCheapestPrice(int[][] graph, boolean[] visited,
                               int src, int dst, int K, int[] minCost, int cost) {
    if (src == dst) {
        minCost[0] = Math.min(minCost[0], cost);
    }
   
    if (K >= 0 && cost < minCost[0]) {
        for (int i = 0; i < graph.length; ++i) {
            if (graph[src][i] != 0 && !visited[i]) {
                visited[i] = true;
                findCheapestPrice(graph, visited, i, dst, K - 1,
                                  minCost, cost + graph[src][i]);
                visited[i] = false;
            }
        }
    }
}

法二: 广度优先搜索

根据广度优先搜索的特性,我们很容易求出从城市src出发能够直达的城市(在图中和src直接相连的节点)、中转一次能够到达的城市(在图中从src出发需要搜索两步到达的节点),以此类推可以求出中转K次能够到达的城市在图中从src出发需要搜索K+1步到达的节点)。

 

值得注意的是,常规的广度优先搜索算法从src出发到达dst,经过的一定是最短路径。这个题目不是求从src到dst的最短路径,而是票价最便宜的线路,因此要对常规的广度优先搜索算法稍微做点调整

 

假设我们从src出发经过s次转机到达某一城市c,此时到达c需要的票价是p1。如果之后我们发现了另外一条从src出发经过t次转机(t>s)到达同一城市c,同时这条新线路到达c的票价是p2并且p2<p1,那么我们接下来仍要从城市c出发,更新从src出发经过城市c抵达dst的票价。 

基于广度优先搜索算法的参考代码如下:

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    int[][] graph = new int[n][n];
    for (int[] flight : flights) {
        graph[flight[0]][flight[1]] = flight[2];
    }
   
    int[] costs = new int[n];
    Arrays.fill(costs, Integer.MAX_VALUE);
   
    Set<Integer> set1 = new HashSet<>();
    set1.add(src);
    costs[src] = 0;
   
    while (!set1.isEmpty() && K >= 0) {
        Set<Integer> set2 = new HashSet<>();
        for (int from : set1) {
            for (int i = 0; i < n; ++i) {
                if (graph[from][i] > 0 && costs[from] + graph[from][i] < costs[i]) {
                    costs[i] = costs[from] + graph[from][i];
                    set2.add(i);
                }
            }
        }
       
        set1 = set2;
        K--;
    }
   
    return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
}


上述代码中数组costs的意义是经过若干步骤之后从src出发到达每个城市的最低票价。

法三:动态规划

由于问题是求最低票价,也就是求问题的最优解。通常遇到最优解的问题我们可以尝试动态规划。运用动态规划的第一步是用递归的方法去分析问题。

 

我们用函数f(c,i)表示经过最多中转k次到达城市c的最低票价,那么f(dst,K)就是我们需要的最终输出。

 

首先,经过i-1次中转也有可能到达城市c,也就是f(c,i)=f(c,i-1)。另外,对于其他经过i-1次中转能够到达的每个其他城市d,如果这些城市有到达c的航班,那么f(c,i)=f(d,i-1)+flight(d,c),flight(d,c)表示从城市d到城市c的票价。f(c,i)应该是f(c,i-1)以及所有f(d,i-1)+flight(d,c)的最小值。

 

我们可以用一个二维矩阵来缓存计算的中间结果。该矩阵的行数是K,列数是城市的数目。我们可以从上到下逐行求出这个矩阵中的每个数值。

 

我们进一步观察发现,在求解f(c,i)的时候我们只需要用到第i-1行的值,因此我们可以优化空间效率,只需要保留其中的两行(第i-1行和第i行)就可以了。 

该思路的参考代码如下:

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    int[][] dp = new int[2][n];
    for (int[] row : dp) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }
   
    dp[0][src] = 0;
    int cur = 1;
    while (K >= 0) {
        int prev = 1 - cur;
        for (int[] flight : flights) {
            if (dp[prev][flight[0]] < Integer.MAX_VALUE) {
                dp[cur][flight[1]] = Math.min(dp[cur][flight[1]],
                                              dp[prev][flight[0]] + flight[2]);
            }
        }
       
        dp[prev] = Arrays.copyOf(dp[cur], n);
        cur = prev;
        K--;
    }
   
    return dp[1 - cur][dst] == Integer.MAX_VALUE ? -1 : dp[1 - cur][dst];
}   


举一反三:


一个N*M的矩阵上每个点都有一定数量的糖果。给你一个起点坐标X1、Y1和终点坐标X2、Y2,从起点到终点最多走K步,每一步可以上下左右移动,但不能沿着对角线移动,每到达矩阵的一点可以拿走该点的糖果。请输出可以拿到的糖果的最大值。

这个题目和前面的类似,都是在图上最多走若干步从一个起点到达一个终点。虽然一个是求最大值、一个是求最小值,但求解的思路是一模一样的。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(1578)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018